企业官网建设流程全解析

1. 从“二叉搜索树退化”说起：Treap 到底解决什么问题

1.1 普通 BST 的完美形态与退化根因

先聊一个几乎所有学数据结构的人都会遇到的困惑：明明二叉搜索树（BST）的查找、插入、删除理论上都是 O(log n)，怎么写出来一跑就是 O(n)？

原因其实不复杂。普通 BST 的性能依赖树的形状：如果每次插入的数据是随机的，树会自然长得比较匀称；但实际数据几乎不可能一直随机。比如按递增顺序插入 1、2、3……直到 n，树就会变成一条右斜链；按递减顺序插入则变成左斜链。这时查找第 n 个节点，要从根一路走到最底部，复杂度直接退化成线性。

训练集、日志时间戳、排行榜分数……这些场景的数据分布天然带有递增或递减趋势。我第一次在比赛里用裸 BST 处理有序数据时，直接超时到心态崩溃。当时甚至怀疑是自己代码写错了，反复检查才发现是树退化成链导致的。

所以平衡树的核心诉求就一句话：无论数据怎么进来，保持树高在 O(log n) 级别。业界经典方案是 AVL 树和红黑树，但它们都通过严格的旋转规则维护平衡条件，实现复杂度高，写起来很容易出错。尤其是 AVL 的四种旋转组合，初学时经常把 LL、RR、LR、RL 搞混。

那有没有一种方案，既不需要严格平衡，又能大概率保证树高是 O(log n)，而且实现起来足够简单？

有。就是 Treap。

1.2 树堆（Tree + Heap）的巧妙机制

Treap 这个名称是 Tree 和 Heap 的合成词，中文叫树堆。它的基本思路是：每个节点除了保存一个关键字 key，额外生成一个随机优先级 priority，然后同时满足两个性质：

• 二叉搜索树性质：左子树所有 key 小于当前节点 key，右子树所有 key 大于当前节点 key。
• 堆性质：每个节点的 priority 大于（或小于，看约定）它的左右子节点。

这里的堆性质只要求父节点与子节点之间满足大小关系，不要求整棵树是完全二叉树，所以它本质上是一棵“形态随机的二叉搜索树”。

为什么加一个随机优先级就能解决退化问题？因为堆性质限制了树的形态只能是无序的，而 priority 是随机分配的。当你要把某个节点放进去，BST 性质限定了它的左右位置，但怎样才能让树同时满足堆性质呢？通过旋转。

Treap 的旋转只有两种：左旋和右旋。这是它比 AVL 简单得多的根本原因：AVL 需要根据平衡因子判断转一次还是转两次，Treap 只需要对比父子 priority 是否颠倒即可。

我个人的理解是：Treap 把“平衡”这个全局问题转化成了“父子优先级”这个局部问题。你不需要关心整棵树的形状，只需要保证每一条边都符合堆性质，树自然就是平衡的。至于为什么随机优先级能带来期望 O(log n) 高度，可以把它理解为：在 n 个随机值里，根节点差不多是优先级最大的那个，它把剩下的序列划分成两半；而随机序列的最大值位置是均匀分布的，所以划分在期望意义上是均衡的。

1.3 为什么“随机”能让树变平衡

这个结论值得展开说。假设插入 n 个节点，每个节点的 priority 是独立随机生成的，那么 Treap 的高度期望是 O(log n)，最坏情况确实可能存在，但概率极低并且与输入数据无关。

关键在于，随机性来自 priority，而不是输入顺序。你完全可以按递增顺序插入一组数据，但每个节点进入时会被赋予一个随机 priority，然后通过旋转调整到合适位置。最终树的结构只由 priority 的顺序决定，而 priority 是随机的，所以树高也是随机的。当初我看到这个结论时觉得非常巧妙——传统 BST 的问题恰恰是“树的形状由输入顺序决定”，Treap 则彻底切断了这两者之间的必然联系。

当然，它也有代价：如果 priority 随机数生成质量差，比如用了固定的伪随机种子，或者干脆每次运行都用同一个种子，那树的形状可能会被稳定地控制住，进而退化。这个坑我在后面调试部分会单独展开。

2. 手把手拆解 Treap 的旋转、插入与删除

2.1 节点结构设计

写 Treap 之前先把节点定义清楚。我习惯用结构体加指针的方式，但在竞赛和工程里都推荐用数组模拟指针，因为动态 new 节点慢且容易造成内存碎片。

struct Node { int key; // 关键字 int prio; // 随机优先级 int size; // 子树大小（用于排名统计） Node *left; // 左孩子 Node *right; // 右孩子 Node(int k) : key(k), prio(rand()), size(1), left(nullptr), right(nullptr) {} };

如果你用数组模拟，可以这样写：

const int MAXN = 100005; int ch[MAXN][2]; // ch[x][0] 左孩子, ch[x][1] 右孩子 int key[MAXN], prio[MAXN], sz[MAXN], tot; int newNode(int k) { key[++tot] = k; prio[tot] = rand(); sz[tot] = 1; ch[tot][0] = ch[tot][1] = 0; return tot; }

这里优先级的生成必须依赖随机数。C 语言的 rand() 本身质量一般，实际使用时建议改成 mt19937，后面会详细说。

2.2 旋转操作的完整实现

旋转是 Treap 的灵魂操作。左旋的意思是：当前节点的右孩子上升到父节点位置，当前节点变成左孩子；右旋则完全对称。

为什么需要旋转？因为插入新节点时它可能违反了堆性质（子节点优先级大于父节点），这时就需要通过旋转把优先级高的节点“提上来”。

void zig(Node* &t) { // 右旋：t 的左孩子上升 Node* l = t->left; t->left = l->right; l->right = t; t = l; } void zag(Node* &t) { // 左旋：t 的右孩子上升 Node* r = t->right; t->right = r->left; r->left = t; t = r; }

注意这里参数是Node* &t，也就是指针的引用或双指针。原因是旋转后根节点变了，必须直接修改传入的指针本身，否则调用方还是指向旧根节点，整个树的根就丢了。我第一次写 Treap 时漏了引用符号，插入之后打印树发现根节点没变，调试了很久才发现是这个原因。

数组模拟版本也要注意类似问题，根节点编号在旋转后需要更新：

void rotate(int &t, int dir) { // dir = 0 表示右旋，dir = 1 表示左旋 int child = ch[t][dir]; ch[t][dir] = ch[child][dir ^ 1]; ch[child][dir ^ 1] = t; push_up(t); push_up(child); t = child; }

这里push_up用于更新子树大小，旋转之后两个节点的子树大小都变了，必须先更新原根，再更新新根，顺序不能反。

2.3 插入操作的递归写法和细节

插入的递归写法非常符合 Treap 的思维方式：先按 BST 规则找到插入位置，插入后如果子节点优先级大于当前节点，就旋转。

void insert(Node* &t, int k) { if (t == nullptr) { t = new Node(k); return; } if (k < t->key) { insert(t->left, k); if (t->left && t->left->prio > t->prio) { zig(t); // 优先级更高，右旋 } } else if (k > t->key) { insert(t->right, k); if (t->right && t->right->prio > t->prio) { zag(t); // 左旋 } } else { return; // 重复值按需求处理 } }

每次递归返回后判断是否需要旋转。旋转的方向取决于新节点插在哪一侧：插在左子树，子节点 priority 大于父节点就右旋；插在右子树就左旋。

有两点必须注意。第一，递归插入时，路径上的所有节点都可能因为孩子节点的变化而被旋转，所以旋转的判断必须在递归返回之后执行；第二，如果允许重复键，需要一个计数域 count。很多资料默认 Treap 不允许重复键，但实际场景（比如排行榜、频率统计）里重复值很常见。我的做法是加一个cnt字段表示相同键的数量，这样就不用把所有重复值都建成节点。

2.4 删除操作的三种情况

删除比插入稍微麻烦一点，但比 AVL 还是简单太多。核心思路是：如果当前节点就是要删的节点，不要直接删掉它，而是把它通过旋转降到叶子层，再安全删除。这样做的好处是不需要复杂的左右子树合并。

void erase(Node* &t, int k) { if (t == nullptr) return; if (k < t->key) { erase(t->left, k); } else if (k > t->key) { erase(t->right, k); } else { // 找到了要删除的节点 if (t->left && t->right) { // 两个孩子都还在，选择优先级高的孩子旋转上来 if (t->left->prio > t->right->prio) { zig(t); // 左孩子优先级高，右旋 erase(t->right, k); // 要删的节点换到了右子树 } else { zag(t); // 右孩子优先级高，左旋 erase(t->left, k); } } else { Node* tmp = t; t = (t->left ? t->left : t->right); delete tmp; } } if (t) push_up(t); }

删除的过程本质上是“把孩子中优先级较高的那个旋转上来”，这样要删除的节点会一步步下沉，最终变成只有一个孩子或叶子节点。这个思路我很喜欢，因为它不需要像普通 BST 那样找前驱或后继来替换，代码更短，逻辑也更统一。

如果允许重复值，删除时应该先减cnt，只有cnt减到 0 才真正移除节点。

3. 进阶但常用：排名查询、第 k 小元素与前后驱

3.1 为节点增加子树大小

前面节点定义里已经预留了size字段。维护它只需要所有可能改变树结构的操作完成后调用一次push_up：

void push_up(Node* t) { if (t) { t->size = 1; if (t->left) t->size += t->left->size; if (t->right) t->size += t->right->size; } }

有了size字段，就能做很多普通 BST 做不了或做起来很麻烦的统计操作，比如“查询第 k 小的元素”“查询某个数的排名”。这两个操作是平衡树在榜单、搜索场景里的高频需求。

3.2 查询某元素的排名

排名的定义通常是一共有多少个数“严格小于”它，再加 1。递归逻辑分三种情况：

int rank(Node* t, int k) { if (t == nullptr) return 1; // 找不到也返回一个边界值 int leftSize = t->left ? t->left->size : 0; if (k == t->key) { return leftSize + 1; } else if (k < t->key) { return rank(t->left, k); } else { return leftSize + 1 + rank(t->right, k); } }

这里要注意：如果 k 是重复值且存储在一个节点里，且该节点有cnt计数值，排名要按leftSize + cnt计算。如果不希望相同值的排名出现多个，通常处理成“最小排名”或“最大排名”。我在实际使用时一般求最大排名，因为名称相同说明并列，排名相同会更困惑，而“严格小于当前值的个数 + 计数”能给出区间上界。

3.3 查询第 k 小的元素

第 k 小是和排名互补的操作。根据左子树大小判断第 k 小的位置在哪：

int kth(Node* t, int k) { int leftSize = t->left ? t->left->size : 0; if (k <= leftSize) { return kth(t->left, k); } else if (k == leftSize + 1) { return t->key; } else { return kth(t->right, k - leftSize - 1); } }

这个代码的核心是：第 k 小要么在左子树，要么是当前根，要么在右子树。如果在右子树，问题规模缩减为“在右子树中找第 k - leftSize - 1 小”。

有了kth，Treap 可以当做一个有序数组的替代品，支持插入、删除、按位置访问——这就是平衡有序表的雏形，理论上可以替代部分需要动态维护有序序列的场景。

3.4 前驱与后继的两种写法

前驱是“小于给定值 x 的最大值”，后继是“大于 x 的最小值”。实现方式有两种：一种是通过 BST 的搜索路径不断更新答案，另一种是利用split操作直接分离出区间。我先讲传统的搜索路径法：

int pre(Node* t, int x) { int ans = -1; // 根据数据范围设定 while (t) { if (t->key < x) { ans = t->key; t = t->right; } else { t = t->left; } } return ans; }

后继写法对称，把判断条件改成t->key > x，去左子树找更小的答案即可。写前驱后继最容易犯的错误是搞错“去哪边找”：当前值小于 x 时，它可能是候选答案，但要找更大且仍小于 x 的，得去右子树看；当前值大于等于 x 时，它不能当答案，只能去左子树找更小的。

4. 实战调试与避坑手册

4.1 随机数种子与递归深度

很多人写 Treap 直接srand(time(0))，然后用rand()生成优先级。这在数据量小的时候没问题，但数据量达到几十万时，rand()的周期和质量就会拖后腿，树的平衡效果会变差。

更稳妥的方式是使用mt19937，它周期长、分布均匀，而且实现已经进入 C++ 标准库：

std::mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

每次新建节点时用rng()生成 priority 即可。注意不要把rng放在递归函数内部反复构造，否则会有很大的性能开销。

递归深度方面，虽然 Treap 期望高度是 O(log n)，但极端情况下递归深度仍可能达到几千层，特别是在节点数量一百万且优先级完全一样（很难发生）或者随机种子被写死时。如果使用递归写法，建议在大数据量场景把递归栈扩大，或者改用非递归实现。

一个常见的隐蔽坑是：测试时为了方便调试，故意把优先级设成“固定递增”或“全相同”，这时 Treap 的随机性被破坏了，退化成普通 BST 或按堆性质退化成另一条链。这是正常的，不代表代码有 bug。调试时可以打印树的高度和前序遍历，确认整体平衡。

4.2 优先级方向的统一问题

Treap 的堆性质有两种约定：大根堆（父节点 priority 大于子节点）或小根堆（父节点 priority 小于子节点）。两种写法都能工作，但整个代码必须统一。

我经常看到有人插入时用“子节点 priority 大于父节点则旋转”，删除时却用了“子节点 priority 小于父节点则旋转”，结果树结构越维护越乱。检查方法也很直接：插入若干随机数据后，写一个isHeap函数递归验证所有父节点的 priority 是否都大于子节点，就能立刻暴露问题。

bool checkHeap(Node* t) { if (t == nullptr) return true; if (t->left && t->left->prio > t->prio) return false; if (t->right && t->right->prio > t->prio) return false; return checkHeap(t->left) && checkHeap(t->right); }

这个验证函数建议在写完 Treap 后保留，它可以在整个调试阶段帮你排除大量隐性问题。

4.3 删除操作里的引用陷阱

前面强调过旋转和插入必须用Node* &t，删除更是如此。如果没有引用，递归删除一个节点后无法把父节点的孩子指针置空，树会连接到已释放的内存上，导致随机崩溃或内存泄漏。

用数组模拟版本时，参数是int &t传递根节点编号，同样要小心。常见的崩溃场景是：删除叶子节点时把t直接设为 0，但调用方没有同步更新父节点的孩子数组，后续操作访问到已“删除”的节点编号时就会越界或读到旧数据。

我的建议是：无论用指针还是数组，删除函数的递归参数都写成引用或直接返回新子树根节点。返回新根节点的方式更纯粹：

Node* erase(Node* t, int k) { if (t == nullptr) return nullptr; if (k < t->key) { t->left = erase(t->left, k); } else if (k > t->key) { t->right = erase(t->right, k); } else { // ... } push_up(t); return t; }

调用处用root = erase(root, k)更新根节点即可，这样不容易出错。

4.4 内存回收与节点复用

动态new出来的节点在删除时需要delete，但高频插入删除时反复new/delete会有性能开销。很多竞赛选手和工程实现者会维护一个空闲节点栈或队列，把删除的节点编号回收复用。

比如数组模拟版本里，删除一个节点后把它的编号压入栈，新建节点时优先从栈中取出编号，而不是从 0 重新分配。

注意回收时要清零left/right指针，否则下次复用时会残留旧的孩子关系。

5. 从裸 Treap 到实用容器：封装与略复杂场景

5.1 整体类封装与对外接口

写完整篇骨架后，顺手把 Treap 封装成一个有序集合类，日常使用会舒服非常多。我习惯把之前所有函数收进来，只暴露需要的方法：

class Treap { private: Node* root; std::mt19937 rng; // 每次实例独立随机 void push_up(Node* t); void rotate(Node* &t, int dir); void insert(Node* &t, int k); void erase(Node* &t, int k); int rank(Node* t, int k); int kth(Node* t, int k); public: Treap() : root(nullptr), rng(std::random_device{}()) {} void insert(int k) { insert(root, k); } void erase(int k) { erase(root, k); } int rank(int k) { return rank(root, k); } int kth(int k) { return kth(root, k); } };

如果要在多线程环境下使用，需要给每个实例独立的rng而不是使用全局随机函数，避免并发下随机序列错乱。这个细节不做的话，并发场景下很容易出现不可复现的奇怪 bug。

5.2 Treap 的扩展思路：split 与 merge

传统旋转型 Treap 是可以做到更多区间操作的。把插入、删除换成split和merge两个核心原语后，Treap 可以优雅地支持区间反转、区间求和、区间加值等序列操作，这就是 FHQ Treap（无旋 Treap）的基本思路。

由于本篇文章以旋转型 Treap 为主线，这里想补充的是：当你掌握了旋转型 Treap 之后，可以顺着两个孩子的方向进一步看无旋 Treap，它不需要旋转，只依赖 split 和 merge，代码更短，功能更灵活。

学习顺序上，我建议先写熟旋转型 Treap，理由有两个：第一，旋转操作对“为什么要调平衡”有直观的身体记忆，后续理解任何平衡树都更容易；第二，旋转型 Treap 涉及引用参数、递归返回更新、优先级维护，这些踩坑经验是数据结构调试的通用技术。

但如果你目标明确是拿来做区间操作的文艺平衡树，比如维护一个可翻转序列，那直接学 FHQ Treap 会更高效。我自己是两种都写过之后，才形成“旋转型理解本质、FHQ 型应对业务”的搭配。

5.3 最后的实测建议

手写 Treap 的过程里，最容易出问题的其实不是旋转，而是各种递归路径上size更新不及时。这里分享一个习惯：每次插入或删除完，写一个小的数据生成器，生成随机操作序列，再用暴力数组模拟验证结果是否一致。

验证步骤大概是：随机执行 1 万次插入/删除/查询排名/查询第 k 小，每组操作同时在一个普通数组里做同样的事，最后对比输出。Treap 输出和暴力结果不一致，就立刻能定位到是哪个操作出了问题。这个过程可以帮你快速排掉 90% 的隐藏 bug。

关于 Treap 的实际性能，以我测试的结果来看：在 10 万级随机插入删除的场景下，和红黑树相比并没有明显劣势；在需要频繁找第 k 小、排名的场景下甚至更灵活。它最大的优势从来不是极限性能，而是“在可接受的复杂度保证下，代码短、写法统一、不容易写错”。

使用 Treap 时还需要注意数据范围。如果 node 数量很大且坐标值也很大，推荐用离散化后的下标作为 key，而不是直接存原始值，这样搜索定位更稳定，内存也更紧凑。

我在实际项目中最后一次大规模用 Treap，是在一个动态榜单模块里：用户分数实时更新，需要高频查询自己的排名，也需要定时取前 100 名。直接用一个 Treap 实例存分数到人数的映射，配合kth接口，整个模块只用了不到两百行代码就上线了，至今没有出过问题。

如果你正在为平衡树选型纠结，我的建议是：除非有严格的性能瓶颈分析指明需要红黑树，否则从 Treap 起步完全够用。等它满足不了需求时，你已经有足够的数据结构直觉去学更复杂的替代方案了。