二叉搜索树（BST）-BINARY SEARCH TREE
DHWJHY
2024-04-12 17:44:58
## 前言-INTRODUCTION
我们曾经听说过很多 $\texttt{逆天、优雅}$ 的**平衡树**数据结构，包括 $\texttt{splay}$、$\texttt{treap}$、**红黑树** 等，然而，他们共同的基础是**二叉搜索树（$\texttt{Binary Search Tree-BST}$）**，于是，我们先从 $\texttt{BST}$ 开始讲起……
## 一、$\texttt{BST}$的定义-THE DIFNITION OF $\texttt{BST}$
给定一棵二叉树，树上的每个节点带有一个数值，即权值或关键码。其 $\texttt{BST}$ 性质指，对于任意一个节点：
1. 该节点的权值严格大于它的左子树中任意节点的权值。
2. 该节点的权值严格小于它的右子树中任意节点的权值。
如此的二叉树就是一棵**二叉搜索树（$\texttt{BST}$）**。
当然，它还有一个小小的性质是，其中序遍历为从小到大的排序。
## 二、$\texttt{BST}$ 的实现与维护-THE PRACTICE AND MAINTENANCE OF $\texttt{BST}$
本人因为比较懒，所以这里直接引用博客，感谢 Brilliant11001 的巨著，希望他能重新找到归属。
然而，小小蒟蒻觉得大佬的博客还是太 $\texttt{高端}$ 了，于是，这里有几个小小的补充，结合着看，应该不至于完全看不懂。
感谢大佬！“上帝保佑，但愿人人都能”看见这篇博客：[《二叉搜索树（BST）》](https://www.luogu.com/article/zqha49ef)
注意，以下代码**满足例题**，即输入应**受到题目限制**，否则**代码不保证正确性**。
- ### 建立-BUILDING
这里，我们用类似**前向星**的方式进行“指向”表示根叶关系，用**结构体**来把一个节点表示出来，于是便有定义如下：
```cpp
const int N = 1e6,inf = 0x7ffffff;
//一个代表无穷的inf
struct BST{
int ls,rs;//左右儿子的下标，全部初始化为0
int val;//权值或关键码
int num;//val出现的次数
int siz;//当前子树的节点个数
}a[N];
int cnt,root;
//与前向星类似的cnt
//root是根节点
```
大家可能注意到了一个`num`，一方面，BST 中不会出现权值相同的节点，另一方面，`num`的实际含义表示了节点的“虚实”，这将在后面的排名中起重大作用。
（主要是由于 同机房数学大佬 ~~就是下面那位~~ 被这玩意儿迷惑了，加以细说）
然而，为了方便查找、修改操作，我们初始化时需要两个边界——$+\infty$、$-\infty$ ，我们把 $-\infty$ 作为根节点，于是在最开始 $+\infty$ 便是根节点的右儿子，
```cpp
int renew(int u){//加入新节点
a[++cnt].val=u;
a[cnt].num++;
a[cnt].siz++;
return cnt;
}
void build(){
renew(-inf);
a[1].num--;a[1].siz--;//边界不需要计入数量
renew(inf);
a[2].num--;a[2].siz--;//边界不需要计入数量
root=1;//根节点更新
a[1].rs=2;//右儿子下标
}
```
- ### 查询-QUERY
查找 $x$ ，有可能有这个数，也可能没这个数。
从根节点开始，按如下操作遍历节点：
1. 当 $val$ == $x$ 时，返回当前节点下标；
2. 当 $val$ < $x$ 时，向右儿子 $\texttt{query}$ 。
3. 当 $val$ > $x$ 时，向做儿子 $\texttt{query}$ 。
4. 当当节点下标无意义时，返回 `0` 。
```cpp
int query(int p,int val){
if(!p) return 0;
if(val==a[p].val) return p;
if(val<a[p].val) return query(a[p].ls,val);
else return query(a[p].rs,val);
}
```
- ### 插入-INSERT
设要插入一个数 $x$ 。那么如下。
从根节点开始，按 $\texttt{BST}$ 的性质，一点一点往下遍历，
在 $\texttt{BST}$ 有可能已经有一个 $x$ ，所以当查找到 $x$ 的时候，直接返回；如果没有，那么比较大小，当当前节点 $val$ 大于 $x$ 时，向左儿子走，不管是否为空，反之向右儿子走，不管是否为空。
代码如下：
```cpp
void inserten(int &p,int val){
if(!p){//先看看下面的，再回来看
p=renew(val);
//上面的int &p是引用，当当前p为0时，就是此位置为空
//那么就更新当前空节点，引用修改父节点的子节点下标
return ;
}
if(val==a[p].val) return ;//假如有这个val，则无为返回
if(val<a[p].val) inserten(a[p].ls,val);//向左查找
else inserten(a[p].rs,val);//向右查找
}
```
- ### 求前驱/后继-ASK FOR PREMAXN OR SUFMINN
例如求 $x$ 的前驱后继。
$\bold{前驱}\texttt{pre-small bigger or lower-bound}$：在 $\texttt{BST}$ 中权值小于 $x$ 的前提下，权值最大的节点。
$\bold{后继}\texttt{suf-big smaller or upper-bound}$：在 $\texttt{BST}$ 中权值大于 $x$ 的前提下，权值最小的节点。
搜索查找嘛，有一种情况是，当 $\texttt{BST}$ 中有这个节点，那么只需要在它的左子树中一直往右节点找（查前驱）或在其右子树中一直往右节点找（查后继）。
```cpp
int get_pre(int p,int val){
int ans=1;//先假设答案为inf
p=root;//从根节点开始
while(p){
if(val==a[p].val){//假如有这个节点
if(a[p].l>0){//他有左儿子
p=a[p].l;
while(a[p].r) p=a[p].r;//使劲找右儿子
ans=p;
}
break;
}
if(a[p].val<val && a[ans].val<a[p].val) ans=p;//使劲更新
p=val<a[p].val?a[p].l:a[p].r;//左右进入
}
return ans;
}
int get_suf(int p,int val){
int ans=2;
p=root;
while(p){
if(val==a[p].val){
if(a[p].r>0){
p=a[p].r;
while(a[p].l) p=a[p].l;
ans=p;
}
break;
}
if(val<a[p].val && a[p].val<a[ans].val) ans=p;
p=val<a[p].val?a[p].l:a[p].r;
}
return ans;
}
```
注意，这么写无论 $\texttt{BST}$ 中有没有 $x$ ，都可以得到合理答案。
- ### 查询排名-QUERY FOR CERTAIN ONE'S RANKING
和查询类似，但要注意，小于 $x$ 的节点，不一定就在 $x$ 的左子树中，有可能 $x$ 作为某节点的右儿子（大于该节点），所以出现这种情况时还要加上这“某节点”的左子树及其本身。
策略是从根节点开始：
1. 当当前节点等于 $x$ 时，返回当前节点左子树节点个数。
2. 当当前节点小于 $x$ 时，若有右子树，则向右子树询问，并返回询问与当前节点的左子树节点个数、当前节点的和；若无右子树，则直接返回当前节点子树节点个数+1。
3. 当当前节点大于 $x$ 时，若有左子树，则向左子树询问；若无，说明 $x$ 为当前子树的最小权值，返回 1。
在 3 中，我们返回的 1 就恰好是“小于 $x$ 的个数+1”中的 1 ，2 中同理。
此时，前面形同虚设的`a[].num`就派上用场了，由于左右边界$\texttt{-inf}$、$\texttt{inf}$不计入 $\texttt{BST}$ ，所以他们的`a[1].num`、`a[2].num`为 $0$ ，而其他的作为 $1$，此时就很好处理了。
```cpp
int query_rank(int p,int val){
printf("query(%d,%d)\n",p,val);
if(val==a[p].val) return a[a[p].l].siz+1;
//如果有 x ，那么小于 x 的必定包含 x 的左子树
if(val>a[p].val){
//当 x 大于当前节点时，当前节点的左子树也是小于 x 的
if(a[p].r>0)//有右子树，节点及其左子树都小于 x
return a[a[p].l].siz+a[p].num+query_rank(a[p].r,val);
else//没有，当前节点所剩其下的节点都小于 x ，加 size
return a[p].siz+1;
}else{
//当 x 小于当前节点时，往左走，
if(a[p].l>0) return query_rank(a[p].l,val);
else return 1;//x 比子树中所有数都小，排名 0+1
}
}
```
- ### 排名查询-QUERY FOR SOMEONE RANKED CERTAINLY
查询排名为 $x$ 的节点权值为多少。
类似于上一个操作，我们尝试得到当前节点的排名，并不断比较，从而更进，然而，有一点特殊的是，我们需要判断当前节点是否为边界，因为当查找最后排名时，会先到边界，所以还要判断。
```cpp
int query(int p,int rank,int rate){
if(rank==rate+a[a[p].l].siz+a[p].num){
if(a[p].num) return a[p].val;
else return query(a[p].l,rank,rate);
}
if(rank<rate+a[a[p].l].siz+a[p].num){
return query(a[p].l,rank,rate);
}else{
return query(a[p].r,rank,rate+a[a[p].l].siz+a[p].num);
}
}
```
- ### 删除-DELETE
删除已有的 $x$ 。
先要找到 $x$ ，其次，当失去 $x$ 时，我们可以让 $x$ 的前驱或者后继来代替 $x$ 的位置，但我们仍需处理其前驱或后继的子树。
以后继替代 $x$ 为例。
当找到 $x$ 时，向其右子树寻找后继 $suf$ ，然而 $suf$ 一定没有左子树，所以用其右子树替代它，并且，用它把 $x$ 替换掉。
```cpp
void deleten(int &p,int val){
if(!p) return ;
if(val==a[p].val){
//无左无右下仍可
if(!a[p].l) p=a[p].r;//无左用右替
else if(!a[p].r) p=a[p].l;//无右用左替
else{
//有左有右
int suf=a[p].r;//找后继
while(a[suf].l) suf=a[suf].l;//直到无左子树
deleten(a[suf].r,a[suf].val);//用其右子树替其
//用suf替x
a[suf].l=a[p].l,a[suf].r=a[p].r;
p=suf;
}
return ;
}
//检索
if(val<a[p].val) deleten(a[p].l,val);
else deleten(a[p].r,val);
}
```
### 例题-EXAMPLE
有了上述操作（不包括删除、查询操作），我们就可以做这道题：[P5076 【深基16.例7】普通二叉树（简化版）](https://www.luogu.com.cn/problem/P5076)
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10,inf=0x7fffffff;
struct BST{
int l,r;
int val;
int num;
int siz;
}a[N];
int cnt,root;
int q;
void couten();
int renew(int u){
a[++cnt].val=u;
a[cnt].num++;
a[cnt].siz++;
return cnt;
}
void build(){
renew(-inf);
a[1].num--;a[1].siz--;
renew(inf);
a[2].num--;a[2].siz--;
root=1,a[1].r=2;
}
int query_rank(int p,int val){
// printf("query(%d,%d)\n",p,val);
if(val==a[p].val) return a[a[p].l].siz+1;
//如果有 x ，那么小于 x 的必定包含 x 的左子树
if(val>a[p].val){
//当 x 大于当前节点时，当前节点的左子树也是小于 x 的
if(a[p].r>0)//有右子树，节点及其左子树都小于 x
return a[a[p].l].siz+a[p].num+query_rank(a[p].r,val);
else
return a[p].siz+1;
}else{
if(a[p].l>0) return query_rank(a[p].l,val);
else return 1;
}
}
void inserten(int &p,int val){
if(!p){//先看看下面的，再回来看
p=renew(val);
//上面的int &p是引用，当当前p为0时，就是此位置为空
//那么就更新当前空节点，引用修改父节点的子节点下标
return ;
}
a[p].siz++;
if(val==a[p].val) return ;//假如有这个val，则无为返回
if(val<a[p].val) inserten(a[p].l,val);//向左查找
else inserten(a[p].r,val);//向右查找
}
int get_suf(int p,int val){
int ans=2;
p=root;
while(p){
if(val==a[p].val){
if(a[p].r>0){
p=a[p].r;
while(a[p].l) p=a[p].l;
ans=p;
}
break;
}
if(val<a[p].val && a[p].val<a[ans].val) ans=p;
p=val<a[p].val?a[p].l:a[p].r;
}
return ans;
}
int get_pre(int p,int val){
int ans=1;//先假设答案为inf
p=root;//从根节点开始
while(p){
if(val==a[p].val){//假如有这个节点
if(a[p].l>0){//他有左儿子
p=a[p].l;
while(a[p].r) p=a[p].r;//使劲找右儿子
ans=p;
}
break;
}
if(a[p].val<val && a[ans].val<a[p].val) ans=p;//使劲更新
p=val<a[p].val?a[p].l:a[p].r;//左右进入
}
return ans;
}
int query(int p,int rank,int rate){
if(rank==rate+a[a[p].l].siz+a[p].num){
if(a[p].num) return a[p].val;
else return query(a[p].l,rank,rate);
}
if(rank<rate+a[a[p].l].siz+a[p].num){
return query(a[p].l,rank,rate);
}else{
return query(a[p].r,rank,rate+a[a[p].l].siz+a[p].num);
}
}
int main(){
build();
scanf("%d",&q);
while(q--){
int op,x;
scanf("%d%d",&op,&x);
if(op==5){
inserten(root,x);
}else if(op==4){
printf("%d\n",a[get_suf(root,x)].val);
}else if(op==3){
printf("%d\n",a[get_pre(root,x)].val);
}else if(op==1){
printf("%d\n",query_rank(root,x));
}else{
printf("%d\n",query(root,x,0));
}
}
return 0;
}
void couten(){
vector<int> s;
s.push_back(root);
while(!s.empty()){
vector<int> g;
for(int i=0;i<s.size();i++){
BST j=a[s[i]];
printf("%d:%d(%d)[%d,%d] ",s[i],j.val,j.siz,j.l,j.r);
if(j.l) g.push_back(j.l);
if(j.r) g.push_back(j.r);
}
s=g;
puts("");
}
}
```
再打了一遍：[模板（最新款——马蜂优良、定义明确）](https://www.luogu.com.cn/article/67o1dbix)。
## 不如STL……-$\texttt{STL}$ BETTER
[大佬救我](https://www.luogu.com/article/t00def0c)
$\bold{谨记}$，使用 $\texttt{STL}$ 时一定要先初始化两个哨兵（$-\infty$、$+\infty$），防止在只有一个数时找一个小于这个数的数的前继时迭代器越界。
## 三、特异性进化-EVOLUTION FOR SPECIFICTY
显然，满足 $\texttt{BST}$ 性质且中序遍历相同的二叉查找树不唯一，如此，有可能树的深度达到 $O(\frac{1}{2}n)$ ，从而被卡成 $O(n^2)$ 的时间复杂度，所以，我们想要把中序遍历相同的二叉树确定下来，确定成深度维持在 $O(\log n)$ 的级别。
于是，下一代数据结构登场——[树堆-TREAP](https://www.luogu.com.cn/article/ugcagegy)。