이진 탐색 트리의 삭제 (Remove of Binary Search Trees)

이진 트리의 삭제 조건

이진 트리의 remove는 3가지 조건을 따로 살펴보아야한다.

• 삭제되는 노드가
  1. 말단(leaf) 노드인 경우
  2. 자식을 하나만 가지고 있는 경우
  3. 자식을 둘 가지고 있는 경우

1. 말단(leaf) 노드인 경우

말단 노드가 위치하는 부모노드의 참조를 (left or right) None으로 변경해주기만 하면됨.

즉, 말단 노드가 왼쪽에 있는지 오른쪽에 있는지 확인 후 부모 노드의 참조값만 None으로 변경.

2. 자식을 하나만 가지고 있는 경우

삭제되는 노드 자리에 그 자식을 대신 배치

즉, 자식이 왼쪽에 있는지 오른쪽에 있는지 확인 후 부모 노드에 자식을 배치

3. 자식을 둘 가지고 있는 경우

1. 삭제되는 노드(A)보다 바로 다음 큰 key를 가지는 노드(B)를 찾는다.
2. 삭제하고자 하는 노드(A)와 key를 가지는 노드(B)를 대체한다. (A→B)
3. B가 대체되고 남은 자리에 B의 오른쪽 노드로 채운다. (B.right)
   
   
   

자식 둘을 가지고 있는 경우 삭제

결과

실습

• 3번 자식을 둘 가지고 있는 경우 코드만 추출

parent = node
successor = node.right
# parent 는 node 를 가리키고 있고,
# successor 는 node 의 오른쪽 자식을 가리키고 있으므로
# successor 로부터 왼쪽 자식의 링크를 반복하여 따라감으로써
# 순환문이 종료할 때 successor 는 바로 다음 키를 가진 노드를,
# 그리고 parent 는 그 노드의 부모 노드를 가리키도록 찾아낸다.
while successor.left:
    parent = successor
    successor =  successor.left

# 삭제하려는 노드인 node 에 successor 의 key 와 data 를 대입.
node.key = successor.key
node.data = successor.data
# 이제, successor 가 parent 의 왼쪽 자식인지 오른쪽 자식인지를 판단
# 그에 따라 parent.left 또는 parent.right 를
# successor 가 가지고 있던 (없을 수도 있지만) 자식을 가리키도록 합니다
if parent:
    if(parent.key == successor):
        parent.left = successor.right

    #오직 한가지의 경우, 즉 찾으려고하는 노드가 while문을 돌지 않고 루트 노드의 successor = node.right로 설정 후 그것을 찾는 경우임. 
    elif(parent.right == successor):
        parent.right = successor.right

1. 실수 정리

• 실수 코드

if parent:
    if(parent.key > successor.key):
        parent.left = successor.right

    #오직 한가지의 경우, 즉 찾으려고하는 노드가 while문을 돌지 않고 루트 노드의 successor = node.right로 설정 후 그것을 찾는 경우임. 
    elif(parent.key < successor.key):
        parent.right = successor.right

• 왜 parent와 successor의 키값을 연산자로 비교하면 안되는 걸까?

   10
     \\
      15
     /
    12

위와 같은 예시를 들 수 있다. 10을 삭제하고자 했을 때 12는 부모 노드의 오른쪽에 있지만 나의 실수코드로는 왼쪽이라고 판단할 것이다.

따라서 아래와 같이 참조값을 이용해야한다.

if parent.left == successor:
    parent.left = successor.right
elif parent.right == successor:
    parent.right = successor.right

즉 한가지의 경우, 찾으려고하는 노드가 while문을 돌지 않고 루트 노드의 successor = node.right로 설정 후 그것을 찾을 때는 참조값을 이용해야하며 parent.right와 successor를 비교해야만 한다..