수정 된 이진 검색 트리에서 검색, 삽입 및 삭제

Question

이진 탐색 트리 x의 각 노드가 x.parent 대신 x.successor를 유지한다고 가정 해보십시오. O (h)에서 작동하는 의사 코드를 사용하여 검색, 삽입 및 삭제 알고리즘을 설명하십시오. 여기서 h는 트리의 높이입니다. 지금까지 검색을위한 간단한 이진 검색 트리 알고리즘이 적용됩니다.

TREE-SEARCH(x, k) 
if x == NIL or k == x.key 
    return x 
if k < x.key 
    return TREE-SEARCH(x.left, k) 
else return TREE-SEARCH(x.right, k) 

이 알고리즘은 수정에 영향을받지 않아야하며 O (h) 시간에 명확하게 실행되어야합니다. 그러나 삽입 및 삭제 알고리즘의 경우 수정이이를 수행하는 간단한 방법을 변경합니다. 예를 들어, 다음

TREE-INSERT(T,z) 
y = NIL 
x = T.root 
while x =/= NIL 
    y = x 
    if z.key < x.key 
     x = x.left 
    else x = x.right 
z.p = y 
if y == NIL 
    T.root = z //Tree T was empty 
elseif z.key < y.key 
    y.left = z 
else y.right = z 

은 분명히 우리가 때문에 이진 검색 트리에 대한 우리의 수정의 z.p 사용할 수 없습니다, T.

일반 이진 검색 트리를 사용하여 삽입하는 알고리즘이다. 부모를 찾는 서브 루틴을 구현하는 것이 제안되었지만 이것이 어떻게 수행되는지는 볼 수 없습니다.

Answer 1

검색은 삽입 동안, 우리가 새로 삽입 된 노드의 후계자를 원하는 답변

의 영향을받지

스케치 할 것이다. 정상적인 이진 검색 트리에서 후계 노드의 알고리즘을 알고있는 경우 리프 노드에서 후미 노드가 왼쪽 자식이 노드의 조상 인 첫 번째 조상임을 알 수 있습니다. 그래서 정상적인 삽입을하는 동안 우리가 따르는 왼쪽 자식 노드는 노드의 후속 노드가 될 것입니다. 이 삽입 경로에서 오른쪽 자식을 따르는 마지막 노드는 후속 노드가 현재 노드입니다.

x.successor에서 후속 노드에 대한 포인터를 저장하면 간단 해집니다. 삭제할 노드의 키를 후속 키로 바꾸고 node.successor 포인터를 후속 노드로 바꿉니다. 바늘. 키를 저장하는 중이면이 노드를 후속 노드로 사용하여 노드를 업데이트해야합니다. 후보자는 왼쪽 자식이있는 경우이 하위 트리의 맨 오른쪽 노드입니다. 그렇지 않으면 노드를 검색하면 오른쪽 하위 노드로 이동 한 마지막 노드가 필수 노드가됩니다.

다이어그램 그리는 방법을 모르겠다. 다이어그램에서 더 간단합니다.