基本BST

admin

BST是一种特殊的二叉树，对于每一个结点，若有左儿子的话，左儿子的值比它小，若有右儿子的话，右儿子的值比大。若是中序遍历这棵树，将得到一个排好序的序列。
一般的维护顺序结构若是在数组中实现，那么删除，插入将会带来很大的移动操作，时间复杂度不好，要是在BST上操作，那么插入和删除将会更加高效，至于查找，数组和BST差距不大。
假设一个BST如下，若是中序遍历，将得到1,2,3,4,5,6,7,8。

admin

在我们上面最简BST的基础上，需要加上4个操作，我们先不说如何建高级的树，先来看看这四个操作在我们的最简BST里面如何实现，尽管这样做会被卡超时，但是好理解：
一、查询x的排名，排名定义为比x小的数+1，那么我们只要求出比x小的数的个数就是
我们从根节点开始，比较a(rt).val和x
1 a(rt).val==x 那么所有左子树里面所有节点的cnt加起来就是
2 a(rt).val<x说明只有rt的左子树里面的节点才有可能，rt=a(rt).ls，递归
3  a(rt).val>x 说明除了rt节点和rt的左子树里面所有的节点都需要统计外，还需要加上a(rt).rs里面<x的数，先统计前面，在递归统计第三项
为了加快速度，类似线段树，在AA结构体里面加上一个附加sz域，表示我这个子树包含我下一共有多少个节点，这样统计的速度会加快，但是每次插入，删除的时候需要更新相关节点的sz域。

二、查询排名为 x 的数，这个和上面那个有点相同点，假设目前rt的左儿子有al个节点，右儿子有ar个节点，自己有cnt个节点，那么可以很容易想到：
1、al+1<=x && x<=al+cnt 那么所求就是a(rt).val
2、al+1<x那么此数应该在左儿子里，递归
3、al+a[rt].cnt<x 右儿子里去找排名为x-al-cnt的


三、求 x 的前驱(前驱定义为小于 x，且最大的数)
四、求 x 的后继(后继定义为大于 x，且最小的数)
两个的思路差不多，以三为例吧，设当前根为rt，比较a(rt)和x
0、rt==0，找不到，为了便捷，返回-inf，这里注意！
1、a (rt)>=x 说明在左子树中可能存在这样的数，到左子树中去找；
2、a (rt)<x 不能断定就在右子树中，也可能就是rt，这里也要注意。应该说右子树中的满足条件的数和a(rt)中的最大值。

秀一把，写一个递归和一个非递归的：

1. int Pre(int rt, int x)   ///小于x的最大数 和getmin有区别
   
2. {
   
3.         if(rt==0) return 0;
   
4.         if(a[rt].val>=x) return Pre(a[rt].ls,x);//递归查找左子树
   
5.         else
   
6.                 {
   
7.                         int t=Pre(a[rt].rs,x);
   
8.                         if (a[t].val<a[rt].val) return rt;//找右子树中是否存在前驱
   
9.                         else return t;
   
10.                 }
    
11. }
    
12. 
    
13. 
    
14. int Suc(int rt, int x)  ///大于x的最小
    
15. {
    
16.         int p = rt, ans=0;
    
17.         while(p>0)
    
18.                 {
    
19.                         if(a[p].val<=x) p=a[p].rs;
    
20.                         else
    
21.                                 {
    
22.                                         ans = p;
    
23.                                         p=a[p].ls;
    
24.                                 }
    
25.                 }
    
26.         return ans;
    
27. }

复制代码

admin

好好体会上面的程序，现在我们学会了基本的建树和查找，删除，这是后面很多高级树结构的基本，替罪羊树，treap，splay等很多基本思路和做法都是这样的。
下面我们来看一个难一点的BST，普通平衡树
https://www.luogu.com.cn/problem/P3369

admin

用这个来做LG1097 统计数字，数据规模不大，硬搞，居然AC了。

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. const int mm=10100;
   
4. struct AA
   
5. {
   
6.         int val,cnt;
   
7.         int ls,rs;
   
8. } a[mm];
   
9. int tot;/// 有效节点总数
   
10. void ArrayPr()
    
11. {
    
12.         for (int i=1; i<=tot; i++) cout<<setw(3)<<i;
    
13.         cout<<endl;
    
14.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].val;
    
15.         cout<<endl;
    
16.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].cnt;
    
17.         cout<<endl;
    
18.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].ls;
    
19.         cout<<endl;
    
20.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].rs;
    
21.         cout<<endl;
    
22. 
    
23. }
    
24. void BSTPr(int rt) ///中序输出以rt为根的BST
    
25. {
    
26.         if (a[rt].ls>0)  BSTPr(a[rt].ls);
    
27.         cout<<a[rt].val<<' '<<a[rt].cnt<<endl;
    
28.         if (a[rt].rs>0)  BSTPr(a[rt].rs);
    
29. }
    
30. void BSTIns(int  & rt,int x)  ///在以rt为根的BST中传插入x
    
31. {
    
32.         if (rt==0)  ///新建
    
33.         {
    
34.                 rt=++tot;
    
35.                 a[tot].val=x;
    
36.                 a[tot].cnt=1;
    
37.                 a[tot].ls=a[tot].rs=0;
    
38.         }
    
39.         else  if (a[rt].val==x)a[rt].cnt++;
    
40.         else if (a[rt].val<x) BSTIns(a[rt].rs,x);
    
41.         else if (a[rt].val>x) BSTIns(a[rt].ls,x);
    
42. }
    
43. int main()
    
44. {
    
45.         int n,x,rt=0;
    
46.         cin>>n;
    
47.         while (n--)
    
48.         {
    
49.                 cin>>x;
    
50.                 BSTIns(rt,x); ///以rt为根节点
    
51.         }
    
52.         BSTPr(rt);
    
53.         return 0;
    
54. 
    
55. }
    
56. 
    
57. /*
    
58. 8
    
59. 2
    
60. 4
    
61. 2
    
62. 4
    
63. 5
    
64. 100
    
65. 2
    
66. 100
    
67. 
    
68. */

复制代码

admin

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. const int mm=100;
   
4. struct AA
   
5. {
   
6.         int val,cnt;
   
7.         int ls,rs;
   
8. } a[mm],ta;
   
9. int tot;/// 有效节点总数
   
10. void ArrayPr()
    
11. {
    
12.         for (int i=1; i<=tot; i++) cout<<setw(3)<<i;
    
13.         cout<<endl;
    
14.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].val;
    
15.         cout<<endl;
    
16.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].cnt;
    
17.         cout<<endl;
    
18.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].ls;
    
19.         cout<<endl;
    
20.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].rs;
    
21.         cout<<endl;
    
22. 
    
23. }
    
24. void BSTPr(int rt) ///中序输出以rt为根的BST
    
25. {
    
26.         if (a[rt].ls>0)  BSTPr(a[rt].ls);
    
27.         cout<<a[rt].val<<' '; /// 也可以加上cnt
    
28.         if (a[rt].rs>0)  BSTPr(a[rt].rs);
    
29. }
    
30. void BSTIns(int  & rt,int x)  ///在以rt为根的BST中传插入x
    
31. {
    
32.         if (rt==0)  ///新建
    
33.         {
    
34.                 rt=++tot;
    
35.                 a[tot].val=x;
    
36.                 a[tot].cnt=1;
    
37.                 a[tot].ls=a[tot].rs=0;
    
38.         }
    
39.         else  if (a[rt].val==x)a[rt].cnt++;
    
40.         else if (a[rt].val<x) BSTIns(a[rt].rs,x);
    
41.         else if (a[rt].val>x) BSTIns(a[rt].ls,x);
    
42. }
    
43. int findx(int rt,int x)
    
44. {
    
45.         if (rt==0)  return 0;
    
46.         else if (a[rt].val==x) return rt;
    
47.         else if (a[rt].val<x) return findx(a[rt].rs,x);
    
48.         else if (a[rt].val>x) return findx(a[rt].ls,x);
    
49. }
    
50. int  rank(int x)
    
51. {
    
52. }
    
53. AA DelMin(int & rt) ///删除rt为根的树里的最小结点 并返回这个结点的val值
    
54. {
    
55.         AA t;
    
56.         if (a[rt].ls==0)   ///没有左儿子，它就是最小，准备删除
    
57.         {
    
58.                 t.val=a[rt].val,t.cnt=a[rt].cnt;t.ls=t.rs=0;
    
59.                 rt=a[rt].rs; ///右儿子接上了
    
60.                 return t;
    
61.         }
    
62.         else return DelMin(a[rt].ls);
    
63. }
    
64. 
    
65. void BSTDel(int & rt,int x) ///在rt子树中删除x
    
66. {
    
67.         if (rt==0)  return ;
    
68.         else if (a[rt].val>x) BSTDel(a[rt].ls,x);
    
69.         else if (a[rt].val<x) BSTDel(a[rt].rs,x);
    
70.         else if (a[rt].cnt>1) a[rt].cnt--;
    
71.         else if (a[rt].ls==0) rt=a[rt].rs; /// 要不要考虑将右儿子清0
    
72.         else if (a[rt].rs==0) rt=a[rt].ls;
    
73.         else ///右子树的最小值接上来
    
74.         {
    
75.                 a[rt].val=DelMin(a[rt].rs).val;
    
76.                 a[rt].cnt=DelMin(a[rt].rs).cnt;
    
77.         }
    
78. }
    
79. int main()
    
80. {
    
81.         int x, rt=1;
    
82.         cin>>x;
    
83.         while (x>0)
    
84.         {
    
85.                 BSTIns(rt,x); ///以rt为根节点
    
86.                 cin>>x;
    
87.         }
    
88. 
    
89. 
    
90.         cout<<tot<<endl;
    
91.         ArrayPr();
    
92.         cout<<rt<<' ';
    
93.         BSTPr(rt);
    
94.         cout<<endl<<findx(rt,1); ///找到1
    
95. 
    
96. }
    
97. 
    
98. /*
    
99. 50 25 75 18 38 66 80 10 16 26 40 62 68 79 90 9 12 15 30 42 93 8 14 41 43 95 6 44 94 99 5 7 0
    
100. 
     
101. */

复制代码

admin

下面我们逐步的来建立这个二叉树，然后进行简单的查询，插入和删除的操作，在进一步学习朝鲜树，替罪羊树，Treap，Splay等。

我们可以用指针和数组静态指针来表示二叉树，一般裸的BST用得少，而改进的BST比如treap等基本不会退化，空间浪费不大，所以我们还是主要用数组静态指针法来表示二叉树。
每个节点完整的信息如下
struct AA
{
        int val,cnt;    基本信息值，这个值出现的次数
        int ls,rs,fa;    指针信息  左右儿子和爸爸  有的时候爸爸也很重要
        int flag,size;  维护信息，此节点是否被删除，这个子树共有多少个有效节点等
} a[mm];
一般a[0]不用，a[1]为树的根，这里先讲基本的BST，只用到val cnt ls rs四个相关域。

一、监视结构体数组
这个a数组里面存放的BST的所有数据，数据之间的逻辑关系比较复杂，不是简单的线性，要注意看看左右儿子，怕程序出错，写个函数打印a数组，便于查看内部数据和逻辑关系

1. void ArrayPr()
   
2. {
   
3.         for (int i=1; i<=tot; i++) cout<<setw(3)<<i;
   
4.         cout<<endl;
   
5.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].val;
   
6.         cout<<endl;
   
7.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].cnt;
   
8.         cout<<endl;
   
9.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].ls;
   
10.         cout<<endl;
    
11.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].rs;
    
12.         cout<<endl;
    
13. }

复制代码

二、中序遍历输出
和普通二叉树的中序遍历一样，递归就是，按此处要求应该能打印出一个递增序列，在关键的地方运行这个函数，比如插入，删除之后，要是没有得到一个递增的序列，说明有问题。

1. void BSTPr(int rt) ///中序输出以rt为根的BST
   
2. {
   
3.         if (a[rt].ls>0)  BSTPr(a[rt].ls);
   
4.         cout<<a[rt].val<<' '; /// 也可以加上cnt
   
5.         if (a[rt].rs>0)  BSTPr(a[rt].rs);
   
6. }

复制代码

三、插入和建树：在空的树中插入一个节点就是建树，在已经存在的树里进行插入某个值x是一个递归的过程：若这个子树的根节点值==x，不用插入，cnt++，若这个子树的根节点值>x，则应该把x插入到它的左子树，若这个子树的根节点值<x，则应该把x插入到它的右子树，这里尤其要注意这个int &rt 传地址的细节！！

1. void BSTIns(int  & rt,int x)  ///在以rt为根的BST中传插入x
   
2. {
   
3.         if (rt==0)  ///新建
   
4.         {
   
5.                 rt=++tot;
   
6.                 a[tot].val=x;
   
7.                 a[tot].cnt=1;
   
8.                 a[tot].ls=a[tot].rs=0;
   
9.         }
   
10.         else  if (a[rt].val==x)a[rt].cnt++;
    
11.         else if (a[rt].val<x) BSTIns(a[rt].rs,x);
    
12.         else if (a[rt].val>x) BSTIns(a[rt].ls,x);
    
13. }

复制代码

四、查找数值x
其实插入的过程中也有查找，就是一简单的递归，因为没有修改，所以这里的rt是传地址，注意和上面的区别。

1. int findx(int rt,int x)
   
2. {
   
3.         if (rt==0)  return 0;
   
4.         else if (a[rt].val==x) return rt;
   
5.         else if (a[rt].val<x) return findx(a[rt].rs,x);
   
6.         else if (a[rt].val>x) return findx(a[rt].ls,x);
   
7. }

复制代码

五、删除数值x

这个就比较复杂了，有的人不写BST的删除，都是让cnt=0打标记假删除，这里我们还是锻炼一下写一个，删除的方法很多，这里我们用一个简单好想的：删除我的话，就把我的后继（右子树的最小值）来取代我，那个后继肯定是个叶子，可以直接删除。当然，用我的前驱左子树的最大值来取代也是一回事。还有一个做法就是层层迭代，用左儿子或者右儿子的值取代我，然后递归处理左或者右儿子，但是比较麻烦。

1. AA DelMin(int & rt) ///删除rt为根的树里的最小结点 并返回这个结点的val值
   
2. {
   
3.         AA t;
   
4.         if (a[rt].ls==0)   ///没有左儿子，它就是最小，准备删除
   
5.         {
   
6.                 t.val=a[rt].val,t.cnt=a[rt].cnt;t.ls=t.rs=0;
   
7.                 rt=a[rt].rs; ///右儿子接上了
   
8.                 return t;
   
9.         }
   
10.         else return DelMin(a[rt].ls);
    
11. }
    
12. 
    
13. void BSTDel(int & rt,int x) ///在rt子树中删除x
    
14. {
    
15.         if (rt==0)  return ;
    
16.         else if (a[rt].val>x) BSTDel(a[rt].ls,x);
    
17.         else if (a[rt].val<x) BSTDel(a[rt].rs,x);
    
18.         else if (a[rt].cnt>1) a[rt].cnt--;
    
19.         else if (a[rt].ls==0) rt=a[rt].rs; /// 要不要考虑将右儿子回收？
    
20.         else if (a[rt].rs==0) rt=a[rt].ls;
    
21.         else ///右子树的最小值接上来
    
22.         {
    
23.                 a[rt].val=DelMin(a[rt].rs).val;
    
24.                 a[rt].cnt=DelMin(a[rt].rs).cnt;
    
25.         }
    
26. }

复制代码