经过一天RE的洗礼，终于把\(\mathrm{Splay}\)赶出来了，真不容易
虽然都是平衡树，但是\(\mathrm{Splay}\)和\(\mathrm{Treap}\)是不一样的
\(\mathrm{Treap}\)维持平衡的条件是每个节点随机赋予的优先级，但\(\mathrm{Splay}\)没有这个条件
\(\mathrm{Splay}\)维持平衡的条件就是：把一个节点插入到最底之后，直接用splay操作旋转到根
虽然单次操作可能较慢，但是这样保证了整棵\(\mathrm{Splay}\)的期望树高为\(O(\log n)\)，总体复杂度是确定的，相较于\(\mathrm{Treap}\)来说更稳定
原文：https://www.cnblogs.com/info---tion/p/13412171.html