平衡树 (tt{Treap}) & (tt{Splay})

壹.单旋 (tt{Treap})

首先了解 (tt{BST})
非常好用的东西，但是数据可以把它卡成一条链 (dots)
于是，我们将 (tt{Tree}) 与 (tt{heap}) (堆) 合并，以保证平衡树 (log) 的深度。
具体地，我们可以使用旋转操作实现

K8He的图
以右旋为例，我们发现，本来的中序遍历顺序为 (y<p<x<q<z<r)，那么对于 (q) 右旋，即将左儿子旋上来，由于本来 (p<q) ，所以显然 (q) 要成为 (p) 的右儿子。那就剩下 (x) 无家可归，我们发现 (p<x<q)，那么 (q) 的左儿子再适合不过了。
我们规定 (0) 方向为左，(1) 方向为右，即可通过 (d) ^ (1) 实现方向取反。
一般的，对于一个节点 (i)，如果将其 (d) 方向上的儿子 (s) 旋上去，那么 (i) 要成为 (s) 在 ......