Python中的树形数据结构: 2-3树

2023-04-11 00:00:00 python 数据结构

2-3树是一种平衡树，它可以用来存储有序的数据，并且支持快速查找、插入和删除操作。每个节点可以包含一个或两个关键字，同时可以有一个或两个子节点。如果一个节点包含一个关键字，那么它只有一个子节点；如果一个节点包含两个关键字，那么它有两个子节点。

2-3树满足以下性质：
1. 所有的叶子节点都在同一层上。
2. 每个节点可以包含一个或两个关键字。
3. 所有的关键字都按照顺序排列，并且每个关键字在它左侧的子树中的所有关键字都小于它，在它右侧子树中的所有关键字都大于它。
4. 所有节点的左子树和右子树的关键字数目都不相差超过1.

以下是一个Python实现的2-3树类：

class TwoThreeTree:
    class Node:
        def __init__(self, key1=None, key2=None, left=None, middle=None, right=None):
            self.keys = (key1, key2)
            self.children = (left, middle, right)

    def __init__(self):
        self.root = None

    def search(self, key):
        def search_helper(node):
            if not node:
                return False
            if key in node.keys:
                return True
            elif key < node.keys[0]:
                return search_helper(node.children[0])
            elif len(node.keys) == 1 or key < node.keys[1]:
                return search_helper(node.children[1])
            else:
                return search_helper(node.children[2])

        return search_helper(self.root)

    def insert(self, key):
        def insert_helper(node):
            if not node:  # Tree is empty
                self.root = self.Node(key)
            elif node.children[0] is None:  # Leaf node
                if len(node.keys) == 1:
                    if key < node.keys[0]:
                        node.keys = (key, node.keys[0])
                    else:
                        node.keys = (node.keys[0], key)
                else:  # Node has two keys
                    if key < node.keys[0]:
                        node.keys = (key, node.keys[0])
                        left = self.Node(node.keys[1])
                        right = self.Node(node.keys[2])
                    elif key < node.keys[1]:
                        left = self.Node(node.keys[0])
                        right = self.Node(node.keys[2])
                        node.keys = (node.keys[0], key)
                    else:
                        left = self.Node(node.keys[0])
                        right = self.Node(key)
                        node.keys = (node.keys[1], key)
                    node.children = (left, right, None)
            else:  # Internal node
                if key < node.keys[0]:
                    insert_helper(node.children[0])
                elif len(node.keys) == 1 or key < node.keys[1]:
                    insert_helper(node.children[1])
                else:
                    insert_helper(node.children[2])
                if node.children[2] is not None:  # Two keys in two children
                    left = self.Node(node.keys[0], None, node.children[0], node.children[1])
                    right = self.Node(node.keys[1], None, node.children[2], None)
                    node.keys = (node.keys[0], None)
                    node.children = (left, right, None)
                elif node.children[1].keys is None:  # Two keys in one child
                    if key < node.keys[0]:
                        node.children[1].keys = (node.keys[0], node.children[0].keys[1])
                        node.keys = (key, None)
                    else:
                        node.children[1].keys = (node.keys[0], node.keys[1])
                        node.keys = (node.keys[1], None)
                elif node.children[0].keys is None:  # Two keys in one child
                    if key < node.keys[0]:
                        node.children[0].keys = (key, node.keys[0])
                    else:
                        node.children[0].keys = (node.keys[0], key)
                    node.keys = (None, None)
                    node.children = (node.children[0], node.children[1], node.children[2])

        insert_helper(self.root)

以下是如何使用2-3树类的示例代码：

tree = TwoThreeTree()
tree.insert("pidancode.com")
tree.insert("皮蛋编程")
print(tree.search("pidancode.com"))  # True
print(tree.search("皮蛋编程"))  # True
print(tree.search("bilibili.com"))  # False

在这个示例中，我们使用2-3树类来存储字符串，然后使用insert()方法将“pidancode.com”和“皮蛋编程”插入到树中。接着我们使用search()方法查找这两个字符串，输出结果为True，说明它们确实存在于树中。最后我们又使用search()方法查找一个不存在的字符串“bilibili.com”，输出结果为False，说明它不在树中。

相关文章