ツリーは、リンク リストやハッシュ テーブルとは異なり、非線形データ構造です。ツリーは、二分木、二分探索木、B ツリー、B ツリー、赤黒の木など。
ツリーはデータ構造であり、n 個の限定されたノードで構成される階層関係の集合です。これを絵で表すと、木が逆さまになったように見えることがわかります。したがって、このタイプのデータ構造を総称してツリーと呼び、根が上部にあり、葉が下部にあります。一般的なツリーには次の特徴があります。
各ノードには 0 個以上の子ノードがあります。
親ノードのないノードはルートと呼ばれます。ノード
各非ルート ノードには親ノードが 1 つだけあります
各子ノードは複数の互いに素な子ツリーに分割できます
バイナリ ツリーの定義は次のとおりです。各ノードには最大 2 つの子ノードがあります。つまり、各ノードでは次の 4 つの状況のみが発生します。
左のサブツリーと右のサブツリーの両方が空である
左のサブツリーのみサブツリーが存在します ツリー
右のサブツリーのみが存在します
左のサブツリーと右のサブツリーの両方が存在します
バイナリ検索ツリーはバイナリ ソート ツリーとも呼ばれ、空のツリーまたは次のプロパティを持つバイナリ ツリーのいずれかです。左のサブツリーが空でない場合、左のサブツリー上のすべてのノードの値はルート ノードの値より小さくなります。右のサブツリーが空でない場合、右のサブツリー上のすべてのノードの値は大きくなります。
その左側と右側のサブツリーもそれぞれ二分探索ツリーです
Python での一般的な実装方法をいくつかリストします:
class Node: def __init__(self, data): self.data = data self.left = None self.right = None class BST: def __init__(self): self.root = None def insert(self, value): if self.root is None: self.root = Node(value) else: self._insert(value, self.root) def _insert(self, value, node): if value < node.data: if node.left is None: node.left = Node(value) else: self._insert(value, node.left) elif value > node.data: if node.right is None: node.right = Node(value) else: self._insert(value, node.right) def search(self, value): if self.root is None: return False else: return self._search(value, self.root) def _search(self, value, node): if node is None: return False elif node.data == value: return True elif value < node.data: return self._search(value, node.left) else: return self._search(value, node.right) def delete(self, value): if self.root is None: return False else: self.root = self._delete(value, self.root) def _delete(self, value, node): if node is None: return node elif value < node.data: node.left = self._delete(value, node.left) elif value > node.data: node.right = self._delete(value, node.right) else: if node.left is None and node.right is None: del node return None elif node.left is None: temp = node.right del node return temp elif node.right is None: temp = node.left del node return temp else: temp = self._find_min(node.right) node.data = temp.data node.right = self._delete(temp.data, node.right) return node def _find_min(self, node): while node.left is not None: node = node.left return node
リストを使用して二分探索ツリーの要素を格納し、位置指定による挿入、検索、および削除を実装します。リスト内の要素の関係 操作を待ちます。コード例は次のとおりです:
class BST: def __init__(self): self.values = [] def insert(self, value): if len(self.values) == 0: self.values.append(value) else: self._insert(value, 0) def _insert(self, value, index): if value < self.values[index]: left_child_index = 2 * index + 1 if left_child_index >= len(self.values): self.values.extend([None] * (left_child_index - len(self.values) + 1)) if self.values[left_child_index] is None: self.values[left_child_index] = value else: self._insert(value, left_child_index) else: right_child_index = 2 * index + 2 if right_child_index >= len(self.values): self.values.extend([None] * (right_child_index - len(self.values) + 1)) if self.values[right_child_index] is None: self.values[right_child_index] = value else: self._insert(value, right_child_index) def search(self, value): if value in self.values: return True else: return False def delete(self, value): if value not in self.values: return False else: index = self.values.index(value) self._delete(index) return True def _delete(self, index): left_child_index = 2 * index + 1 right_child_index = 2 * index + 2 if left_child_index < len(self.values) and self.values[left_child_index] is not None: self._delete(left_child_index) if right_child_index < len(self.values) and self.values[right_child_index] is not None: self
辞書のキーはノード値を表し、辞書の値は左と左を含む辞書です。右側の子ノード。コード例は次のとおりです。
def insert(tree, value): if not tree: return {value: {}} elif value < list(tree.keys())[0]: tree[list(tree.keys())[0]] = insert(tree[list(tree.keys())[0]], value) else: tree[list(tree.keys())[0]][value] = {} return tree def search(tree, value): if not tree: return False elif list(tree.keys())[0] == value: return True elif value < list(tree.keys())[0]: return search(tree[list(tree.keys())[0]], value) else: return search(tree[list(tree.keys())[0]].get(value), value) def delete(tree, value): if not search(tree, value): return False else: if list(tree.keys())[0] == value: if not tree[list(tree.keys())[0]]: del tree[list(tree.keys())[0]] elif len(tree[list(tree.keys())[0]]) == 1: tree[list(tree.keys())[0]] = list(tree[list(tree.keys())[0]].values())[0] else: min_key = min(list(tree[list(tree.keys())[0]+1].keys())) tree[min_key] = tree[list(tree.keys())[0]+1][min_key] tree[min_key][list(tree.keys())[0]] = tree[list(tree.keys())[0]] del tree[list(tree.keys())[0]] elif value < list(tree.keys())[0]: tree[list(tree.keys())[0]] = delete(tree[list(tree.keys())[0]], value) else: tree[list(tree.keys())[0]][value] = delete(tree[list(tree.keys())[0]].get(value), value) return tree
4. スタックを使用した実装
スタック (Stack) を使用すると、単純な二分探索ツリーを実装でき、反復によって挿入、検索、削除などの操作を実装できます。具体的な実装プロセスは次のとおりです。
ノード値、左右のサブノード、その他の属性を含むノード クラスを定義します。
スタックを定義し、最初にルート ノードをスタックにプッシュします。
スタックが空でない場合は、スタックの最上位要素を取り出して操作します。挿入する値が現在のノード値より小さい場合は、その値をノードに挿入します。左の子ノードとして挿入され、左の子ノードをスタックにプッシュします。挿入される値が現在のノード値より大きい場合は、挿入される値を右の子ノードとして挿入し、右の子ノードをプッシュします。スタックに追加し、検索または削除する値が現在のノード値と等しい場合は、ノードを返すか削除します。
操作が完了したら、スタックから次のノードを取得し、スタックが空になるまで操作を続けます。
この実装では、ツリーを走査するプロセスを保存するためにスタックが使用されるため、メモリ使用量が高くなる可能性があることに注意してください。さらに、スタックの特性により、この実装は深さ優先探索 (深さ優先検索、DFS) のみをサポートし、幅優先検索 (BFS) をサポートできません。
class Node: def __init__(self, data): self.data = data self.left = None self.right = None def insert(root, value): if not root: return Node(value) stack = [root] while stack: node = stack.pop() if value < node.data: if node.left is None: node.left = Node(value) break else: stack.append(node.left) elif value > node.data: if node.right is None: node.right = Node(value) break else: stack.append(node.right) def search(root, value): stack = [root] while stack: node = stack.pop() if node.data == value: return True elif value < node.data and node.left: stack.append(node.left) elif value > node.data and node.right: stack.append(node.right) return False def delete(root, value): if root is None: return None if value < root.data: root.left = delete(root.left, value) elif value > root.data: root.right = delete(root.right, value) else: if root.left is None: temp = root.right del root return temp elif root.right is None: temp = root.left del root return temp else: temp = root.right while temp.left is not None: temp = temp.left root.data = temp.data root.right = delete(root.right, temp.data) return root
以上がPythonで二分探索木を実装する方法は何ですかの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。