Treap 的随机优先级防退化本质是使树形态等价于随机顺序插入的BST，期望深度O(log n)；插入时通过旋转维护BST与堆双性质，rd必须高质量随机以避免伪平衡。
为什么 Treap 的随机优先级能防退化
普通二叉搜索树退化成链，本质是插入顺序决定了树高——比如按升序插入 1,2,3,4,5，结果就是右倾单链，查询/插入退化到 O(n)。Treap 不靠调整插入顺序，而是给每个节点额外绑定一个独立随机值 rd，并强制要求：键值 v 满足 BST 性质，而 rd 满足堆性质（通常用大根堆）。这样，整棵树的形态就等价于「按 rd 从小到大（或从大到小）的顺序插入这些键值」所形成的 BST ——而随机顺序插入的 BST，期望深度是 O(log n)，退化概率指数级衰减。
insert 时怎么用旋转维持双性质
插入新节点后，先按 v 找到叶子位置（BST 规则），再沿父路径向上检查堆性质：若当前节点 rd 小于父节点（大根堆下不满足），就旋转提升它。关键点在于：
- 右旋（
rotate(k, 1)）用于当新节点在父节点左子树且rd更大时；左旋（rotate(k, 0)）对应右子树情况 - 每次旋转只交换父子关系，不改变中序遍历顺序 → BST 性质不变
- 旋转后需调用
pushup(k)更新子树大小等信息，否则后续size统计会错 - 递归插入函数里，必须用引用传参（如
void insert(int &k, int v)），否则旋转后父指针无法更新
rd 随机数生成不能只用 rand()
rand() 在多数 libc 实现中周期短、低位随机性差，连续调用易出现相关性，极端情况下会让 rd 序列局部单调，削弱平衡效果。实操建议：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 用
std::mt19937配合std::uniform_int_distribution，种子用std::chrono::steady_clock::now().time_since_epoch().count() - 避免把
rd设为 0 或极小值（尤其做大根堆时），否则可能卡在根节点无法下沉 - 如果节点允许重复值，
rd必须全局唯一（可用计数器 fallback），否则堆比较时相等会导致旋转逻辑未定义
无旋 Treap 的 Split/Merge 更依赖 rd 分布
无旋写法不靠旋转，而是靠 split 和 merge：插入时先 split 出 v 两棵子树，再 merge 左子树 + 新节点 + 右子树。此时 merge 的决策依据是比对两子树根的 rd ——谁大谁当新根。这意味着：
立即学习“C++免费学习笔记（深入）”；
-
rd的分布质量直接决定树高：若某次merge总选同一侧根，就会偏向生长 - 不能用
rand() % MOD截断，必须保证足够大范围（如uint32_t全域），减少碰撞概率 -
split递归终止条件要严格区分和 <code>> v，否则重复键值处理会漏节点或重复计数
真正难的不是写对旋转或 split，而是让 rd 足够“随机”——它不参与业务逻辑，却默默撑起整棵树的复杂度底线。很多线上 Treap 崩溃，查到最后都是 rd 生成器被复用或种子固定导致的伪随机塌方。
