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 サイトの他の関連記事を参照してください。