人生中第一次知道怎么写可持久化Treap……之前一直以为split是两个log的，后来发现split的过程中merge是O(1)的，这才想明白

.版权声明：本文为博主原创文章，未经博主允许不得转载。
目录(?)[+]
定义数据结构SBT树的性质旋转维护SBT性质Maintain插入删除获取最小值获取最大值前驱后继求第K小数求元素的秩定义数据结构
[cpp] view plain copy print?
01.struct SBT
02.{
03. int key,left,right,size; 04.} tree[N];
struct SBT
{
int key,left,right,size;
} tree[N];key:存储值，left,right：左右子树，size：保持平衡最终要的数据，表示子树的大小
SBT树的性质
定义一个节点x，同时满足下面两个条件
[cpp] view plain copy print?
01.(a)、x.left.size >= max(x.right.right.size, x.right.left.size)
02.(b)、x.right.size >= max(x.left.left.size, x.left.right.size)
(a)、x.left.size >= max(x.right.right.size, x.right.left.size)
(b)、x.right.size >= max(x.left.left.size, x.left.right.size)即每棵子树的大小不小于其兄弟子树的大小
结点L 和R 分别是结点T 的左右儿子。子树A;B;C;D 分别是结点L 和R 各自的左右子树。
即：R.size >= max(A.size,B.size)
L.size >= max(C.size,D.size)
旋转
左旋伪代码：
[cpp] view plain copy print?
01.Left-Rotate (t)
02.
03.1 k ← right[t]
04.2 right[t] ← left[k]
05.3 left[k] ← t
06.4 size[k] ← size[t]
07.5 size[t] ← size[left[t]] + size[right[t]] + 1
08.6 t ← k
Left-Rotate (t)
1 k ← right[t]
2 right[t] ← left[k]
3 left[k] ← t
4 size[k] ← size[t]
5 size[t] ← size[left[t]] + size[right[t]] + 1
6 t ← k[cpp] view plain copy print?
01.void left_rot(int &x)
02.{
03. int y = tree[x].right; 04. tree[x].right = tree[y].left;
05. tree[y].left = x;
06. tree[y].size = tree[x].size;//转上去的节点数量为先前此处节点的size 07. tree[x].size = tree[tree[x].left].size + tree[tree[x].right].size + 1;
08. x = y;
09.}
void left_rot(int &x)
{
int y = tree[x].right;
tree[x].right = tree[y].left;
tree[y].left = x;
tree[y].size = tree[x].size;//转上去的节点数量为先前此处节点的size
tree[x].size = tree[tree[x].left].size + tree[tree[x].right].size + 1;
x = y;
}
右旋
[cpp] view plain copy print?
01.Right-Rotate(t)
02.
03.1 k ← left[t]
04.2 left[t] ← right[k]
05.3 right[k] ← t
06.4 size[k] ← size[t]
07.5 size[t] ← size[left[t]] + size[right[t]] + 1
08.6 t ← k
Right-Rotate(t)
1 k ← left[t]
2 left[t] ← right[k]
3 right[k] ← t
4 size[k] ← size[t]
5 size[t] ← size[left[t]] + size[right[t]] + 1
6 t ← k[cpp] view plain copy print?
01.void right_rot(int &x)
02.{
03. int y = tree[x].left; 04. tree[x].left = tree[y].right;
05. tree[y].right = x;
06. tree[y].size = tree[x].size;
07. tree[x].size = tree[tree[x].left].size + tree[tree[x].right].size + 1;
08. x = y;
09.}
void right_rot(int &x)
{
int y = tree[x].left;
tree[x].left = tree[y].right;
tree[y].right = x;
tree[y].size = tree[x].size;
tree[x].size = tree[tree[x].left].size + tree[tree[x].right].size + 1;
x = y;
}旋转只需要理解如何维护子树size即可，旋转操作不能改变二叉查找树的基本性质
维护SBT性质（Maintain）
当我们插入或删除一个结点后，SBT的大小就发生了改变。这种改变有可能导致性质(a)或(b)被破坏。这时，我们需要用Maintain操作来修复这棵树。Maintain操作是SBT中最具活力的一个独特过程；Maintain(T)用于修复以T为根的 SBT。调用Maintain(T)的前提条件是T的子树都已经是SBT了。
我们需要讨论的有4种情况。由于性质a和性质b是对称的，所以我们仅仅详细的讨论性质a。
第一种情况：x.left.left.size > x.right.size
即：insert(T.left,key)后A.size > R.size
1、首先执行Right-Ratote(t)，这个操作使上图变成下图；
2、在这之后，有时候这棵树还仍然不是一棵SBT，因为 s[C]>s[B] 或者 s[D]>s[B] 也是可能发生的。所以就有必要继续调用Maintain(T)。
3、结点L的右子树有可能被连续调整，因为有可能由于性质的破坏需要再一次运行Maintain(L)。
第二种情况：x.left.right.size > x.right.size
在执行完insert(T.left,key)后发生B.size > R.size，如图5，这种调整要比情况1复杂一些。我们可以执行下面的操作来修复：
1、执行一次左旋操作Left-Ratote(L)后，就会变成下图
2、接着执行一次右旋操作Right-Ratote(T)，变成下图：
3、在经过两个巨大的旋转之后，整棵树就变得非常不可预料了。万幸的是，子树A;E; F;R 依然是容均树，所以要依次修复L 和T，Maintain(L),Maintain(T)。
4、子树都已经是容均树了，但B 可能还有问题，所以还要调用Maintain(B)
第三种情况：x.right.right.size > x.left.size
与第一种情况相反
第四种情况：x.right.left.size > x.left.size
与第二种情况相反
伪代码
[cpp] view plain copy print?
01.Maintain (t,flag)
02.
03.01 If flag=false then 04.02 If s[left[left[t]]>s[right[t]] then //case1 05.03 Right-Rotate(t)
06.04 Else
07.05 If s[right[left[t]]>s[right[t]] then //case2 08.06 Left-Rotate(left[t])
09.07 Right-Rotate(t)
10.08 Else //needn’t repair 11.09 Exit
12.10 Else
13.11 If s[right[right[t]]>s[left[t]] then //case1' 14.12 Left-Rotate(t)
15.13 Else
16.14 If s[left[right[t]]>s[left[t]] then //case2' 17.15 Right-Rotate(right[t])
18.16 Left-Rotate(t)
19.17 Else //needn’t repair 20.18 Exit
21.19 Maintain(left[t],false) //repair the left subtree 22.20 Maintain(right[t],true) //repair the right subtree 23.21 Maintain(t,false) //repair the whole tree 24.22 Maintain(t,true) //repair the whole tree Maintain (t,flag)
01 If flag=false then
02 If s[left[left[t]]>s[right[t]] then //case1
03 Right-Rotate(t)
04 Else
05 If s[right[left[t]]>s[right[t]] then //case2
06 Left-Rotate(left[t])
07 Right-Rotate(t)
08 Else //needn’t repair
09 Exit
10 Else
11 If s[right[right[t]]>s[left[t]] then //case1'
12 Left-Rotate(t)
13 Else
14 If s[left[right[t]]>s[left[t]] then //case2'
15 Right-Rotate(right[t])
16 Left-Rotate(t)
17 Else //needn’t repair
18 Exit
19 Maintain(left[t],false) //repair the left subtree
20 Maintain(right[t],true) //repair the right subtree
21 Maintain(t,false) //repair the whole tree
22 Maintain(t,true) //repair the whole tree[cpp] view plain copy print?
01.void maintain(int &x,bool flag)
02.{
03. if(flag == false)//左边 04. {
05. if(tree[tree[tree[x].left].left].size > tree[tree[x].right].size)//左孩子的左子树大于右孩子 06. right_rot(x);
07. else if(tree[tree[tree[x].left].right].size > tree[tree[x].right].size)//右孩子的右子树大于右孩子 08. {
09. left_rot(tree[x].left);
10. right_rot(x);
11. }
12. else return; 13. }
14. else //右边 15. {
16. if(tree[tree[tree[x].right].right].size > tree[tree[x].left].size)//右孩子的右子树大于左孩子 17. left_rot(x);
18. else if(tree[tree[tree[x].right].left].size > tree[tree[x].left].size)//右孩子的左子树大于左孩子 19. {
20. right_rot(tree[x].right);
21. left_rot(x);
22. }
23. else return; 24. }
25. maintain(tree[x].left,false); 26. maintain(tree[x].right,true); 27. maintain(x,true); 28. maintain(x,false); 29.}
void maintain(int &x,bool flag)
{
if(flag == false)//左边
{
if(tree[tree[tree[x].left].left].size > tree[tree[x].right].size)//左孩子的左子树大于右孩子
right_rot(x);
else if(tree[tree[tree[x].left].right].size > tree[tree[x].right].size)//右孩子的右子树大于右孩子
{
left_rot(tree[x].left);
right_rot(x);
}
else return;
}
else //右边
{
if(tree[tree[tree[x].right].right].size > tree[tree[x].left].size)//右孩子的右子树大于左孩子
left_rot(x);
else if(tree[tree[tree[x].right].left].size > tree[tree[x].left].size)//右孩子的左子树大于左孩子
{
right_rot(tree[x].right);
left_rot(x);
}
else return;
}
maintain(tree[x].left,false);
maintain(tree[x].right,true);
maintain(x,true);
maintain(x,false);
}
插入
在BST插入的基础上添加一个Maintain操作，用来对size的维护
[cpp] view plain copy print?
01.void insert(int &x,int key)
02.{
03. if(x == 0) 04. {
05. x = ++top;
06. tree[x].left = tree[x].right = 0;
07. tree[x].size = 1;
08. tree[x].key = key;
09. }
10. else 11. {
12. tree[x].size ++;
13. if(key < tree[x].key) insert(tree[x].left,key); 14. else insert(tree[x].right,key);//相同元素插入到右子树中 15. maintain(x, key >= tree[x].key);//每次插入把平衡操作压入栈中 16. }
17.}
void insert(int &x,int key)
{
if(x == 0)
{
x = ++top;
tree[x].left = tree[x].right = 0;
tree[x].size = 1;
tree[x].key = key;
}
else
{
tree[x].size ++;
if(key < tree[x].key) insert(tree[x].left,key);
else insert(tree[x].right,key);//相同元素插入到右子树中
maintain(x, key >= tree[x].key);//每次插入把平衡操作压入栈中
}
}
删除
与普通维护size域的BST删除相同。
关于无需Maintain的说明by sqybi：
在删除之前，可以保证整棵树是一棵SBT。当删除之后，虽然不能保证这棵树还是SBT，但是这时整棵树的最大深度并没有改变，所以时间复杂度也不会增加。这时，Maintain就显得是多余的了。
下面给出两种删除方式，一种是找前驱替换，一种是找后继替换
//后继
[cpp] view plain copy print?
01.int remove(int &x,int key)
02.{
03. tree[x].size --;
04. if(key > tree[x].key) 05. remove(tree[x].right,key);
06. else if(key < tree[x].key) 07. remove(tree[x].left,key);
08. else 09. {
10. //有左子树，无右子树 11. if(tree[x].left != 0 && tree[x].right == 0) 12. {
13. int temp = x; 14. x = tree[x].left;
15. return temp; 16. }
17. else if(tree[x].right !=0 && tree[x].left == 0) 18. {
19. int temp = x; 20. x = tree[x].right;
21. return temp; 22. }
23. //无左子树和右子树 24. else if(!tree[x].left && !tree[x].right) 25. {
26. int temp = x; 27. x = 0;
28. return temp; 29. }
30. //有右子树 31. else //找到x右子树中最小元素，也就是找后继元素 32. {
33. int temp = tree[x].right; 34. while(tree[temp].left) temp = tree[temp].left; 35. tree[x].key = tree[temp].key;
36. //tree[x].cnt = tree[temp].cnt; 37. remove(tree[x].right,tree[temp].key);
38. }
39. }
40.}
int remove(int &x,int key)
{
tree[x].size --;
if(key > tree[x].key)
remove(tree[x].right,key);
else if(key < tree[x].key)
remove(tree[x].left,key);
else
{
//有左子树，无右子树
if(tree[x].left != 0 && tree[x].right == 0)
{
int temp = x;
x = tree[x].left;
return temp;
}
else if(tree[x].right !=0 && tree[x].left == 0)
{
int temp = x;
x = tree[x].right;
return temp;
}
//无左子树和右子树
else if(!tree[x].left && !tree[x].right)
{
int temp = x;
x = 0;
return temp;
}
//有右子树
else //找到x右子树中最小元素，也就是找后继元素
{
int temp = tree[x].right;
while(tree[temp].left) temp = tree[temp].left;
tree[x].key = tree[temp].key;
//tree[x].cnt = tree[temp].cnt;
remove(tree[x].right,tree[temp].key);
}
}
}//前驱
[cpp] view plain copy print?
01.int remove(int &x,int key)
02.{
03. int d_key; 04. //if(!x) return 0; 05. tree[x].size --;
06. if((key == tree[x].key)||(key < tree[x].key && tree[x].left == 0) || 07. (key>tree[x].key && tree[x].right == 0))
08. {
09. d_key = tree[x].key;
10. if(tree[x].left && tree[x].right) 11. {
12. tree[x].key = remove(tree[x].left,tree[x].key+1);
13. }
14. else 15. {
16. x = tree[x].left + tree[x].right;
17. }
18. }
19. else if(key > tree[x].key) 20. d_key = remove(tree[x].right,key);
21. else if(key < tree[x].key) 22. d_key = remove(tree[x].left,key);
23. return d_key; 24.}
int remove(int &x,int key)
{
int d_key;
//if(!x) return 0;
tree[x].size --;
if((key == tree[x].key)||(key < tree[x].key && tree[x].left == 0) ||
(key>tree[x].key && tree[x].right == 0))
{
d_key = tree[x].key;
if(tree[x].left && tree[x].right)
{
tree[x].key = remove(tree[x].left,tree[x].key+1);
}
else
{
x = tree[x].left + tree[x].right;
}
}
else if(key > tree[x].key)
d_key = remove(tree[x].right,key);
else if(key < tree[x].key)
d_key = remove(tree[x].left,key);
return d_key;
}
获取最小值
直接向左子树找到最左叶子节点即可
[cpp] view plain copy print?
01.int getmin()
02.{
03. int x; 04. for(x = root ; tree[x].left; x = tree[x].left); 05. return tree[x].key; 06.}
int getmin()
{
int x;
for(x = root ; tree[x].left; x = tree[x].left);
return tree[x].key;
}
获取最大值
[cpp] view plain copy print?
01.int getmax()
02.{
03. int x; 04. for(x = root ; tree[x].right; x = tree[x].right); 05. return tree[x].key; 06.}
int getmax()
{
int x;
for(x = root ; tree[x].right; x = tree[x].right);
return tree[x].key;
}
前驱
[cpp] view plain copy print?
01.int pred(int &x,int y,int key)//前驱 小于
02.{
03. if(x == 0) return y; 04. if(tree[x].key < key)//加上等号，就是小于等于 05. return pred(tree[x].right,x,key); 06. else return pred(tree[x].left,y,key); 07.}//pred(root,0,key) int pred(int &x,int y,int key)//前驱 小于
{
if(x == 0) return y;
if(tree[x].key < key)//加上等号，就是小于等于
return pred(tree[x].right,x,key);
else return pred(tree[x].left,y,key);
}//pred(root,0,key)
注解：if(tree[x].key < key) 则说明前驱(小于key中所有元素最大的那个)在右子树，并且设定当前节点x为其前驱
if(tree[x].key >= key)说明前驱在左子树，当前节点x的key值也不是其前驱，所以设定其前驱仍为y
后继
[cpp] view plain copy print?
01.int succ(int &x,int y,int key)//后继 大于
02.{
03. if(x == 0) return y; 04. if(tree[x].key > key) 05. return succ(tree[x].left,x,key); 06. else return succ(tree[x].right,y,key); 07.}
int succ(int &x,int y,int key)//后继 大于
{
if(x == 0) return y;
if(tree[x].key > key)
return succ(tree[x].left,x,key);
else return succ(tree[x].right,y,key);
}同前驱。
求第K小数
[cpp] view plain copy print?
01.int select(int &x,int k)//求第k小数
02.{
03. int r = tree[tree[x].left].size + 1; 04. if(r == k) return tree[x].key; 05. else if(r < k) return select(tree[x].right,k - r); 06. else return select(tree[x].left,k); 07.}
int select(int &x,int k)//求第k小数
{
int r = tree[tree[x].left].size + 1;
if(r == k) return tree[x].key;
else if(r < k) return select(tree[x].right,k - r);
else return select(tree[x].left,k);
}注解：首先该源码如果插入的数有重复数据(即树中会出现两个或多个27，这样的数据)，此SBT是可以建树的，同样在查询第K小数上述代码也不会产生错误，但是这里需要消耗更多的存储空间（这里应该很容易明白），如果我们在数据结构中加上一个字段cnt,专门用来记录重复数据的个数，这样的话树中就没有重复数据，因为它们已经被合并了，这里需要修改insert函数和remove函数和旋转操作，如果删除操作每次删除的是整个节点而不是cnt>2就仅仅将cnt--而是整个删除，这样就会对size造成很大的影响 ，这种情况的remove函数我暂时没有想好如何去写，首先可以确定思路，如果删除节点是x，它的直接或间接父亲节点的size都需要减去x.cnt，但是我们是用的替换删除，这里怎么操作？还请哪位大牛指教，能够写出这样的remove函数。
还是先解释上面的代码，首先求出x的左子树size，再加上自己本身，如果这时r == k 则说明x.key就是第K小数，如果r < k，就说明第K小数在以x为根的右子树上，此时只需要在右子树上求第k-r小数即可，如果r > k那么说明第K小数在以x为根的左子树上。
求元素的秩
就是求这个元素排第几
[cpp] view plain copy print?
01.int rank(int &x,int key)//求key排第几
02.{
03. if(key < tree[x].key) 04. return rank(tree[x].left,key); 05. else if(key > tree[x].key) 06. return rank(tree[x].right,key) + tree[tree[x].left].size + 1; 07. return tree[tree[x].left].size + 1; 08.}
int rank(int &x,int key)//求key排第几
{
if(key < tree[x].key)
return rank(tree[x].left,key);
else if(key > tree[x].key)
return rank(tree[x].right,key) + tree[tree[x].left].size + 1;
return tree[tree[x].left].size + 1;
}这里就类似select的逆操作，代码就不解释了。
下面给出整个C++源码
[cpp] view plain copy print?
01.#include <iostream>
02.#include <cstdio> 03.#include <cstdlib> 04.#include <cstring> 05.#include <cmath> 06.#include <algorithm> 07.#include <set> 08.#include <map> 09.#include <vector> 10.#include <queue> 11.#include <ctime> 12.using namespace std; 13.#define LL long long 14.const int N = 10005; 15.const int INF=0x7FFFFFFF; 16.
17.struct SBT 18.{
19. int key,left,right,size; 20.} tree[N];
21.
22.int root,top; 23.
24.void left_rot(int &x) 25.{
26. int y = tree[x].right; 27. tree[x].right = tree[y].left;
28. tree[y].left = x;
29. tree[y].size = tree[x].size;//转上去的节点数量为先前此处节点的size 30. tree[x].size = tree[tree[x].left].size + tree[tree[x].right].size + 1;
31. x = y;
32.}
33.
34.void right_rot(int &x) 35.{
36. int y = tree[x].left; 37. tree[x].left = tree[y].right;
38. tree[y].right = x;
39. tree[y].size = tree[x].size;
40. tree[x].size = tree[tree[x].left].size + tree[tree[x].right].size + 1;
41. x = y;
42.}
43.
44.void maintain(int &x,bool flag) 45.{
46. if(flag == false)//左边 47. {
48. if(tree[tree[tree[x].left].left].size > tree[tree[x].right].size)//左孩子的左子树大于右孩子 49. right_rot(x);
50. else if(tree[tree[tree[x].left].right].size > tree[tree[x].right].size)//右孩子的右子树大于右孩子 51. {
52. left_rot(tree[x].left);
53. right_rot(x);
54. }
55. else return; 56. }
57. else //右边 58. {
59. if(tree[tree[tree[x].right].right].size > tree[tree[x].left].size)//右孩子的右子树大于左孩子 60. left_rot(x);
61. else if(tree[tree[tree[x].right].left].size > tree[tree[x].left].size)//右孩子的左子树大于左孩子 62. {
63. right_rot(tree[x].right);
64. left_rot(x);
65. }
66. else return; 67. }
68. maintain(tree[x].left,false); 69. maintain(tree[x].right,true); 70. maintain(x,true); 71. maintain(x,false); 72.}
73.
74./* 75.*insert没有合并相同的元素，如果出现相同的元素则把它放到右子树上，这样能保证求第k小数的时候对相同元素也能正确
76.*/
77.void insert(int &x,int key) 78.{
79. if(x == 0) 80. {
81. x = ++top;
82. tree[x].left = tree[x].right = 0;
83. tree[x].size = 1;
84. tree[x].key = key;
85. }
86. else 87. {
88. tree[x].size ++;
89. if(key < tree[x].key) insert(tree[x].left,key); 90. else insert(tree[x].right,key);//相同元素插入到右子树中 91. maintain(x, key >= tree[x].key);//每次插入把平衡操作压入栈中 92. }
93.}
94.
95.int del(int &p,int w) 96.{
97. if (tree[p].key==w || (tree[p].left==0 && w<tree[p].key) || (tree[p].right==0 && w>tree[p].key)) 98. {
99. int delnum=tree[p].key; 100. if (tree[p].left==0 || tree[p].right==0) p=tree[p].left+tree[p].right; 101. else tree[p].key=del(tree[p].left,INF); 102. return delnum; 103. }
104. if (w<tree[p].key) return del(tree[p].left,w); 105. else return del(tree[p].right,w); 106.}
107.
108.int remove(int &x,int key) 109.{
110. int d_key; 111. //if(!x) return 0; 112. tree[x].size --;
113. if((key == tree[x].key)||(key < tree[x].key && tree[x].left == 0) || 114. (key>tree[x].key && tree[x].right == 0))
115. {
116. d_key = tree[x].key;
117. if(tree[x].left && tree[x].right) 118. {
119. tree[x].key = remove(tree[x].left,tree[x].key+1);
120. }
121. else 122. {
123. x = tree[x].left + tree[x].right;
124. }
125. }
126. else if(key > tree[x].key) 127. d_key = remove(tree[x].right,key);
128. else if(key < tree[x].key) 129. d_key = remove(tree[x].left,key);
130. return d_key; 131.}
132.
133.int getmin() 134.{
135. int x; 136. for(x = root ; tree[x].left; x = tree[x].left); 137. return tree[x].key; 138.}
139.
140.int getmax() 141.{
142. int x; 143. for(x = root ; tree[x].right; x = tree[x].right); 144. return tree[x].key; 145.}
146.
147.int select(int &x,int k)//求第k小数 148.{
149. int r = tree[tree[x].left].size + 1; 150. if(r == k) return tree[x].key; 151. else if(r < k) return select(tree[x].right,k - r); 152. else return select(tree[x].left,k); 153.}
154.
155.int rank(int &x,int key)//求key排第几 156.{
157. if(key < tree[x].key) 158. return rank(tree[x].left,key); 159. else if(key > tree[x].key) 160. return rank(tree[x].right,key) + tree[tree[x].left].size + 1; 161. return tree[tree[x].left].size + 1; 162.}
163.
164.int pred(int &x,int y,int key)//前驱 小于 165.{
166. if(x == 0) return y; 167. if(tree[x].key < key) 168. return pred(tree[x].right,x,key); 169. else return pred(tree[x].left,y,key); 170.}
171.
172.int succ(int &x,int y,int key)//后继 大于 173.{
174. if(x == 0) return y; 175. if(tree[x].key > key) 176. return succ(tree[x].left,x,key); 177. else return succ(tree[x].right,y,key); 178.}
179.
180.void inorder(int &x) 181.{
182. if(x==0) return; 183. else 184. {
185. inorder(tree[x].left);
186. cout<<x<<" "<<tree[x].key<<" "<<" "<<tree[x].size<<" "<<tree[tree[x].left].key<<" "<<tree[tree[x].right].key<<endl; 187. inorder(tree[x].right);
188. }
189.}
190.
191.int main() 192.{
193. root = top = 0;
194. char ch; 195. int x,tmp; 196. while(scanf("%c %d",&ch,&x)) 197. {
198. switch(ch) 199. {
200. case 'I': 201. insert(root,x);
202. break; 203. case 'D': 204. remove(root,x);
205. break; 206. case 'K': 207. tmp=select(root,x);
208. printf("%d\n",tmp); 209. break; 210. case 'C': 211. printf("%d\n",rank(root,x)); 212. break; 213. case 'P': 214. tmp = pred(root,0,x);
215. printf("%d\n",tree[tmp].key); 216. break; 217. case 'S': 218. tmp = succ(root,0,x);
219. printf("%d\n",tree[tmp].key); 220. break; 221. case 'L': 222. inorder(root);
223. break; 224. }
225.
226. }
227. return 0; 228.}
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <ctime>
using namespace std;
#define LL long long
const int N = 10005;
const int INF=0x7FFFFFFF;
struct SBT
{
int key,left,right,size;
} tree[N];
int root,top;
void left_rot(int &x)
{
int y = tree[x].right;
tree[x].right = tree[y].left;
tree[y].left = x;
tree[y].size = tree[x].size;//转上去的节点数量为先前此处节点的size
tree[x].size = tree[tree[x].left].size + tree[tree[x].right].size + 1;
x = y;
}
void right_rot(int &x)
{
int y = tree[x].left;
tree[x].left = tree[y].right;
tree[y].right = x;
tree[y].size = tree[x].size;
tree[x].size = tree[tree[x].left].size + tree[tree[x].right].size + 1;
x = y;
}
void maintain(int &x,bool flag)
{
if(flag == false)//左边
{
if(tree[tree[tree[x].left].left].size > tree[tree[x].right].size)//左孩子的左子树大于右孩子
right_rot(x);
else if(tree[tree[tree[x].left].right].size > tree[tree[x].right].size)//右孩子的右子树大于右孩子
{
left_rot(tree[x].left);
right_rot(x);
}
else return;
}
else //右边
{
if(tree[tree[tree[x].right].right].size > tree[tree[x].left].size)//右孩子的右子树大于左孩子
left_rot(x);
else if(tree[tree[tree[x].right].left].size > tree[tree[x].left].size)//右孩子的左子树大于左孩子
{
right_rot(tree[x].right);
left_rot(x);
}
else return;
}
maintain(tree[x].left,false);
maintain(tree[x].right,true);
maintain(x,true);
maintain(x,false);
}
/*
*insert没有合并相同的元素，如果出现相同的元素则把它放到右子树上，这样能保证求第k小数的时候对相同元素也能正确
*/
void insert(int &x,int key)
{
if(x == 0)
{
x = ++top;
tree[x].left = tree[x].right = 0;
tree[x].size = 1;
tree[x].key = key;
}
else
{
tree[x].size ++;
if(key < tree[x].key) insert(tree[x].left,key);
else insert(tree[x].right,key);//相同元素插入到右子树中
maintain(x, key >= tree[x].key);//每次插入把平衡操作压入栈中
}
}
int del(int &p,int w)
{
if (tree[p].key==w || (tree[p].left==0 && w<tree[p].key) || (tree[p].right==0 && w>tree[p].key))
{
int delnum=tree[p].key;
if (tree[p].left==0 || tree[p].right==0) p=tree[p].left+tree[p].right;
else tree[p].key=del(tree[p].left,INF);
return delnum;
}
if (w<tree[p].key) return del(tree[p].left,w);
else return del(tree[p].right,w);
}
int remove(int &x,int key)
{
int d_key;
//if(!x) return 0;
tree[x].size --;
if((key == tree[x].key)||(key < tree[x].key && tree[x].left == 0) ||
(key>tree[x].key && tree[x].right == 0))
{
d_key = tree[x].key;
if(tree[x].left && tree[x].right)
{
tree[x].key = remove(tree[x].left,tree[x].key+1);
}
else
{
x = tree[x].left + tree[x].right;
}
}
else if(key > tree[x].key)
d_key = remove(tree[x].right,key);
else if(key < tree[x].key)
d_key = remove(tree[x].left,key);
return d_key;
}
int getmin()
{
int x;
for(x = root ; tree[x].left; x = tree[x].left);
return tree[x].key;
}
int getmax()
{
int x;
for(x = root ; tree[x].right; x = tree[x].right);
return tree[x].key;
}
int select(int &x,int k)//求第k小数
{
int r = tree[tree[x].left].size + 1;
if(r == k) return tree[x].key;
else if(r < k) return select(tree[x].right,k - r);
else return select(tree[x].left,k);
}
int rank(int &x,int key)//求key排第几
{
if(key < tree[x].key)
return rank(tree[x].left,key);
else if(key > tree[x].key)
return rank(tree[x].right,key) + tree[tree[x].left].size + 1;
return tree[tree[x].left].size + 1;
}
int pred(int &x,int y,int key)//前驱 小于
{
if(x == 0) return y;
if(tree[x].key < key)
return pred(tree[x].right,x,key);
else return pred(tree[x].left,y,key);
}
int succ(int &x,int y,int key)//后继 大于
{
if(x == 0) return y;
if(tree[x].key > key)
return succ(tree[x].left,x,key);
else return succ(tree[x].right,y,key);
}
void inorder(int &x)
{
if(x==0) return;
else
{
inorder(tree[x].left);
cout<<x<<" "<<tree[x].key<<" "<<" "<<tree[x].size<<" "<<tree[tree[x].left].key<<" "<<tree[tree[x].right].key<<endl;
inorder(tree[x].right);
}
}
int main()
{
root = top = 0;
char ch;
int x,tmp;
while(scanf("%c %d",&ch,&x))
{
switch(ch)
{
case 'I':
insert(root,x);
break;
case 'D':
remove(root,x);
break;
case 'K':
tmp=select(root,x);
printf("%d\n",tmp);
break;
case 'C':
printf("%d\n",rank(root,x));
break;
case 'P':
tmp = pred(root,0,x);
printf("%d\n",tree[tmp].key);
break;
case 'S':
tmp = succ(root,0,x);
printf("%d\n",tree[tmp].key);
break;
case 'L':
inorder(root);
break;
}
}
return 0;
}
总结：SBT，Treap，红黑树，都很类似，其中SBT和Treap代码很好写，SBT只需要正确理解旋转操作，和如何维护size域，另外就是Maintain函数，这个是重点，其他的操作都和BST一样了，SBT的高度是O(logn)，Maintain是O(1)，所有主要操作都是O(logn)。
最后还请大神解决下重复数据的remove操作函数如何写（具体见求第K小数下的注解），欢迎指教。