关于二叉查找树的一些事儿（bst详解，平衡树入门）
ztz11
2018-07-11 09:06:08
最近刚学了平衡树，然后突发奇想写几篇博客纪念一下，可能由于是刚学的缘故，还有点儿生疏，望大家海涵
平衡树是一种数据结构，可以处理数据的增、删、查、改。说到平衡树，就不得不从基础说起，而基础，正是二叉查找树（Binary Search Tree, BST）。
## 什么是二叉查找树？？
大家观察一下下面的这棵二叉树
相信大家一眼就能发现，这棵树从左往右是递增的（也就是右儿子大于根节点大于左儿子）
那么这样的一棵树有什么用呢？
就比如说图上的这个数列 `12 10 15 6 13 19 2 8 14 22`
如果你想找第n大的数，你明显需要冒泡排序或快速排序，最坏复杂度分别为：$O（n^2/2）$，O（nlogn）；
如果数列再改大一下，而你每次都要跑这么高的复杂度，电脑累死了
但如果你用上图这棵树，根据他（右儿子>自己>左儿子）的特性，可以在期望复杂度O（logn）的时间内查出一个数据
同时修改也变得简单，O（logn）的时间查找位置，O（1）的时间连边
## 首先先看看插入
以7为例，我们从根节点开始
很明显，根节点大于7，那么我把7下放到当前的左儿子
还是大，怎么办？继续下放到当前的左儿子
这次是小了，放当前的右儿子
右儿子又大了，我们打算把他往当前的左儿子上放
但是，8这里并没有左儿子
可以恭喜了，7终于找到了自己的位置，我们现在新建一个结点，连一条边，使他变为8的左儿子
当然，有重复时也很好办，在该结点加一个数量标记，告诉他有几个即可
### 插入的代码：
```cpp
//这篇文章中，wz表示当前节点的编号，
//v和val表示得是值，rank表示排名，
//size表示当前节点的子树大小和自己的大小的和，
//cnt表示当前节点代表的数有几个
//ls是左儿子，rs是右儿子
void add(int wz, int v)
{
x[wz].size++;
if (x[wz].val == v)
{
x[wz].cnt++;
return;
}
if (x[wz].val > v)
{
if (x[wz].ls != 0)
{
add(x[wz].ls, v);
}
else
{
bnt++;
x[bnt].val = v;
x[bnt].size = 1;
x[bnt].cnt = 1;
x[wz].ls = bnt;
}
}
else
{
if (x[wz].rs != 0)
{
add(x[wz].rs, v);
}
else
{
bnt++;
x[bnt].val = v;
x[bnt].size = 1;
x[bnt].cnt = 1;
x[wz].rs = bnt;
}
}
}
```
## 然后是删除
删除其实可以通过改变该数字连的边来做到，但这我放到讲treap时再说，这个图的删除可以利用cnt标记，找到这个数后cnt--即可，如果为cnt=0，就表示此时已经没有这个数；
同时，cnt的改变不会影响大小关系，所以这棵树还是一定满足bst的性质的
## 真正的重头戏————查询
不得不说bst的功能还是很强大，常规的也可以支持找前驱，找后继，按值查排名和按排名查值，下面我一个一个来说
### 1. 找前驱和后继：
#### 先说前驱
根据定义，x的前驱是小于x的最大的数，所以前驱一定比x小，前驱就有可能在x的左子树或x的左父亲里
这里以9为例
我们知道前驱一定比9小，那么从根开始
我们发现根比9大，不满足前驱小于本身的条件，那么根据二叉查找树的性质，我们找他的左子树
发现还是大，找他的左子树
这回终于碰上一个比9小的了，我们把他记下来，为了确保6是最小的，我们要看他的右子树
这回是8，还是比9小，我们更新一下
在我们想向右跑时，发现当前已经没有右子树了，说明不可能有别的满足条件的，所以答案是8
总结一下，其实找前驱，就是从根节点开始，递归子树，如果当前节点大于你要找的数，就找他的左子树，反之找他的右子树，直到没有可以找的为止；
#### 至于后继：
其实道理一样，不过是反过来，这里我就不多说了，大家自己手码
### 代码:
找前驱：
```cpp
int GetPre(int wz, int val, int ans)
{
if (x[wz].val >= val)
{
if (x[wz].ls == 0)
{
return ans;
}
else
{
return GetPre(x[wz].ls, val, ans);
}
}
else
{
if (x[wz].rs == 0)
{
if (x[wz].val < val)
{
return x[wz].val;
}
else
{
return ans;
}
}
if (x[wz].cnt != 0)
{
return GetPre(x[wz].rs, val, x[wz].val);
}
else
{
return GetPre(x[wz].rs, val, ans);
}
}
}
```
#### 找后继：
```cpp
int GetNext(int wz, int val, int ans)
{
if (x[wz].val <= val)
{
if (x[wz].rs == 0)
{
return ans;
}
else
{
return GetNext(x[wz].rs, val, ans);
}
}
else
{
if (x[wz].ls == 0)
{
if (x[wz].val > val)
{
return x[wz].val;
}
else
{
return ans;
}
}
if (x[wz].cnt != 0)
{
return GetNext(x[wz].ls, val, x[wz].val);
}
else
{
return GetNext(x[wz].ls, val, ans);
}
}
}
```
### 2. 按排名找值和按值找排名
#### 按排名找值：
相信大家在刚才的代码中发现了不和谐的东西——size，现在他就要派上用场了
还是刚才的图，我要找排名第7的数，怎么办呢？
看图（绿色的是子树及本身的大小）
根据bst的性质，右面的元素严格大于左面的元素，所以右面的排名也大于左面的，自然，排名为n的数就是第n靠左的节点
在这里我以n=7为例
我还是从根开始
因为root的左子树的大小为5，说明root本节点及他的左子树大小为6，而我要找的排名为7，显然不足，于是我可以假装把树切了一半（如图），然后查询新树中排名第1的数
因为我们知道5的左子树大小为2，而2+1=3>1，所以我们找他的左子树（如图）
13没有左子树，所以他在该子树中的排名为1，满足，所以答案为13。
由上面的例子可以得出，我们在按排名查值时，当前位置的排名为他左子树的大小加上自己cnt（该节点有几个）的大小，如果当前排名小于要找的排名，就去右子树找，并更新要找的排名，反之先自查，不行再去左子树找
### 看代码：
```cpp
int GetValByRank(int wz, int rank)
{
if (wz == 0)
{
return INF;
}
if (x[x[wz].ls].size >= rank)
{
return GetValByRank(x[wz].ls, rank);
}
if (x[x[wz].ls].size + x[wz].cnt >= rank)
{
return x[wz].val;
}
return GetValByRank(x[wz].rs, rank - x[x[wz].ls].size - x[wz].cnt);
}
```
#### 按值找排名：
这个其实和按排名查值是一样的，只不过变量从排名成了值，但其实也很简单，我们以13为例：
首先们从根开始（蓝色为当前数的总数）
12显然是小于13的，所以我们找12的右子树，同时我们已知的小于13的数有了6个
15比13大，所以我们找他的左子树，比他小的还是6个
我们发现15的左儿子的值为13，到达终点。这时我们知道他的排名是所有比他小的数+1，比他小的有路上的6个，而他的左子树大小为0，所以排名为6+0+1=7
总结一下，按值找排名时，从根开始，如果该位置的值小于要查询的值，就找他的右子树，同时记住他左子树的大小，如果小于，就查询他的左子树，直到大小相等，他的排名就是该点左子树的大小加上一路上比他小的节点个数再加上1
### 看代码：
```cpp
int GetRankByVal(int wz,int val)
{
if(wz==0)
{
return 0;
}
if(val==x[wz].val)
{
return x[x[wz].ls].size+1;
}
if(val<x[wz].val)
{
return GetRankByVal(x[wz].ls,val);
}
return GetRankByVal(x[wz].rs,val)+x[x[wz].ls].size+x[wz].cnt;
}
```
有关二叉查找树的内容暂时告一段落，这个数据结构相对较优，但在遇到下图时会被卡成O（n）。所以一些优化还是必不可少的，过一段时间我会继续写下去，给大家带来关于treap，splay和替罪羊树的一些事儿
## 几个解答：
1.当初我写这篇之前还不太会写平衡树，于是拿着@czq大佬的代码研究，我一个一个地自己重构函数，然后加进@czq大佬的代码里改，所以我不敢改函数名，因此沿用了@czq大佬的函数名。后来会写了，但习惯已经养成，也就懒得再改，于是就沿用到博客里了。~~其实就是一个字懒~~
2.如果大家认为我的码风有锅，可以将代码复制后放到DEV里，ctrl+shift+a格式化代码，看起来可能比较舒服。
安利一发博客：[ztz11](https://www.cnblogs.com/ztz11/p/9296584.html)