Python で二分探索ツリーを実装する方法

Binary Search Tree (BST) は、バイナリ ツリーに基づく検索アルゴリズムです。その特徴は、ツリー内の各ノードの左側のサブツリーの値がこのノードの値より小さく、右側のサブツリーの値がこのノードの値より大きいことです。したがって、BST の検索および挿入操作の時間計算量は O(logN) です。

Python でバイナリ検索ツリーを実装する方法は比較的簡単です。Python にはリストと辞書という 2 つの組み込みデータ構造があり、どちらもバイナリ ツリーの実装に使用できるからです。ここではリストを使った二分探索木を実装する方法を説明します。

まず、各ノードの値、左のサブツリーと右のサブツリーを表す Node クラスを定義する必要があります。

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

次に、2 つの二分探索 Tree クラスを定義できます。メソッド: 挿入と検索。挿入方法では、ルート ノードから開始してノードの値を 1 つずつ比較し、新しく挿入された値が現在のノードの値より小さい場合は左側のサブツリーで検索を続け、そうでない場合は検索を続けます。右側のサブツリーにあります。ノードの左側 (または右側) のサブツリーが空であることが判明した場合は、挿入されるノードをこの位置に配置する必要があることを意味します。

class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self, value):
        new_node = Node(value)
        if self.root is None:
            self.root = new_node
        else:
            current_node = self.root
            while True:
                if value <= current_node.value:
                    if current_node.left is None:
                        current_node.left = new_node
                        break
                    else:
                        current_node = current_node.left
                else:
                    if current_node.right is None:
                        current_node.right = new_node
                        break
                    else:
                        current_node = current_node.right
    
    def search(self, value):
        current_node = self.root
        while current_node is not None:
            if value == current_node.value:
                return True
            elif value < current_node.value:
                current_node = current_node.left
            else:
                current_node = current_node.right
        return False

これで、ツリーを作成して複数のノードを挿入し、検索関数をテストできます:

bst = BinarySearchTree()
bst.insert(9)
bst.insert(3)
bst.insert(12)
bst.insert(1)
bst.insert(4)
bst.insert(10)
bst.insert(15)

print(bst.search(4))  # True
print(bst.search(7))  # False

この二分探索ツリーでは、 4 を検索すると、 が返されることがわかります。 True; 7 を検索すると、7 がツリーにないことを示す False が返されます。

二分探索木を実装するときは、いくつかの問題に注意する必要があります。まず、挿入操作と検索操作の時間計算量はツリーの高さに依存するため、実際の操作ではツリーの高さをできるだけ低く保つことが非常に重要です。第 2 に、大規模なデータ セットの場合、二分探索ツリーのバランスが崩れ (つまり、ツリーというよりリストに近くなり)、検索が遅くなる可能性があるため、バランスのとれた二分探索ツリーなどのより高度なアルゴリズムが必要となり、パフォーマンスを最適化します。

以上がPython で二分探索ツリーを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。