如题。

官方题解好像也说 Treap 和红黑树都是对的。看起来是在说 Treap 一次插入旋转次数期望 $O(1)$，旋转的节点的子树大小期望 $O(\log n)$。这是真的吗，怎么证啊。

题外话，如果是真的，关于 Treap 的分裂合并操作（就是一般说的 fhq Treap）有类似的性质吗，有没有人给点学习资料啥的。