표준 ML에서 BST 노드의 조상 찾기

Question

SML의 BST에서 노드의 부모 및 조부모를 찾으려고합니다.

나는이 기능을 수정하기 위해 노력했다

: 입력의 형식, 비교 출력 변경하여

fun search(tree : bst, compare, (data) = 
    let fun s(Leaf) = NONE 
      | s(Node{data=nodedata,left=left,right=right}) = 
       (case compare(data,nodedata) of 
         LESS => s(left) 
        | GREATER => s(right) 
        | EQUAL => SOME (Node{data=nodedata,left=left,right=right})) 
    in 
     s(tree) 
    end 

을 : 분명히

fun search(tree : bst, compare, (data) = 
let fun s(Leaf) = NONE 
|s(Node{data=nodedata,left=Node{data=nodedata1,left=left1,right=right1},right=right}) =       
     (case compare(data,nodedata) of 
      LESS => s(left) 
      | GREATER => s(right) 
      | EQUAL => SOME nodedata) 

가 작동하지 않습니다와 나는이 가정 이것을하는 더 쉬운 방법.

나는 (나를 위해) 또한 내가 확인 노드의 할아버지를 유지하는 방법을 찾아야 그러나 그것은 어렵다, 내가 확인하고있어 작동 각 노드의 현재 아버지를 구하기 위해 새로운 변수를 추가했다.

아이디어가 있으십니까? 미리 감사드립니다.

Answer 1

우선 검색 기능이 제대로 작동하지 않아 조금만 청소했습니다. 형식 선언 오류에서 언 바운드 형식 변수를 피하려면 bst 형식을 'a bst으로 정의해야합니다. 나는 또한 paranthesis 오류를 수정했습니다. 여기 search 기능의 나의 버전은 다음과 같습니다

datatype 'a bst = Leaf | Node of {data: 'a, left: 'a bst, right: 'a bst} 

(*search(tree, compare, key) = t 
    where t = the tree which has `key` as its root 
    *) 
fun search(tree : 'a bst, compare : ('a * 'a -> order), key : 'a) 
      : 'a bst option = 
    let 
    fun s(tree: 'a bst) : 'a bst option = 
     case tree of 
     Leaf => NONE 
     | Node({data=x, left=l, right=r}) => 
      case compare(key,x) of 
      LESS => s(l) 
      | GREATER => s(r) 
      | EQUAL => SOME tree 
    in 
     s(tree) 
    end 
(*Example: 
search(Node({data=5, 
      left=Node({data=3, 
         left=Node({data=2,left=Leaf,right=Leaf}), 
         right=Node({data=4,left=Leaf,right=Leaf})}), 
      right=Leaf}), 
     Int.compare, 
     3); 
*) 

당신이 검색의 부모 및 조부모 노드를 반환하는 함수를 원하기 때문에, 당신은 다음의 튜플 반환하는 함수가 필요 :의 (검색 노드, 부모를 검색 노드, 검색 노드의 조부모). 그러나 부모님이나 조부모가 항상있는 것은 아닙니다. 예를 들어 찾고있는 키가 이미 기본 트리의 루트에있는 경우 부모 나 조부모가 없습니다. 따라서 option 유형을 사용해야합니다. 이렇게하면 해당 검색에 대한 상위 노드가없는 경우 NONE을 부모 노드로 반환하는 데 도움이됩니다. 이제 (메인 트리, NONE, NONE)를 사용하여 검색을 시작한 다음 트리를 따라 이동하면서 부모 노드를 오른쪽으로 이동하면됩니다. 키를 찾지 못하면 NONE의 세 쌍을 반환하십시오.

(*searchParent(tree, compare, key) = 
    (t, the parent of t, the grandparent of t) 
    where t = the tree which has `key` as its root 
    *) 
fun searchParent(tree : 'a bst, compare : ('a * 'a -> order), key : 'a) 
       : ('a bst option * 'a bst option * 'a bst option) = 
    let 
    fun s(tree: 'a bst, par: 'a bst option, gpar: 'a bst option) 
     : ('a bst option * 'a bst option * 'a bst option) = 
     case tree of 
     Leaf => (NONE, NONE, NONE) 
     | Node({data=x, left=l, right=r}) => 
      case compare(key,x) of 
      LESS => s(l, SOME tree, par) 
      | GREATER => s(r, SOME tree, par) 
      | EQUAL => (SOME tree, par, gpar) 
    in 
     s(tree, NONE, NONE) 
    end 

(*Example: 
searchParent(Node({data=5, 
      left=Node({data=3, 
         left=Node({data=2,left=Leaf,right=Leaf}), 
         right=Node({data=4,left=Leaf,right=Leaf})}), 
      right=Leaf}), 
     Int.compare, 
     4); 
*) 

내가 도울 수있는 희망 : 여기에 대한 코드입니다. 이 문제 또는 코드에 대해 다른 질문이 있으면 물어보십시오.

Answer 2

joom의 답변으로는 충분하지만 아마도 약간 자세한 정보가 있습니다. 문제에 대한보다 짧은 해석과 답을 쓰려는 시도가 있습니다. BST와 요소 x을 사용하면 두 요소가있는 경우 (SOME parent, SOME grandparent)을 찾습니다. 내가 사용

전략은 이것이다 : 재귀 호출 될 때마다 바로 이전의 부모로 방문 grandparent 된 요소로 기록 parent. EQUAL에서 x까지 요소가 발견되면 현재 사용 가능한 (parent, grandparent)을 반환합니다.

이 두 개의 추가 변수는 원래 검색 기능의 서명의 일부가 아닌, 내가 그들을되고 싶지 않기 때문에, 로컬 기능 helper이 이루어지기 때문에.

datatype 'a bst = Node of 'a * 'a bst * 'a bst 
       | Leaf 

fun search (initTree, compare, x) = 
    let fun helper (tree, parent, grandparent) = 
      case tree of 
       Leaf   => (NONE, NONE) 
      | Node (y, L, R) => case compare (x, y) of 
            LESS => helper (L, SOME y, parent) 
            | GREATER => helper (R, SOME y, parent) 
            | EQUAL => (parent, grandparent) 

    in helper (initTree, NONE, NONE) end 

테스트 다음 BST 사용하여이 기능 :

- search (t, Int.compare, 2); 
> val it = (SOME 3, SOME 5) : int option * int option 
- search (t, Int.compare, 3); 
> val it = (SOME 5, NONE) : int option * int option 

불행하게도,이 기능이 요소가 루트에서 발견되었는지 여부를 알 수 없습니다 :

val t = Node (5, Node (3, Node (2, Leaf, Leaf), 
          Node (4, Leaf, Leaf)), 
       Node (7, Node (6, Leaf, Leaf), 
          Node (8, Leaf, Leaf))) 

우리는 예상 된 결과를 참조 또는 BST의 존재하지 않았다. 두 경우 모두 (NONE, NONE)이 리턴되기 때문입니다.