randomized BST · Cartesian tree

treap 树堆 · 拆解与动手

本页假设已了解二叉搜索树 (BST) 的基本结构；若想先看另一种平衡方案可参考 red-black tree。平衡 BST 通常要记颜色 (red-black) 或平衡因子 (AVL) 才能不退化成链表。treap 走了一条更轻巧的路——给每个节点掷一个随机 priority，让树在满足 BST 有序的同时还满足 heap 序（priority 越小越靠根）。关键性质：满足两条性质的形状唯一，而随机的 priority 让这个形状的期望树高是 O(log n)，不需要任何额外的平衡元数据。先从随机为何能平衡的直觉出发，再看旋转式插入 / 删除中 rotation 怎么把 heap 序补回来，最后看 treap 的另一套实现——用 split / merge 两块积木无旋转地组合出全部操作。

本页约定：节点画成圆圈，圈内上方是 value（BST 钥匙）、下方小字是 p+priority（heap 钥匙）。priority 越小越靠根、颜色越深；越大越靠叶、颜色越浅。当前操作涉及的节点用橙色描边高亮。本实现用 min-heap 约定（根的 priority 最小）。

1 · 为什么随机 priority 就能平衡

朴素 BST 的形状只由插入顺序决定：按 1, 2, 3, … 这样的有序序列插入，每个新值都比所有已存在的大，只能不停往右挂——树退化成一根链表，查找退回 O(n)。

**treap 的巧思：**再给每个值配一把随机的「第二钥匙」priority。要求树同时满足两条性质——其一，横向看是 BST（左 < 根 < 右）；其二，纵向看是 min-heap（父的 priority ≤ 孩子）。可以证明：满足这两条的形状是唯一的，而且它正好等于「按 priority 从小到大的顺序把这些值插入朴素 BST」得到的树。

既然 priority 是随机的，这就等价于按随机顺序插入——而随机顺序 BST 的期望树高约 2 ln n ≈ 1.39 log₂n，即 O(log n)，与原始输入是否有序无关。

下面把同一串有序输入分别交给朴素 BST 和 treap。朴素 BST 退化成链；treap 每次重掷 priority 形状都不同，但高度始终保持在 log 级附近。多次点击「重掷 priority」可观察随机带来的稳定性。

为什么唯一？priority 最小的那个值必然是根（heap 序）；它把其余值按 value 分成左右两堆；每一组里再选 priority 最小者当子树根，递归下去，每一步的选择都被两条性质完全确定，没有自由度，所以形状唯一。换句话说，treap =「BST 结构」与「按 priority 的堆」的同一棵树，这也是它另一个名字笛卡尔树 (Cartesian tree) 的来历：把每个节点看成平面上的点 (value, priority)。

2 · 插入：BST 挂叶，再按 priority 上浮

插入分两段，第二段是 rotate 起作用的地方：

其一，按 BST 规则从根下降，找到空位把新节点挂成叶子，给它配一个 priority。此时 BST 序一定对，但 heap 序可能被破坏——新叶子的 priority 也许比它父亲还小。

其二，上浮 (bubble up):只要新节点的 priority < 父亲的 priority，就对父亲做一次 rotation 把它转上去一层：

它是父亲的左孩子 → 对父亲右旋 (rotateRight);
它是父亲的右孩子 → 对父亲左旋 (rotateLeft)。

一直转到它的 priority ≥ 父亲、或它升成根为止。每次 rotation 都不改变中序顺序，所以 BST 序自始至终成立，我们只是在修 heap 序。

输入一个 value（priority 留空则随机掷），点「插入」，再用「下一步」逐步看下降、挂叶、每次旋转上浮；旁白说清每一步在干什么。插完展示两条性质的校验。

**为什么旋转不破坏 BST?**left / right rotation 是 BST 的恒等变形——它只改变父子的「上下」关系，被旋转的子树中序遍历结果完全不变。所以上浮过程只动 heap 序（priority 的上下）,BST 序（value 的左右）永远正确。这正是 treap 能「两把钥匙各管一维」的关键。

3 · 删除：把目标向下旋成叶子再摘掉

删除是旋转式插入的镜像。插入把新节点往上旋，删除则把目标往下旋：

其一，定位到要删的节点。若它已是叶子，直接摘除即可。

其二，向下旋转 (sink):只要它还有孩子，就看两个孩子里谁的 priority 更小，把那个孩子 rotation 上来，目标随之下沉一层：

左孩子 priority 更小 → 对目标右旋，左孩子升上去；
右孩子 priority 更小 → 对目标左旋，右孩子升上去。

（只有一个孩子时就转那个。）一直转到目标变成叶子，直接摘除。每次都把 priority 更小的孩子换到上面，所以下沉全程 heap 序保持；rotation 又不动中序，BST 序也保持。

先「随机建树」得到一棵 treap，再输入要删的 value 点「删除」，用「下一步」看目标怎么一层层沉到底被摘掉。

**和 BST 普通删除比？**普通 BST 删除「有两个孩子」的节点要找中序后继来顶替，分支多、易写错。treap 把它统一成「一直往下旋到叶子再摘」一种情形——代码很短，而且因为每次都让 priority 小的上移，旋完仍是合法 treap，不需要任何额外修复。

4 · split / merge：另一套无旋转实现

旋转式插入与删除要分左旋右旋、上浮下沉。treap 还有一套完全不靠 rotation 的实现，只需两个递归函数，其他操作都是它俩的组合：

merge(L, R)——前提：L 里所有 value < R 里所有 value。比较两棵根的 priority，谁小谁当合并后的根（heap 序），另一棵递归并到它对应的一侧。

split(T, key)——把 T 拆成两棵：L 装所有 value < key,R 装所有 value ≥ key，两棵各自仍是合法 treap。沿 BST 路径下降，按当前节点落在哪边把它和对应子树分给 L 或 R。

两者都是 O（树高）= 期望 O(log n)。

下面对一棵 treap 输入 key 做 split，看它拆成 <key 与 ≥key 两棵并排；再 merge 拼回原样。

有了这两块积木，其他操作都是拼装：

insert(v): 把树 split 成 (L, R) 关于 v，新建单节点 m，然后 merge(merge(L, m), R)。
delete(v): 找到 v，把它的左右子树直接 merge 起来顶替它的位置（左全 < 右，满足前提）。
区间操作 / implicit treap: 按「子树大小」而非 value 来 split，就能 O(log n) 抽取任意一段下标区间，做区间翻转、区间加等——这是平衡 BST 里 treap 在竞赛中常用的用法，下面有 lab。

5 · 进阶：implicit treap——按下标 split,O(log n) 区间翻转

把 treap 当成一个序列来用：节点不再按 value 排序，而是中序遍历的位置 = 数组下标。关键改动是每个节点多存一个 子树大小 size（节点右上角徽标），于是 split 不再比较 value，而是按 size 比下标：要取前 k 个，就在每个节点比较「左子树大小 + 1」与 k 决定往左还是往右——这就是 implicit（隐式）treap。

有了「按下标 split」，区间翻转 [l, r] 只需三步：split 出前 l 个得 A、再从余下 split 出 $r-l+1$ 个得中段 B；给 B 的根打一个「待翻转」懒标记(lazy)；最后 merge(A, B, C) 拼回。懒标记在后续访问 B 时才下传——交换左右孩子即完成翻转，整个操作 $O(\log n)$ ，完全不用真的搬动区间里的元素。

**value treap 与 implicit treap 是同一套 split/merge，只换了「split 的依据」。**前者按 value 比较（维护有序集合），后者按 size 比较（维护可随机存取、可区间操作的序列）。正因为 split/merge 把树拆拼得如此自由，配上懒标记后，区间翻转、区间加、区间和、把一段「剪切」到别处……都能做到 $O(\log n)$ ——这是数组和普通平衡 BST 都难兼得的。