二分探索木におけるノードの削除

Deletion in Binary Search Tree

方針

二分探索木からあるノードを削除したい場合、下記の3つのパターンに分けて考えます。

1. 削除対象のノードが子を持たない
2. 削除対象のノードが1つの子を持つ
3. 削除対象のノードが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が右部分木を持つ場合にのみ使われることを想定しています。

参考