别再死记硬背了！用Treap（树堆）搞定平衡树，从‘分裂’与‘合并’理解无旋式实现

从分裂与合并入手无旋Treap的实战指南在算法竞赛和数据结构学习中平衡二叉搜索树BST一直是让许多学习者头疼的难点。传统的旋转式平衡树如AVL树和红黑树虽然效率很高但其复杂的旋转操作和平衡条件往往让人望而生畏。今天我们将介绍一种更为直观、易于理解的平衡树实现——无旋Treap树堆它通过分裂split和合并merge这两个核心操作实现了BST的高效维护。1. Treap基础树与堆的完美结合TreapTree Heap是一种结合了二叉搜索树和堆特性的数据结构。每个节点除了存储键值key外还拥有一个随机生成的优先级priority。Treap需要同时满足以下两个性质二叉搜索树性质对于任意节点左子树所有节点的键值小于当前节点右子树所有节点的键值大于当前节点堆性质每个节点的优先级大于其子节点的优先级这种双重性质使得Treap在期望情况下能保持较好的平衡性。Treap主要分为两种实现方式旋转式Treap通过左旋和右旋操作维护平衡无旋Treap通过分裂和合并操作维护平衡class Node: def __init__(self, key): self.key key self.priority random.randint(1, 10**9) self.left None self.right None self.size 1 # 子树大小2. 无旋Treap的核心操作2.1 分裂Split分裂操作是无旋Treap的基础它能将一棵Treap按照给定的键值分成两棵子树左子树所有节点的键值小于等于分裂键值右子树所有节点的键值大于分裂键值分裂的实现思路如果当前树为空返回两个空树如果当前节点的键值小于等于分裂键值对右子树进行分裂将分裂得到的较小树作为当前节点的右子树否则对左子树进行分裂将分裂得到的较大树作为当前节点的左子树def split(root, key): if not root: return (None, None) if key root.key: left, root.left split(root.left, key) return (left, root) else: root.right, right split(root.right, key) return (root, right)2.2 合并Merge合并操作将两棵Treap合并为一棵前提是左树的所有键值都小于右树的所有键值。合并时根据节点的优先级决定谁成为新的根节点。合并的实现思路如果其中一棵树为空返回另一棵树比较两棵树根节点的优先级如果左树根节点优先级更高将右树合并到左树的右子树否则将左树合并到右树的左子树def merge(left, right): if not left or not right: return left or right if left.priority right.priority: left.right merge(left.right, right) return left else: right.left merge(left, right.left) return right3. 基于分裂与合并的常用操作3.1 插入操作插入一个新键值时按照插入键值将原树分裂为两部分创建新节点按顺序合并左树、新节点和右树def insert(root, key): left, right split(root, key) new_node Node(key) return merge(merge(left, new_node), right)3.2 删除操作删除一个键值时按照key-1将树分裂为左树和中间右树按照key将中间右树分裂为中间树和右树丢弃中间树即要删除的节点合并左树和右树def delete(root, key): left, right split(root, key - 1) _, right split(right, key) return merge(left, right)3.3 查询操作无旋Treap支持所有标准BST查询操作包括查找键值是否存在查询键值的排名查询某排名的键值查找前驱和后继def find_kth(root, k): while root: left_size root.left.size if root.left else 0 if k left_size: root root.left elif k left_size 1: return root.key else: k - left_size 1 root root.right return None4. 无旋Treap的进阶应用4.1 区间操作无旋Treap的一个显著优势是天然支持区间操作。例如要反转区间[l, r]按r分裂得到树A和树B对树A按l-1分裂得到树C和树D对树D中的区间节点打上反转标记按顺序合并树C、树D和树Bdef reverse_range(root, l, r): left, right split(root, r) left_left, to_reverse split(left, l - 1) to_reverse.reversed ^ True # 标记反转 return merge(merge(left_left, to_reverse), right)4.2 可持久化实现由于无旋Treap不使用旋转操作它在进行分裂和合并时只需要修改受影响路径上的节点这使得实现可持久化版本变得相对简单。只需在修改节点时创建新副本而非直接修改原节点。def persistent_insert(root, key): left, right split(root, key) new_node Node(key) return merge(merge(left, new_node), right)5. 性能分析与比较操作无旋Treap旋转式TreapAVL树红黑树插入O(log n)O(log n)O(log n)O(log n)删除O(log n)O(log n)O(log n)O(log n)查询O(log n)O(log n)O(log n)O(log n)区间操作支持不支持不支持不支持可持久化容易困难困难困难代码复杂度简单中等高高6. 实战案例洛谷P3369让我们以洛谷P3369模板题为例展示无旋Treap的完整实现。题目要求实现一个数据结构支持以下操作插入x数删除x数查询x数的排名查询排名为x的数求x的前驱求x的后继import random import sys class TreapNode: def __init__(self, key): self.key key self.priority random.randint(1, 10**9) self.left None self.right None self.size 1 def update_size(node): if node: node.size 1 (node.left.size if node.left else 0) (node.right.size if node.right else 0) def split(root, key): if not root: return (None, None) if key root.key: left, root.left split(root.left, key) update_size(root) return (left, root) else: root.right, right split(root.right, key) update_size(root) return (root, right) def merge(left, right): if not left or not right: return left or right if left.priority right.priority: left.right merge(left.right, right) update_size(left) return left else: right.left merge(left, right.left) update_size(right) return right def insert(root, key): left, right split(root, key) new_node TreapNode(key) return merge(merge(left, new_node), right) def delete(root, key): left, right split(root, key) left_left, to_delete split(left, key - 1) return merge(left_left, right) def get_rank(root, key): if not root: return 1 if key root.key: return get_rank(root.left, key) else: left_size root.left.size if root.left else 0 return left_size 1 get_rank(root.right, key) def get_kth(root, k): while root: left_size root.left.size if root.left else 0 if k left_size: root root.left elif k left_size 1: return root.key else: k - left_size 1 root root.right return None def get_predecessor(root, key): res None while root: if root.key key: res root.key root root.right else: root root.left return res def get_successor(root, key): res None while root: if root.key key: res root.key root root.left else: root root.right return res def main(): root None n int(sys.stdin.readline()) for _ in range(n): op, x map(int, sys.stdin.readline().split()) if op 1: root insert(root, x) elif op 2: root delete(root, x) elif op 3: print(get_rank(root, x)) elif op 4: print(get_kth(root, x)) elif op 5: print(get_predecessor(root, x)) elif op 6: print(get_successor(root, x)) if __name__ __main__: main()7. 调试与优化技巧在实际使用无旋Treap时以下几点可以帮助你更好地调试和优化代码可视化工具编写简单的打印函数以树形结构输出Treap便于直观检查结构是否正确优先级冲突处理当两个节点优先级相同时可以添加次要比较条件如节点键值确保确定性行为内存管理对于频繁插入删除的场景考虑实现节点池复用机制减少内存分配开销性能测试针对大规模数据测试各操作的实际耗时确保符合理论时间复杂度def print_tree(node, indent0): if node: print_tree(node.right, indent 4) print( * indent f{node.key}({node.priority})) print_tree(node.left, indent 4)无旋Treap以其简洁的实现和强大的功能成为了算法竞赛中平衡树的热门选择。相比传统旋转式平衡树它更易于理解和实现特别适合那些希望快速掌握平衡树核心思想的学习者。通过掌握分裂与合并这两个核心操作你不仅能实现基本的BST功能还能轻松扩展到区间操作等高级应用场景。