Help us understand the problem. What is going on with this article?

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

Deletion in Binary Search Tree

方針

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

  1. 削除対象のノードが子を持たない
  2. 削除対象のノードが1つの子を持つ
  3. 削除対象のノードが2つの子を持つ

Screen Shot 2019-10-14 at 10.48.50.png

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が右部分木を持つ場合にのみ使われることを想定しています。

参考

https://ja.wikipedia.org/wiki/二分探索木

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away