Treap树从零实现（Python Treap树实现与平衡二叉搜索树入门教程）

什么是 Treap？

Treap 是一种平衡二叉搜索树，每个节点包含两个值：

• key（键）：用于维持二叉搜索树的性质（左子树 < 根 < 右子树）
• priority（优先级）：一个随机生成的数值，用于维持最大堆性质（父节点优先级 ≥ 子节点）

通过这种双重约束，Treap 在插入时自动“旋转”调整结构，从而保持平衡。这也是为什么 Treap 被称为随机化二叉搜索树。

Python 实现 Treap 节点类

首先，我们定义一个 TreapNode 类：

import randomclass TreapNode:    def __init__(self, key):        self.key = key        self.priority = random.randint(1, 1000000)  # 随机优先级        self.left = None        self.right = None

旋转操作：左旋与右旋

为了维持堆性质，我们需要实现两种基本旋转操作：

def rotate_right(y):    x = y.left    T2 = x.right        # 执行旋转    x.right = y    y.left = T2        return x  # 新的根节点def rotate_left(x):    y = x.right    T2 = y.left        # 执行旋转    y.left = x    x.right = T2        return y  # 新的根节点

插入操作

插入遵循 BST 规则，但插入后若违反堆性质，则通过旋转修复：

def insert(root, key):    # 步骤1：执行标准 BST 插入    if not root:        return TreapNode(key)        if key < root.key:        root.left = insert(root.left, key)        # 若左子节点优先级更高，右旋        if root.left.priority > root.priority:            root = rotate_right(root)    else:        root.right = insert(root.right, key)        # 若右子节点优先级更高，左旋        if root.right.priority > root.priority:            root = rotate_left(root)        return root

完整 Treap 类封装

我们将上述函数封装成一个完整的 Treap 类，方便使用：

class Treap:    def __init__(self):        self.root = None        def _rotate_right(self, y):        x = y.left        T2 = x.right        x.right = y        y.left = T2        return x        def _rotate_left(self, x):        y = x.right        T2 = y.left        y.left = x        x.right = T2        return y        def _insert(self, node, key):        if not node:            return TreapNode(key)                if key < node.key:            node.left = self._insert(node.left, key)            if node.left.priority > node.priority:                node = self._rotate_right(node)        else:            node.right = self._insert(node.right, key)            if node.right.priority > node.priority:                node = self._rotate_left(node)                return node        def insert(self, key):        self.root = self._insert(self.root, key)        def _inorder(self, node, result):        if node:            self._inorder(node.left, result)            result.append(node.key)            self._inorder(node.right, result)        def inorder(self):        result = []        self._inorder(self.root, result)        return result

使用示例

# 创建 Treaptreap = Treap()# 插入数据keys = [10, 20, 5, 15, 1]for k in keys:    treap.insert(k)# 中序遍历（应为有序）print("中序遍历结果:", treap.inorder())# 输出: 中序遍历结果: [1, 5, 10, 15, 20]

为什么选择 Treap？

相比 AVL 树或红黑树，Treap 的实现更简单，且通过随机化保证了良好的平均性能。它是学习平衡二叉搜索树和随机化算法的理想入门数据结构。

掌握 Python Treap树实现 不仅能加深你对树结构的理解，还能为你后续学习更复杂的算法打下坚实基础。

总结

本文详细讲解了 Treap 的原理，并提供了完整的 Python 实现代码。无论你是算法初学者，还是想巩固数据结构知识，这个随机化二叉搜索树的实现都能帮助你提升编程能力。

现在，你可以尝试扩展功能，比如实现删除、查找、范围查询等操作，进一步探索 Treap 的强大之处！