为何我实现的Treap高度几乎是预期值的两倍？

先明确：对于n=934的Treap，理论期望高度约为2*log₂(n)≈20（Treap的期望高度是O(log n)，常数通常在2左右）。你的测试结果[19,26]刚好卡在这个区间的上下限附近，用log₁₀计算出的6-7常数，换成log₂的话其实是1.9-2.6，更接近理论常数范围。不过回到你的问题，假设插入、高度计算、随机优先级生成逻辑都正确，可能的原因有这些：

• 旋转操作细节错误：比如左旋/右旋时，没有正确维护子节点的父子关系，或者旋转后未及时更新节点的高度、子树大小等关联字段。举个例子，右旋时把左子节点的右子树挂到当前节点左子树后，忘记更新当前节点的高度，导致树的结构没有真正被“拉平”，平衡调整失效。
• 优先级比较方向搞反：Treap的核心规则是父节点优先级必须高于子节点（通常数值越大优先级越高）。如果代码里把比较逻辑写反——比如子节点优先级高于父节点时才触发旋转，平衡调整方向会完全错误，树会往更深的方向生长，最终高度翻倍。
• 节点高度维护时机遗漏：即使高度计算逻辑正确，插入或旋转后若没有回溯更新所有祖先节点的高度，会导致后续平衡调整依赖的高度数据不准确，间接让树的结构失衡。比如插入新节点后只更新了父节点高度，没继续往上同步到根节点，使得某些分支的旋转调整没有被触发。
• 重复优先级处理缺失：就算随机优先级生成逻辑没问题，若未处理优先级重复的情况，当多个节点优先级相同时，Treap会退化成普通BST结构。如果测试用例的键值本身是有序的，重复优先级会直接导致树的高度接近log₂(n)的两倍甚至更高。
• 分裂/合并逻辑的隐藏错误：如果你的Treap实现包含分裂或合并操作（哪怕只测试了插入），这些操作的逻辑漏洞可能间接影响插入后的树结构，破坏平衡效果。

另外补充：Treap的期望高度常数因子本身约为2，如果你把“预期高度”当成log₂(n)，其实是对Treap理论预期的理解偏差。

内容的提问来源于stack exchange，提问作者idkusrname126