treap学习笔记

最近自学了treap发现真tm好写，跟splay不相上下，更重要的是它的无旋版本，简直强到爆炸，还有什么可持久化。。。先讲讲带旋转的。

我们看下treap是啥玩意

treap == tree + heap，也就是二分查找树加上堆

我们首先思考一下，为什么我们要用平衡树这种神奇的万一而不用二叉查找树？因为万恶的出题人出的数据总能搞爆你。

但是如果我的二叉排序树的建立并不依靠于你输入的顺序而是完全随机的呢？

可以发现这样的树一般都不会被卡住，毕竟RP也不会太差。

于是便有了基于这种思想的treap

我们给每一个节点附加一个值，这个值由rand生成，总所周知，平衡树的旋转操作不会改变它的中序遍历，所以我们就基于这个思想，在按照二叉排序树的规则插入之后，再使得这个节点符合大根（小根）堆的性质，把它往上旋转，可以发现，你的二叉排序树的建构正是这些点按照随机数值从大到小的顺序插入而形成的。

很容易解释，因为这个点如果越先插入，自然越上层，而这个点的随机权值越大，自然越往上层走，自然这棵树也就是按照这样的权值从大到小建立。

于是就很好写的吧。。

插入就是插了之后看符不符合堆的性质，删除就是把这个节点旋转至叶子再删，并且实际上这个树是可以实现分裂与合并的，并不是大多数人说的只有无旋treep才能分裂合并。

分裂的时候我们找到要分裂的那个点，然后把随机权值变成无限大，然后把它往上旋转，然后旋转到根节点后如果是1-l,就把它的右子树分离出去，如果是1-l-1则是左子树分离。

同样合并的时候必须满足左边的点都小于右边的点，然后瞎jb建一个点，随机权值设为最小，它的左右两颗子树分别是两个要合并的树的根，然后把这个点往下旋转到叶子删除后就是合并。