Treap（平衡树）
注：本文有部分内容参照了清华大学计算机科学与技术系 02 班郭家宝 2010011267 论文，如与其他同学的博客有所雷同，纯属巧合。
首先引入几个基础概念
BST性质：
一棵树中，左子树的值比当前的根小，右子树的值比当期的根大。左子树<根<右子树。
1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若它的右子树不空，则右子树上所有结点的值均大于它根结点的值；
3. 它的左、右子树也分别为二叉查找树。
上述性质被称为 BST 性质。可以看出，二叉查找树是递归定义的。
如图， 是一个二叉查找树。
最小堆性质：
最小堆，是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于其左子节点和右子节点的值。
通俗点讲：根节点的值比左右子树的值都要小。
如图，为最小堆。
PS：
之所以要讲BST性质，以及最小堆性质，因为Treap平衡树是他们结合起来的进化版。接下来就要进入正题了。
Treap的基本性质：Treap= Tree + Heap：
Treap 是一种平衡树。它满足BST性质，即左孩子的值，小于根节点的值，右孩子的值大于根节点的值。
Treap 在 BST 的基础上，添加了一个随机修正值。在满足 BST 性质的基础上，Treap 节点的修正值还满足最小堆性质。
最小堆性质可以被描述为每个子树根节点都小于等于其子节点。于是，Treap 可以定义为有以下性质的二叉树：
1. 若它的左子树不空， 则左子树上所有结点的值均小于它的根结点的值， 而且它的根节点的修正值小于等于左子树根节点的修正值；
2. 若它的右子树不空， 则右子树上所有结点的值均大它的根结点的值， 而且它的根节点的修正值小于等于右子树根节点的修正值；
3. 它的左、右子树也分别为 Treap。
旋转操作：
为了使Treap 中的节点同时满足BST 性质和最小堆性质，不可避免地要对其结构进行调整，当树的随机修正值不满足最小堆性质的时候，就要对树进行调整。
这种调整方式被称为旋转。在维护Treap 的过程中，只有两种旋转，分别是左旋转(简称左旋)和右旋转(简称右旋)。
左旋转：把这个节点一下的树整体向左旋转，也就是把右节点旋到根的位置，而根的位置旋转到左结点的位置，如果右节点本身也有一个右节点，那么把它的右节点旋到根的右节点位置。
至于这么放的原理，如果在大小关系上一时不能理解，那么可以认为，因为根的左结点已经有数了，所以只能把右节点的左结点放到根的右节点位置上。
如果从BST性质的方向来看，这样子旋转是有利于维护BST性质的，因为根的右节点中的值都是比根节点的值要大的，所以旋转过来，即使是右节点的左结点，也会比根大，所以要放在根的右节点部位。
可能越说越晕了，看图：
如上图所示的左边的一个 Treap，它仍然满足BST 性质。但是由于某些原因，节点 4 和节点2 之间不满足最小堆序，4 作为2 的父节点，它的修正值大于左子节点的修正值。
我们只有将2 变成4 的父节点，才能维护堆序。根据旋转的性质我们可以知道，由于2 是4 的左子节点，为了使 2 成为4 的父节点，我们需要把以 4 为根的子树右旋。右旋后，2 成为了4的父节点，满足堆序。
插入操作：
在Treap 中插入元素，与在 BST 中插入方法相似。首先找到合适的插入位置，然后建立新的节点，存储元素。但是要注意建立新的节点的过程中，会随机地生成一个修正值，这个值可
能会破坏堆序，因此我们要根据需要进行恰当的旋转。具体方法如下：
1. 从根节点开始插入；
2. 如果要插入的值小于等于当前节点的值：
在当前节点的左子树中插入，插入后如果左子节点的修正值小于当前节点的修正值，对当前节点进行右旋；
3. 如果要插入的值大于当前节点的值：
在当前节点的右子树中插入，插入后如果右子节点的修正值小于当前节点的修正值，对当前节点进行左旋；
4.如果当前节点为空节点，在此建立新的节点，该节点的值为要插入的值，左右子树为空，插入成功。
删除操作:
关于删除操作，我决定先从懒惰删除开始说起：
懒惰删除就是在删除时，仅仅将元素找到后给元素打上“已被删除”的标记，而实际上不把
它从平衡树中删除。
这种做法的优点是节约代码量，减少编程时间，对于初学者来说，是理解以及实现删除功能的好帮手。
但它的缺点也是很严重的：如果插入量和删除量都很大，这种删除方式会在平衡树中留下大量的“废节点”，浪费空间，还影响效率。
专业删除操作：
情况一：该节点为叶节点或链节点，则该节点是可以直接删除的节点。若该节点有非空子节点，用非空子节点代替该节点的，否则用空节点代替该节点，然后删除该节点。
情况二：该节点有两个非空子节点。我们的策略是通过旋转，使该节点变为可以直接删除的节点。如果该节点的左子节点的修正值小于右子节点的修正值，右旋该节点，使该节点降为右子树的根节点，然后访问右子树的根节点，继续讨论；反之，左旋该节点，使该节点降为左子树的根节点，然后访问左子树的根节点，继续讨论，直到变成可以直接删除的节点。
代码实现如下（正确删除方式）：
#include#include #include #include #include struct Tnode{ Tnode *son[2]; int fix, v; int siz; Tnode(int _v = 0) { son[0] = son[1] = 0; v = _v; } void Update() { siz = 1; if (son[0]) siz += son[0] -> siz; if (son[1]) siz += son[1] -> siz; }} *r, Mem[1000050], *cur;Tnode *NewNode(int v = 0){ (*cur) = Tnode(v); return cur ++;}void Rotate(Tnode *&x, int t){ Tnode *y = x -> son[t^1]; x -> son[t^1] = y -> son[t]; y -> son[t] = x; x -> Update(); y -> Update(); x = y;}void Insert(Tnode *&r, int x){ if (!r) { r = NewNode(x); r -> siz = 1; r -> fix = rand(); return ; } int t = (x > (r->v)); Insert(r -> son[t], x); if (r -> son[t] -> fix < r -> fix) Rotate(r, (t^1)); r -> Update();}int Ask(Tnode* r, int k){ if (!r) return 0; int leftsiz = (r->son[0]) ? (r -> son[0]->siz) : 0; if (k <= leftsiz) return Ask(r->son[0], k); if (k <= leftsiz + 1) return r -> v; return Ask(r -> son[1], k - leftsiz - 1);}void Delete(Tnode *&r, int x){ if (x == r -> v) { if (r -> son[0] && r -> son[1]) { int t = (r -> son[1] -> fix > r -> son[0] -> fix); Rotate(r, t); Delete(r -> son[t], x); r -> Update(); } else if (! r -> son[0] && ! r -> son[1]) { r = 0; } else if (r -> son[0]) r = r -> son[0]; else r = r -> son[1]; return ; } Delete(r -> son[x > r->v], x); r -> Update();}int main(){ freopen("2165.in", "r", stdin); freopen("2165.out", "w", stdout); srand((int)time(0)); cur = Mem; int N; scanf("%d", &N); r = 0; while (N--) { int t, x; scanf("%d%d", &t, &x); if (t == 1) { Insert(r, x); } else if (t == 2) { printf("%d\n", Ask(r, x)); } else { Delete(r, x); } } return 0;}
附录：
关于Treap平衡树与其他平衡树的功能及速度比较。
关于treap的其他功能：
查找排名第k排名的元素：
1.定义P 为当前访问的节点，从根节点开始访问，查找排名第 k 的元素；
2.若满足P.left.size + 1<=k <= P.left.size + P.weight，则当前节点包含的元素就是排名第 k 的元素；
3.若满足k <P.left.size + 1 ，则在左子树中查找排名第 k 的元素；
4.若满足k >P.left.size + P.weight，则在右子树中查找排名第 k-(P.left.size +P.weight)的元素。
求元素的排名：
在 Treap 中求元素的排名的方法与查找第 k 小的数是很相似的，可以近似认为是互为逆运算。
1.定义P 为当前访问的节点，cur 为当前已知的比要求的元素小的元素个数。从根节点开始查找要求的元素，初始化 cur为0。
2.若要求的元素等于当前节点元素，要求的元素的排名为区间[ P.left.size + cur + 1, P.left.size + cur + weight ]内任意整数；
3.若要求的元素小于当前节点元素，在左子树中查找要求的元素的排名；
4.若要求的元素大于当前节点元素，更新cur 为cur + P.left.size+weight ，在右子树中查找要求的元素的排名。
前驱与后继 ：
求一个元素在平衡树(或子树)中的前驱，定义为查找该元素在平衡树中不大于该元素的最大元素。相似的，求一个元素在平衡树(或子树)中的后继，定义为 查找该元素在平衡树中不小于该元素的最小元素。
求前驱：
1. 从根节点开始访问，初始化最优节点为空节点；
2. 如果当前节点的值不大于要求前驱的元素的值，更新最有节点为当前节点，访问当前节点的右子节点；
3. 如果当前节点的值大于要求前驱的元素的值，访问当前节点的左子节点；
4. 如果当前节点是空节点，查找结束，最优节点就是要求的前驱。
求后继：
1. 从根节点开始访问，初始化最优节点为空节点；
2. 如果当前节点的值不小于要求前驱的元素的值，更新最有节点为当前节点，访问当前节点的左子节点；
3. 如果当前节点的值小于要求前驱的元素的值，访问当前节点的右子节点；
4. 如果当前节点是空节点，查找结束，最优节点就是要求的后继。