이진 탐색 트리에서 노드 삭제

Deletion in Binary Search Tree

정책

2분 탐색 트리로부터 있는 노드를 삭제하고 싶은 경우, 아래의 3개의 패턴으로 나누어 생각합니다.

삭제 대상의 노드가 아이를 가지지 않는다

삭제 대상의 노드가 1 개의 아이를 가지는

삭제 대상의 노드가 2 개의 아이를 가지는

1의 경우는 단순히 삭제 대상의 노드를 null로 옮겨놓으면 되고, 2의 경우는 삭제 대상의 노드를 그 아이로 옮겨놓으면 됩니다. 3의 경우는 처리가 다소 복잡해져 삭제 대상의 노드를 중간순서열(in-order)로 다음에 오는 노드(successor)의 값으로 덧쓰기한 다음, 원래의 successor를 삭제할 필요가 있습니다. 구체적인 구현 예를 아래에 나타냅니다.

구현 예

    # 二分木のノードを表すクラス
    class TreeNode:
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None

    # 二分探索木rootからkeyの値を持つノードを削除する
    def deleteNode(self, root, key):
        if root is None:
            return None

        if key < root.val:
            # 削除対象が自身より小さければ、左部分木から削除する
            root.left = self.deleteNode(root.left, key)
        elif key > root.val:
            # 削除対象が自身より大きければ、右部分木から削除する
            root.right = self.deleteNode(root.right, key)
        # 削除対象が自身と等しければ、自身を削除する
        else:
            # 子を持たない場合、自身をnullで置き換える
            if root.left is None and root.right is None:
                root = None
            # 1つの子を持つ場合、自身をその子で置き換える
            elif root.left is None or root.right is None:
                root = root.left or root.right            
            else:
                # 2つの子を持つ場合、自身をそのsuccessorの値で上書きし、元のsuccessorを削除する
                root.val = self.successor(root)
                root.right = self.deleteNode(root.right, root.val)

        return root

    # nodeの右部分木からsuccessorの値を返す
    def successor(self, node):
        node = node.right
        while node.left:
            node = node.left
        return node.val

보충

중간 순서 배열(in-order)에 있어서의 자신의 successor는, 자신이 오른쪽 부분 트리를 가지는 경우는 반드시 그 오른쪽 부분 트리내에 존재합니다. 구현예내의 successor 메소드는, 인수의 node 가 오른쪽 부분 트리를 가지는 경우에게만 사용되는 것을 상정하고 있습니다.

참고