1. 题目与适用场景
你需要维护一个动态有序集合，支持按键查找、插入、删除，并偶尔把集合按键切成左右两棵树再合并。请实现 Treap：每个节点同时满足按 key 的二叉搜索树不变量和按随机 priority 的最大堆不变量。题目先假设键唯一，再说明如何处理重复键。
2. 面试官考察点
- 能说清楚 BST 不变量与堆不变量分别解决什么问题。
- 能用
split和merge组合出插入、删除，而不是只背旋转代码。 - 知道
O(log n)是期望复杂度，随机数质量和优先级碰撞会影响形状。 - 能维护子树大小或聚合值，并指出更新顺序和空子树边界。
3. 回答前需要澄清的问题
- 键是否唯一？若允许重复，要选“相同键放左/右”或把
(key, id)当作复合键，并让所有操作采用同一规则。 - 优先级是调用方提供还是内部生成？内部生成要说明随机源、碰撞处理和测试可复现的种子。
split的边界是左树包含key，还是严格小于key？这个选择会改变插入和范围查询的代码。- 是否需要第 k 小、区间和或隐式序列？需要时每个修改函数都必须更新子树元数据。
4. 30 秒回答框架
“我把节点按 key 维护 BST 顺序，再给每个节点随机 priority 维护最大堆。核心是 split(T, key) 返回小于等于 key 与大于 key 的两棵树，merge(L, R) 假设 L 的所有 key 小于 R，并按根 priority 选择新根。插入先 split 再 merge，删除找到节点后 merge 两个子树。每次递归返回前更新 size。平均高度和主要操作是 O(log n)，但极端随机优先级仍可能退化，所以生产实现需要可复现测试、深度监控或有最坏界的平衡树。”
5. 分步骤深入解答
第一步固定不变量。对任意节点，左子树 key 不大于节点 key，右子树 key 更大；节点 priority 不小于两个子节点。本文采用“相同 key 进入左侧”的规则，实际实现也可用 (key, uniqueId) 消除歧义。
第二步实现 split。若根 key 小于等于边界，根和左子树属于左结果，只递归拆右子树；否则根属于右结果，只递归拆左子树。递归返回后重新连接对应孩子并更新 size。这样只沿一条根到叶路径工作。
第三步实现 merge。先处理空树；若左根 priority 更高，左根保留为根，递归把左树右子树与右树合并；否则右根保留为根，递归合并左树与右根左子树。前提是左树所有 key 都不大于右树，否则 BST 不变量会被破坏。
第四步组合操作。插入新节点时 split(root, key)，再 merge(merge(left, node), right)；删除目标节点时用 merge(node.left, node.right) 替换它。查找沿 key 下降，不需要 split。若维护 size，在每个 split、merge、insert、erase 返回前执行 size = 1 + size(left) + size(right)。
第五步讨论复杂度与失败场景。随机 priority 让树形分布等价于随机构造的 BST，主要操作期望为 O(log n)；CP-Algorithms 也给出 split、merge、插入和删除的对数期望复杂度。若随机源产生近似单调 priority，树会退化到 O(n)；需要固定种子做测试、监控高度，或改用 AVL、红黑树等有最坏界结构。
6. 高质量示范回答
“我会先约定重复键规则，再实现两个原语。split 按边界返回左侧和右侧，递归拆一棵子树后把根重新接回；merge 假设左树 key 全部不大于右树，比较两个根的 priority 来决定新根。插入是 split 后把新节点夹在中间，删除是找到节点后 merge 它的两个孩子。每次修改都更新子树 size，因此还能支持第 k 小。随机 priority 带来 O(log n) 期望高度，但不是最坏保证；我会用固定种子覆盖重复键、空树和连续操作，线上监控高度，若需要严格最坏界则选红黑树。”
7. 常见错误
- 错误表现 → 只维护 BST 顺序 → 有序插入仍退化成链表 → 同时维护 priority 堆不变量。
- 错误表现 →
merge不检查两树 key 范围 → 合并后查找路径错误 → 在接口契约中明确左树不大于右树。 - 错误表现 → split 后忘记更新子树 size → 第 k 小和范围统计逐渐失真 → 每次重连孩子后立即 pull。
- 错误表现 → 把期望
O(log n)当成最坏保证 → 对抗 priority 输入可构造深树 → 监控高度，必要时使用 AVL 或红黑树。 - 错误表现 → 重复键规则在查找、删除和 split 中不一致 → 同一键可能落入错误子树 → 用复合键或统一的左/右边界。
8. 追问及应对
如何支持第 k 小元素？
维护每个节点的子树 size。查询时比较左子树大小与 k；修改路径上的 split、merge、插入和删除都要更新 size，否则查询结果不可信。
如何把 Treap 用作隐式序列？
不显式存 key，把节点在序列中的位置定义为左子树大小加祖先贡献。按位置 split，再 merge 回去，就能支持任意位置插入、删除和区间聚合；还需要 lazy 标记处理区间反转或加法。
什么时候不用 Treap？
如果业务要求严格最坏 O(log n)、随机源不可控，或需要成熟并发实现，优先 AVL、红黑树或数据库索引。Treap 的优势是代码短、split/merge 灵活，代价是期望界和随机状态需要测试与监控。