SBT

缘起

关于BST，我们已经介绍很多了. 尤其是针对他的最坏O(N)的弊病, 人们给出了AVL、Splay、红黑树等解决方案. 但是avl和红黑树较为复杂，实际算法竞赛的时候用的不多. 一般用的比较多的是splay、sbt、treap （所谓三大平衡树），这里讲解【1】中介绍的SBT. 它对于平衡的刻画既不是AVL的子树深度，亦不是红黑树的路径上的黑色节点的个数. 而是子树节点个数.

SBT的定义是

  1. 它是BST

  2. 以任意叔叔节点为根节点的子树的节点个数>=以侄子节点为根节点的子树的节点个数.

    ​ 图1

    即s[ A], s[B] <= s[R] && s[C ], s[D] <= s[L]

分析

先上代码, 后面分析算法.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
#include "stdafx.h"
#include <iostream>
#include <cstdlib>
#include <ctime>
#pragma warning(disable:4996)
//#define LOCAL
using namespace std;

const int N = 10005, INF = 0x3f3f3f3f;

struct SBTNode
{
	int left, right, size, key; // 左孩子在数组中的索引, 右孩子在数组中的索引, 以其为根的树的大小, 数据值
} sbt[N]; // 0 不用于存储数据, sbt[x].left(right)=0表示sbt[x]没有左子树(右子树)

int tot, root; // tot是总节点的个数, root是根节点的索引

void leftrotate(int &x) // sbt[x]为根的子树进行左旋， x为左旋之后的根节点索引, 参见图2, 对于BST而言，旋转操作是保持BST的
{
	int r = sbt[x].right; // 即y
	sbt[r].size=sbt[x].size; // 更新大小
	sbt[x].size = sbt[sbt[r].left].size+ sbt[sbt[x].left].size+1; // 更新大小, 1代表sbt[x]自己
	sbt[x].right = sbt[r].left;
	sbt[r].left = x;
	x = r; // 更改根节点索引, 试想一下，传入的是某个节点的left或者right
}

void rightrotate(int &x) // 右旋，参见图2
{
	int l = sbt[x].left;
	sbt[l].size=sbt[x].size;
	sbt[x].size = sbt[sbt[l].right].size+ sbt[sbt[x].right].size+1;
	sbt[x].left = sbt[l].right;
	sbt[l].right = x;
	x = l; 
}

// maintain操作的均摊时间是 O(1)
void maintain(int &x, bool flag) // 维护sbt[x]为根节点的子树(这里x是图1中的T,即爷爷节点)使之依旧满足SBT的定义（因为插入或者删除导致树不再满足SBT定义, 所以要maintain） 
{ // flag=false只用考虑左侄子(即左兄弟的孩子(有两个,偏左的叫做左左侄子,另一个叫做左右侄子))的size>右叔叔的size,flag=true只用考虑右侄子的size>左叔叔的size.maintain操作的均摊时间是O(1),所以maintain是极为有效率的过程
	if (!flag) // 如果左侄子节点个数 > 右叔叔的节点个数
	{
		if (sbt[sbt[x].left].left && sbt[sbt[sbt[x].left].left].size > sbt[sbt[x].right].size) // 如果是左左侄子的节点个数>右叔叔的节点个数（即图1中A的节点个数>R的节点个数）
		{
			rightrotate(x); // 做一次x的右旋
		}
		else if(sbt[sbt[x].left].right && sbt[sbt[sbt[x].left].right].size > sbt[sbt[x].right].size) // 如果是左右侄子的节点个数> 右叔叔的节点个数(即图1中B节点的个数>R节点的个数)
		{
			leftrotate(sbt[x].left); // 先做一次L的左旋
			rightrotate(x); // 再做一次T的右旋
		}
		else return; // 左侄子很安分, 没有搞事情, maintain算法结束
	}
	else // 如果右侄子的节点个数 > 左叔叔的节点个数，这种情况下是完全对称的.
	{
		if (sbt[sbt[sbt[x].right].right].size > sbt[sbt[x].left].size)
		{
			leftrotate(x);
		}
		else if(sbt[sbt[sbt[x].right].left].size > sbt[sbt[x].left].size)
		{
			rightrotate(sbt[x].right);
			leftrotate(x); 
		}
		else return;
	}
	maintain(sbt[x].right, true); // 这是为了防止上层节点违反SBT定义. 关于maintain的原理的清晰解释，见下面的分析
	maintain(sbt[x].left, false);
	maintain(x, true);
	maintain(x, false);
}

void insert(int &x, int key) // 往以x为根节点的sbt中插入关键值key, 注意，这里的处理并没有说重复值就不能加入，而是将其丢到了右子树中去. 这样保证了求第k小数的时候（kth问题）对相同元素也能正确
{
	if (!x) // 如果插入的树是空树或者已经找到了叶子节点, 则新建一个根节点即可
	{
		x = ++tot;
		sbt[x].left = 0;
		sbt[x].right = 0;
		sbt[x].size = 1;
		sbt[x].key = key;
		return;
	}
	sbt[x].size++;
	if (key < sbt[x].key) // 严格小于的话，就丢到左子树
	{
		insert(sbt[x].left, key);
	}
	else // 相等或者大于的话，就丢到右子树
	{
		insert(sbt[x].right, key);
	}
	// 插入之后一定要维护
	maintain(x, key >= sbt[x].key); // 如果key被丢到右子树去的话,则可能出现的情况是右侄子>左叔叔. 所以是true, 如果丢到左子树上去，则可能出现的事情是左子树>右叔叔, 所以为false.
}

int del_pre(int &x, int key) // 在以x为根节点的SBT子树中删除key值, 这里采用的是前驱替换的方法进行删除的. 如果整棵SBT中没有这个值的话, 就删除搜索到的最后的数值
{
	if (!x) return INF; // 如果是空树，返回INF， 注意，只可能是空树才会发生 x=0的情形, 因为你看一下递归的入口，是  del_pre(sbt[x].left, key+1), 而前提是 sbt[x].left 和 sbt[x].right都不是0
	sbt[x].size--;
	int del_key; // 要删除的值
	if (key == sbt[x].key || (key < sbt[x].key && !sbt[x].left) || (key>sbt[x].key && !sbt[x].right)) // 如果当前位置恰是要删除的值或者准备往左走，但是左边没路了, 或者准备往右走，但是右边没路了, 则可以得到要删除的值
	{
		del_key = sbt[x].key;
		if (sbt[x].left && sbt[x].right) // 如果既有左子树 又有 右子树的话, 这里采用前驱替换法删除sbt[x]节点
		{
			sbt[x].key = del_pre(sbt[x].left, key+1); // 不要觉得奇怪, 左子树都是 <=key的, 这里使用key+1是一定搜不到的, 递归的最后结果就是找到了叶子. <key+1的最大叶子之后，将叶子删除(即 x = sbt[x].left+ sbt[x].right) 并且得到了返回的需要删除的值
		}
		else
		{
			x = sbt[x].left+ sbt[x].right; // 否则, sbt[x].left或者sbt[x].right 中至少一个为0，则x是其中一个, 那么这样就完成了嫁接.（删除掉了x）
		}
	}
	else // 否则的话,即需要往左走左边有路（此时右边不一定右路），需要往右走，右边也有路（此时左边不一定右路）， 就要继续跑左子树或者右子树上去递归删除
	{
		del_key = del_pre(key < sbt[x].key? sbt[x].left:sbt[x].right, key);
	}
	//maintain(x, false); // 最后要调整根节点使得重新成为一棵sbt,但是CQF论文中指出,其实没有必要(所以SBT的删除就只是普通的BST删除而已),因为在删除之前，可以保证整棵树是一棵SBT。当删除之后，虽然不能保证这棵树还是SBT，但是这时整棵树的最大深度并没有改变（因为你总是用替换），所以时间复杂度也不会增加（不论你后面做Delete还是Insert还是所有其他操作,如果insert的话,还会maintain的）。这时，maintain就显得是多余的了。
	//maintain(x, true); // 所以CQF论文上说加了这两句maintain代码的叫做标准删除(所谓标准的意思就是删除之后保证仍旧是sbt,但分析过了,没必要)CQF论文中说"它还是一棵高度为 O(logn)的 BST。这里的 n是所有插入结点的个数，而不是当前结点的个数！"是因为maintain只用在Insert中而在Delete中没用(如果Delete中也用的话,n就是当前节点的个数)
	return del_key;
}

int del_post(int &x, int key) // 删除的后继替换版本，删除的是x为根的子树上key值的节点
{
	if (!x) return INF;
	sbt[x].size--;
	int del_key;
	if (key == sbt[x].key || (key < sbt[x].key && !sbt[x].left) || (key>sbt[x].key && !sbt[x].right))
	{
		del_key = sbt[x].key;
		if (sbt[x].left && sbt[x].right)
		{
			sbt[x].key = del_post(sbt[x].right, key-1); // 用key-1 在右子树上搜索
		}
		else
		{
			x = sbt[x].left+ sbt[x].right; 
		}
	}
	else
	{
		del_key = del_post(key < sbt[x].key? sbt[x].left:sbt[x].right, key);
	}
	return del_key;
}

int getmin(int x) // 获取以node[x]为根的子树的最小值
{
	while(sbt[x].left)x = sbt[x].left;
	return sbt[x].key;
}

int getmax(int x) // 获取以node[x]为根的子树的最大值
{
	while(sbt[x].right)x = sbt[x].right;
	return sbt[x].key;
}

int pred(int x, int y, int key) // 返回<key的最大的数。y记录要返回的东西,x是探路者(即sbt[x]是当前节点)
{
	if (!x) return sbt[y].key; // 如果探空了，那就是当前节点
	if (key > sbt[x].key) return pred(sbt[x].right, x ,key); // 到右子树上探索
	return pred(sbt[x].left, y, key); // 因为sbt[x].key>=key,所以前驱在左子树上.并且sbt[x]也不是前驱(因为sbt[x].key>=key),所以前驱仍设定为y, 你其实可以想象一个极端情形——key很小，要一路向左,则y伊始入参是0, 则一直是0, 则最后返回 sbt[0].key, 其实是对的, 因为树中压根就没有<key的节点
} //使用方法:pred(root,0,key),查找整棵树中比key小的最大的数

int succ(int x, int y, int key) // 返回>key的最小的数
{
	if (!x) return sbt[y].key;
	if (key < sbt[x].key) return succ(sbt[x].left,x, key);
	return succ(sbt[x].right, y, key); // 因为 sbt[x].key<=key, 所以x不是要返回的, 所以y不变
}//使用方法:succ(root,0,key),查找整棵树中比key大的最小的数

int kth(int x, int k) // 求从小到大排名第k的数字
{
	int t = sbt[sbt[x].left].size+1; // 求sbt[x].key的排名(size域使得我们可以在O(1)时间内完成排名的计算，可见非常的有用)
	if (t == k) return sbt[x].key;
	if (t<k) return kth(sbt[x].right, k-t); // 跑到右子树上去求排名第 k-t 的
	return kth(sbt[x].left, k);// 跑到左子树上去求排名第k的
}

int _rank(int x,int key) // 返回key在以x为根的树中的排名(时髦点就叫做求秩),也就是比key小的那棵树的大小(size域)加一。
{
	if (!x) return 0; // 如果叶子再递归一层的话, 就返回0
	if (sbt[x].key == key) return sbt[sbt[x].left].size+1;
	if (sbt[x].key > key) return _rank(sbt[x].left, key); // 跑到左子树上去
	else return _rank(sbt[x].right, key) + sbt[sbt[x].left].size+1; // 跑到右子树上去
}


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	int a[] = {12, 1, 9, 2, 0, 11, 7, 19, 4, 15, 18};
	for (int i = 0; i<sizeof(a)/sizeof(int); i++)
	{
		insert(root, a[i]);
	}
	printf("最大是%d\n", getmax(root));
	printf("最小是%d\n", getmin(root));
	printf("<17的最大数是%d\n", pred(root, 0, 17));
	printf(">17的最小数是%d\n", succ(root, 0, 17));
	printf("排名第7数是%d\n", kth(root, 7));
	printf("17在树中的排名是%d\n", _rank(root,17));
	return 0;
}

maintain操作是SBT树操作的核心, 正是因为它的存在，所以SBT的很多接口可以维持在O(logn)的运行速度. 但是虽然maintain操作的代码比较简短，但是其实并不很明显可以看懂. 下面来详细解释一下.

首先maintain发生的契机是插入或者删除一个节点. 导致SBT的定义第二条不被满足. 既然不满足，所以只有左侄子>右叔叔 或者 右侄子>左叔叔 两种违反的情况. flag为false对应前者，flag为true对应后者. main(int &x)的目的是维护图1中的T=x的树，使得以T为根节点的子树满足SBT(即 L节点个数>=C,D；R节点的个数>=A,B)

不难想象, 这两种情况是完全对称的. 所以只需要考虑前者怎么搞就行了.

前者也要分成

  1. 左左侄子>右叔叔（但是左右侄子<=右叔叔）
  2. 左右侄子>右叔叔（但是左左侄子<=右叔叔）

两种情况（注意，一个一个插入节点的时候不会同时左左侄子>右叔叔并且左右侄子>右叔叔的）. 对于左左侄子>右叔叔的情形（即图1中A>R）. 我们做一次x(x就是图1中的T，右旋之后，x是下图的L)的右旋即可. 即图1中做T的右旋，变成下面的样子.

​ 图3

如果变成这个样子，我们要切记，插入点是A的子树，并且插入之前，都是满足SBT的定义的. 右旋之后, 因为之前A>R, 所以右旋之后, A和他的右右侄子是不会违反SBT定义的. 那么A和他的右左侄子B会不会违反SBT定义呢? 不会，因为图1中，A>R>=B,所以A>B . 综上所述, A和他的右侄子们是不会违背SBT的定义. 而且R也不会违反SBT. 同理 T和A的孩子们也不会违反SBT的定义(这是因为A和B是满足SBT的. 所以B>A的左右孩子. 所以T就更大于A的左右孩子了. 所以A和T都不会违反SBT的定义. ) 那么B和R呢? R和B的孩子不会违反SBT定义的(这是因为图1满足SBT定义.) 注意，不需要考虑根节点会不会影响上层, 即不需要考虑下图中对L的maintain使得xxx和L之间不满足SBT，

​ 图4

因为mantain(int &x)仅仅考虑的是以x为根节点的子树是否满足SBT。所谓以x为根节点的子树是否满足SBT指的是图1中（T就是x）满足

s[ A], s[B] <= s[R] && s[C ], s[D] <= s[L]

综上所述, 只可能B和C/D会违反SBT，所以需要(x就是L，所以下面的代码就是维护以T为根的子树（x是L节点）,而maintain算法的入参的x就是树根（即爷爷节点）)

1
maintain(sbt[x].right, true);

咣咣咣一顿维护之后, 以T为根的子树变化很大, 注意，这种维护不会影响以A为根的子树的. 所以以图3中的以A为根节点的子树不会变化. 所以其实对于本情形（即 左左侄子>右叔叔）代码的

1
maintain(sbt[x].left, false);

是没必要的. 但是后面就会知道，这一行代码是对情形2（左右侄子>右叔叔）用的. 但是对于左左侄子>右叔叔写了这行代码也没关系，因为A插入了一个节点导致与R违反SBT定义已经在上面的右旋中解决了. 以A为根节点的子树自身不会因为插入一个节点而违反SBT的（要用递归的眼光看，能到商讨A和R之间的违背SBT关系这一地步，就说说明本身A已经满足SBT定义了）. 所以 maintain(sbt[x].left, false); 对于A子树而言是空操作. 写了也没关系.

最后因为以T为根节点的子树进行maintain一波之后，变化可能非常大以及不可预料. 所以A和maintain一波之后的子树的孩子以及main一波之后的子树和A的孩子都有可能违背SBT定义, 即A与下图T’ 的孩子, T’与A的孩子之间都可能违背SBT定义, 所以最后要来

1
2
maintain(x, true);
maintain(x, false);

这两行代码对L进行维护.

​ 图5

下面我们来考虑情形2

左右侄子>右叔叔

即下图中B>R(其他地方不会违背SBT)

​ 图6

我们首先进行L绕B的一次左旋.

​ 图7

再做一次T绕B的右旋(最后maintain函数的入参x变成了B)

​ 图8

旋完之后，我们同情形1那样开始考虑哪些节点会违背SBT定义. 首先，原本的B>R 几乎已经没有了作用，因为经过了上面两次旋转，树的结构发生了很大的改变. 但是幸运的是 A、E、F（E和F遵守SBT依旧要以递归的眼光来看，来理解，因为插入节点在B，所以不是在E插入就是在F插入）、R、C、D本身都是SBT. 即上图中底部的子树都是没有违背SBT的. 此时x是B节点. 所以可能违背SBT的是L和T的孩子们，或者T与L的孩子们，或者A与E的孩子们，或者E与A的孩子们，或者F与R的孩子们，或者R与F的孩子们. 我们逐一来考察. 注意考察的顺序需要是从底部到顶部，因为底部调整之后可能会影响顶部的. 所以先分析L、T和A、E、F、R之间会不会违反SBT是不行的（这是表明是否要maintain(x), x是B）. 一定要先分析A与E，F与R起.

  1. A与E的孩子们会违反SBT 吗? 不会，因为图6可以知道A>E, 所以A更加大于E的孩子.
  2. E与A的孩子们会违反SBT吗? 可能会的. 综合1和2, 我们需要 maintain(sbt[x].left, false); 其中 sbt[x].left=L
  3. F与C、D会违反SBT吗? 可能会
  4. R与F的孩子会违反SBT吗? 不会，根据图6，B比R多1（想象一下是一个一个的增加节点，所以违背的时候一定是恰好大1），所以R=E+F, 所以R>=F. 综合 3和4，我们需要 maintain(sbt[x].right, true); 其中sbt[x].right=T.

综上，我们需要maintain(L)和maintain(T), 维护之后, L和T的结构可能发生巨变(所以一开始你分析L（T）和T（L）的孩子之间会不会违反SBT是没意义的), 所以还必须要维护B（根节点），即下面四行代码都是不可以省略的.

1
2
3
4
maintain(sbt[x].right, true);
maintain(sbt[x].left, false);
maintain(x, true);
maintain(x, false);

综上, maintain函数的原理我们解释清楚了. 而SBT中除了maintain之外的接口都比较显然. 就不赘述了.

参考

【1】陈启峰 WC2007 论文 数据结构 Size Balanced Tree

附录

​ 图2