@[henrytb](/user/76156)
> 这样能保证树高为 $O(\log n)$，但不保证其满足堆的性质。这样也是正确的，因为无旋式 treap 的优先级是用来使 merge 操作更加随机一点，而不是用来保证树高的。
> ——**OI Wiki**
by reveal @ 2023-03-16 11:10:41
@[reveal](/user/523491) 但是它确实在某个题被卡 T 了（
by AC_Automation @ 2023-03-16 11:12:18
@[reveal](/user/523491) 但是有个私题我这么写就 T 飞了（
by henrytb @ 2023-03-16 11:12:19
@[henrytb](/user/76156) 感觉好神秘阿。是不是按照二叉查找数的方式就能卡...毕竟不满足堆的性质好像确实会退化成链，但是还是不好说。
by opHJY2023 @ 2023-03-16 11:29:21
就是说考虑有旋treap的过程是通过旋转来满足堆的性质从而排除极劣情况。那时不是说如果每次都随机给一个堆值是不是就没有用了，旋转就是完全随机的？
by opHJY2023 @ 2023-03-16 11:32:01
~~还是说常数变大变高然后被卡了~~
by opHJY2023 @ 2023-03-16 11:33:45
@[_HJY2022](/user/236867) 不太懂，~~可能是变答辩糕~~。
by henrytb @ 2023-03-16 11:34:06
@[henrytb](/user/76156) treap的复杂度证明是每次选一个根，然后期望左边右边个数相等。
选取了一个根之后你想要加到一条链上是相当难的，因为你要比每一个都小。
那是不是说每次随机一个你的概率会变大，然后就不是 $O(\log_2 n)$ 的了？但是感觉你每次加到高度为 $h$ 的概率还是不高...
by opHJY2023 @ 2023-03-16 11:41:48
相当于之前是你选择一个随机变量，让他比某个常量少，然后你现在要每次选两个？
不太懂，treap学的不是很好。
by opHJY2023 @ 2023-03-16 11:42:36
以上说法均为本人的感性理解，如果错的离谱可以当我在胡扯
by opHJY2023 @ 2023-03-16 11:44:44