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

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

2-3-4树是一种平衡树，也称为多路查找树。它的特点是每个节点可以存储两条、三条或四条数据和三个、四个或五个子节点，使得树保持平衡。以下是该数据结构的详细介绍和代码演示实现。

2-3-4树定义：

节点包含k-1个数据和k个子节点，其中2 <= k <= 4，且k为偶数。
节点的数据必须按顺序排列。（如二叉搜索树中的节点）
所有叶子节点必须在同一层，即具有相同深度。
非叶子节点包含的数据与子节点数维持以下规则：
若包含一条数据，则有两个子节点。
若包含两条数据，则有三个子节点。
若包含三条数据，则有四个子节点。

2-3-4树的插入操作：

将数据插到叶子节点上。如果插入之后，节点达到了四条数据，则需要进行分裂操作。
若该节点为根节点，则直接分裂，新根节点为原节点的中间元素，左右子节点为原节点的两半。
否则，将原节点中间元素上移至父节点，若父节点已有四个数据，则递归进行分裂操作。
递归寻找插入位置时，遇到满子节点也需要进行分裂操作，直到到达叶子节点。

2-3-4树的删除操作：

删除节点时，若该节点不是叶子节点，则用它的后继节点的值替换，然后删除后继节点。
在叶子节点中删除该值，如果该节点元素的数量少于2，则考虑以下情况：
如果一个兄弟节点有一个额外的字符，则转移一个字符以保持平衡。
如果所有的兄弟节点仅包含2个字符，则删除一个元素并合并为一个节点。
如果父节点仅包含2个元素，则可以将一个兄弟节点合并到父节点中。

Python代码演示实现：

class Node:
    # 2-3-4树的节点类

    def __init__(self):
        self.data = []  # 该节点包含的数据
        self.child = []  # 该节点的子节点

    def is_leaf(self):
        # 是否为叶子节点
        return not self.child

    def is_full(self):
        # 是否已满
        return len(self.data) >= 3

    def insert_data(self, value):
        # 插入值

        # 插入数据并排序
        self.data.append(value)
        self.data.sort()

        # 若该节点满了，则进行分裂操作
        if self.is_full():
            return self.split()

        return None

    def split(self):
        if not self.is_full():
            return None

        # 新建一个节点，作为当前节点的右兄弟节点
        right = Node()

        # 移动两个最大的值（中间值和最大值）到右节点
        right.data = self.data[2:]
        right.child = self.child[2:]

        # 新构建一个节点，作为新子节点，新子节点包括原来节点最小值的子节点
        new_node = Node()
        new_node.data.append(self.data[1])
        new_node.child.append(self.child[0])
        new_node.child.append(self.child[1])

        # 删除当前节点的最大值和中间值，并将右节点挂在新父节点上
        del self.data[1:]
        del self.child[1:]
        self.child.append(new_node)
        self.child.append(right)

        return self


class Tree234:
    # 2-3-4树类

    def __init__(self):
        self.root = Node()  # 根节点

    def insert(self, value):
        # 插入节点

        # 获取根节点
        node = self.root

        # 寻找插入点
        while True:
            # 遍历孩子节点
            i = len(node.data) - 1
            while i >= 0 and value < node.data[i]:
                i -= 1

            # 若找到了插入位置，则插入
            if node.is_leaf():
                return node.insert_data(value)

            # 若未找到插入位置，则移到孩子节点
            child = node.child[i + 1]
            if child.is_full():
                node.split()
                if value > node.data[-1]:
                    child = node.child[-1]
                else:
                    child = node.child[i]

            node = child

    def search(self, value):
        # 查找值是否存在

        # 获取根节点
        node = self.root

        # 遍历节点，直到找到叶子节点
        while node:
            # 遍历节点中的数据，查找目标值
            for x in node.data:
                if value == x:
                    return True
                elif value < x:
                    break

            # 找到对应的孩子节点，继续遍历
            if node.is_leaf():
                return False
            else:
                i = 0
                while i < len(node.data) and value > node.data[i]:
                    i += 1
                node = node.child[i]

        return False


def test_tree():
    tree = Tree234()

    # 插入值
    for value in ["pandabuy", "pandabuyit", "pandabuymore", "pandabuyabc", "python"]:
        tree.insert(value)

    # 查找值
    assert tree.search("pandabuy") == True
    assert tree.search("pandabuyit") == True
    assert tree.search("pandabuymore") == True
    assert tree.search("pandabuyabc") == True
    assert tree.search("python") == True
    assert tree.search("pandabu") == False
    assert tree.search("java") == False

test_tree()  # 运行测试

相关文章