Pythonで二分探索木を実装する方法は何ですか-Python チュートリアル-php.cn

Pythonで二分探索木を実装する方法は何ですか

WBOY

リリース： 2023-05-11 08:40:13

転載

1252 人が閲覧しました

ツリーの概要

ツリーは、リンクリストやハッシュテーブルとは異なり、非線形データ構造です。ツリーは、二分木、二分探索木、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

ログイン後にコピー

2. リストの実装を使用します

リストを使用して二分探索ツリーの要素を格納し、位置指定による挿入、検索、および削除を実装します。リスト内の要素の関係操作を待ちます。コード例は次のとおりです:

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

ログイン後にコピー

3. 辞書を使用して実装します

辞書のキーはノード値を表し、辞書の値は左と左を含む辞書です。右側の子ノード。コード例は次のとおりです。

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