华师一附中OI组

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

作者: admin    时间: 2020-3-22 10:17
下面我们逐步的来建立这个二叉树，然后进行简单的查询，插入和删除的操作，在进一步学习朝鲜树，替罪羊树，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. }

  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. }
复制代码


作者: admin    时间: 2020-3-22 10:59
  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;

  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. }

  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.         }


  90.         cout<<tot<<endl;
  91.         ArrayPr();
  92.         cout<<rt<<' ';
  93.         BSTPr(rt);
  94.         cout<<endl<<findx(rt,1); ///找到1

  96. }

  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

  101. */
复制代码
作者: admin    时间: 2020-3-22 12:35
用这个来做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;

  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;

  55. }

  57. /*
  58. 8
  59. 2
  60. 4
  61. 2
  62. 4
  63. 5
  64. 100
  65. 2
  66. 100

  68. */
复制代码
作者: admin    时间: 2020-3-29 16:34
好好体会上面的程序，现在我们学会了基本的建树和查找，删除，这是后面很多高级树结构的基本，替罪羊树，treap，splay等很多基本思路和做法都是这样的。
下面我们来看一个难一点的BST，普通平衡树
https://www.luogu.com.cn/problem/P3369
作者: admin    时间: 2020-3-29 16:48
在我们上面最简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. }


  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. }
复制代码







欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2