二分探索木の基本操作（挿入、削除、探索）

二分探索木（Binary Search Tree, BST）は、ノードが左の子ノードよりも小さく、右の子ノードよりも大きいという特性を持つデータ構造です。この特性により、探索、挿入、削除の操作が効率良く行えます。この教材では、二分探索木の基本操作である挿入、削除、探索について学びます。

二分探索木の構造

まず、二分探索木を表すためのノードクラスを定義します。

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

このクラスは、各ノードが持つ値（val）、左の子ノード（left）、右の子ノード（right）を表します。

挿入操作

次に、二分探索木にノードを挿入するための関数を実装します。

def insert(root, key):
    if root is None:
        return Node(key)
    else:
        if key < root.val:
            root.left = insert(root.left, key)
        else:
            root.right = insert(root.right, key)
    return root

解説

• rootがNoneの場合、新しいノードを作成して返します。
• keyが現在のノードの値より小さい場合、左の子ノードに挿入します。
• それ以外の場合は、右の子ノードに挿入します。

探索操作

次に、二分探索木から特定の値を探索する関数を実装します。

def search(root, key):
    if root is None or root.val == key:
        return root
    if key < root.val:
        return search(root.left, key)
    return search(root.right, key)

解説

• rootがNoneまたはroot.valがkeyと等しい場合、ノードを返します。
• keyが現在のノードの値より小さい場合は、左の子ノードを探索します。
• それ以外の場合は、右の子ノードを探索します。

削除操作

最後に、二分探索木からノードを削除するための関数を実装します。

def delete_node(root, key):
    if root is None:
        return root

    if key < root.val:
        root.left = delete_node(root.left, key)
    elif key > root.val:
        root.right = delete_node(root.right, key)
    else:
        # ノードが見つかった場合
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left

        # 両方の子が存在する場合
        min_larger_node = find_min(root.right)
        root.val = min_larger_node.val
        root.right = delete_node(root.right, min_larger_node.val)

    return root

def find_min(node):
    current = node
    while current.left is not None:
        current = current.left
    return current

解説

• 削除するノードが見つかるまで、探索と同様の方法で木を辿ります。
• ノードが見つかった場合、以下の3つのケースを処理します：
• 左の子ノードがない場合：右の子ノードを返します。
• 右の子ノードがない場合：左の子ノードを返します。
• 両方の子ノードが存在する場合：右部分木の中で最小のノードを見つけ、その値で削除したノードの値を置き換えます。

使い方の例

これまでの関数を使って、二分探索木を操作する例を示します。

if __name__ == "__main__":
    root = None
    keys = [20, 30, 10, 5, 15, 25, 35]

    # ノードの挿入
    for key in keys:
        root = insert(root, key)

    # ノードの探索
    search_key = 15
    found_node = search(root, search_key)
    if found_node:
        print(f"Node with key {search_key} found.")
    else:
        print(f"Node with key {search_key} not found.")

    # ノードの削除
    root = delete_node(root, 20)
    print("Node with key 20 deleted.")

解説

• 最初に、いくつかのキーを持つ二分探索木を作成します。
• 次に、特定のキーを探索し、結果を表示します。
• 最後に、特定のキーを持つノードを削除します。

これで、二分探索木の基本操作（挿入、削除、探索）についての解説は完了です。これらの基本操作を理解することで、データ構造の効率的な運用が可能となります。