二叉搜索树（BST）-BINARY SEARCH TREE

· · 科技·工程

前言-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）》

注意，以下代码满足例题，即输入应受到题目限制，否则代码不保证正确性。

这里，我们用类似前向星的方式进行“指向”表示根叶关系，用结构体来把一个节点表示出来，于是便有定义如下：

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 便是根节点的右儿子，

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;//右儿子下标 
}

查找 x ，有可能有这个数，也可能没这个数。

从根节点开始，按如下操作遍历节点：

  1. 当 val == x 时，返回当前节点下标；
  2. 当 val < x 时，向右儿子 \texttt{query} 。
  3. 当 val > x 时，向做儿子 \texttt{query} 。
  4. 当当节点下标无意义时，返回 0 。
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);
}

设要插入一个数 x 。那么如下。

从根节点开始，按 \texttt{BST} 的性质，一点一点往下遍历，

在 \texttt{BST} 有可能已经有一个 x ，所以当查找到 x 的时候，直接返回；如果没有，那么比较大小，当当前节点 val 大于 x 时，向左儿子走，不管是否为空，反之向右儿子走，不管是否为空。

代码如下：

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);//向右查找 
}

例如求 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)。