Treap 是什么，它如何用随机优先级保持平衡？

简化版

Treap = Tree + Heap。它对 key 满足二叉搜索树性质，对随机生成的 priority 满足堆性质。插入时先按 BST 插入，再通过旋转让 priority 恢复堆序；由于 priority 随机，树高期望为 O(log n)，所以查找、插入、删除的期望复杂度都是 O(log n)。

详细版

Treap 给每个节点两个值：业务 key 用来保持 BST 有序，随机 priority 用来模拟随机建树的平衡性。以小根堆 priority 为例，父节点 priority 要小于孩子。插入新 key 时，先像普通 BST 一样插到叶子位置，再看它的 priority 是否比父节点更小；若破坏堆性质，就旋转把它提上去，直到 BST 性质和堆性质都满足。

删除时通常把目标节点旋转下沉：优先让 priority 更小的孩子旋上来，直到目标节点变成叶子再删；也可以把 priority 改成极大值再下沉。Treap 不是严格平衡树，最坏仍可能 O(n)，但随机化让期望高度为 O(log n)。面试重点是双性质、旋转维护、期望复杂度和随机化风险。

完整版教学

一、Treap 的名字说明了它的本质

Treap 由 Tree 和 Heap 组成。它同时维护两套顺序：按 key 看，它是一棵二叉搜索树；按 priority 看，它是一棵堆。key 来自业务数据，priority 通常在插入时随机生成。这样做的目标是避免普通 BST 按有序数据插入时退化成链表。

每个节点:
  key      用于 BST 顺序
  priority 用于 Heap 顺序

BST 性质:
  left.key < node.key < right.key

小根堆性质:
  node.priority < child.priority

Treap 的平衡不是靠 AVL 的高度差，也不是靠红黑树的颜色，而是靠随机 priority 让树形近似随机。

二、为什么随机 priority 能带来期望平衡

如果只按 key 插入 1,2,3,4,5，普通 BST 会退化成右链，高度为 5。Treap 给每个 key 一个随机 priority，树形等价于“按 priority 从小到大决定谁先成为根”。随机 priority 打乱了有序 key 的插入影响，使每个元素都有机会成为局部根。

key:      1   2   3   4   5
priority: 50  12  80  30  60

priority 最小的 2 会更靠近根，
而不是让 key=1 因为最早插入就固定成根。

随机化分析的结论是：Treap 的期望高度为 O(log n)。这里要强调“期望”，因为如果随机数很差或被恶意构造，最坏仍可能退化到 O(n)。

三、插入如何同时维护 BST 和堆性质

插入分两步。第一步按 key 做普通 BST 插入，把新节点放到叶子；第二步检查 priority，如果新节点 priority 比父节点更小，就通过旋转把新节点提上去。旋转不会破坏 BST 中序顺序，但会改变父子高度关系，从而恢复堆性质。

插入 key=7, priority=10

      5(p=30)
        \
        9(p=40)
       /
    7(p=10)

7 的 priority 更小，需要先右旋 9，再左旋 5，使 7 上浮。

旋转的方向取决于新节点是父节点的左孩子还是右孩子。左孩子 priority 更高优先级时右旋，右孩子更高优先级时左旋。

四、插入代码框架

下面用小根堆 priority 描述。递归插入后，如果对应孩子的 priority 比当前节点更小，就旋转。

Node insert(Node root, int key) {
    if (root == null) return new Node(key, randomPriority());

    if (key < root.key) {
        root.left = insert(root.left, key);
        if (root.left.priority < root.priority) {
            root = rotateRight(root);
        }
    } else if (key > root.key) {
        root.right = insert(root.right, key);
        if (root.right.priority < root.priority) {
            root = rotateLeft(root);
        }
    }
    return root;
}

如果允许重复值，可以在节点上维护 count，避免相同 key 一直向某一侧插入。Treap 和其他 BST 一样，重复值策略必须提前定义。

五、删除为什么要旋转下沉

删除一个有两个孩子的节点时，普通 BST 会找前驱或后继替换；Treap 更常见的做法是让目标节点通过旋转向下沉，直到变成叶子再删。每次选择 priority 更小的孩子旋上来，才能保持堆性质。

删除场景	处理方式	原因
没有孩子	直接删除	不影响其他结构
只有一个孩子	用孩子替代	BST 和堆性质容易保持
两个孩子	旋转 priority 更小的孩子上来	保持堆性质并让目标下沉

delete(node):
  if node has two children:
    if left.priority < right.priority: rotateRight
    else: rotateLeft
    continue deleting old node below

这个过程的本质是把“要删除的 key”往叶子方向推，同时保持剩余节点仍是合法 Treap。

六、常见误区与追问

记忆钩子：Treap 的 key 管搜索顺序，priority 管树形高度。

误区：Treap 是严格平衡树。 Treap 依靠随机化保证期望平衡，不像 AVL 那样严格限制高度差。
误区：priority 可以根据 key 固定生成。 如果 priority 与 key 强相关，就可能失去随机化平衡效果。
误区：旋转会破坏 BST 性质。 正确的单旋保持中序序列不变，只调整局部高度和堆序。
追问：复杂度为什么说期望 O(log n)？ priority 随机时树形等价于随机 BST，期望高度为对数级。
追问：删除时为什么选择 priority 更小的孩子旋上来？ 因为小根堆要求父节点 priority 更小，旋上更小 priority 的孩子才能维持堆性质。
追问：Treap 和红黑树怎么取舍？ Treap 实现短、随机化简单；红黑树最坏复杂度更稳定，更适合标准库和强确定性场景。

七、加强记忆

Treap 要记成“双规则结构”：key 满足 BST，所以能按值搜索；priority 满足堆，所以随机决定树形。插入先按 key 放到叶子，再靠旋转让 priority 上浮；删除则把目标节点旋转下沉到容易删除的位置。它的优势是实现相对简单、期望 O(log n)，代价是最坏情况没有红黑树那样确定，随机数质量和重复值策略都要说清楚。

简化版

详细版