devbox
人工智能uu
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

《C/C++数据结构与算法》第三讲——平衡树_c++平衡树

作者：人工智能uu | 2024-08-01 14:28:27

赞

踩

c++平衡树

第1节    平衡树的引入

        在上一讲中提到，由于二叉排序树的复杂度很容易退化，因此在实际中的用途没有那么广。但是如果二叉排序树能实现平衡，那么二叉排序树的时间复杂度为O(log_2n)，非常优秀，可以得到非常广泛的应用。

        这里所谓的“平衡”，在不同的地方有着不同的定义， 常见的有高度平衡树、重量平衡树等。但其主要目标，都是保证结点最大深度不超过O(log_2n)，以实现高效的查找效率。

        在接下来的几节中，我们将通过下面的两道例题，来依次介绍替罪羊树、Treap、Splay等一些常用的平衡方法。

         【例3.1.1】普通平衡树

        您需要写一种数据结构（可参考题目标题），来维护一个数集，其中需要提供以下操作：

        1.插入一个整数x。

        2.删除一个整数x（若有多个相同的数，只删除一个）。

        3.查询整数x的排名（排名定义为比当前数小的数的个数+1）。

        4.查询排名为x的数。

        5.求x的前驱（前驱定义为小于x且最大的数）。

        6.求x的后继（后继定义为大于x且最小的数）。

        保证所有操作合法。

        【例3.1.2​​​​​​】普通平衡树（数据加强版）

        在上一题的基础上，扩大数据范围并增加了强制在线。

第2节    替罪羊树 

        替罪羊树的原理在上一讲中已经做了详细说明，这里不再赘述。下面介绍替罪羊树的实现：

3.2.1  替罪羊树的结点

  1. 	struct node
  2. 	{
  3. 		int val,cnt,tot;
  4. 		node *lc,*rc;
  5. 		node(int _val=0,int _cnt=0,int _tot=0)
  6. 		{
  7. 			val=_val,cnt=_cnt,tot=_tot;
  8. 			lc=rc=NULL;
  9. 		}
  10. 	}*root,*null,**goat;

        其中，val代表该结点中的数据（权值），cnt代表此数据出现次数，tot代表以该结点为根的子树大小（每个结点记cnt次）。

        lc和rc代表该结点的左右儿子。

        root代表根结点，null代表“空”结点（即一个所有变量均为0的结点，注意与NULL的区别），goat代表替罪羊结点（即深度最小的不平衡的结点，用于重构）。

3.2.2  替罪羊树的重构

        首先，我们需要判定一个结点是否应重构。为此，我们引入一个平衡因子\alpha​（取值在(0.5,1)，一般采用0.7或0.8），若某结点的子结点大小占它本身大小的比例超过\alpha​，则该结点是不平衡的，应当重构。

        另外，为了避免一些不必要的重构（例如某结点的儿子是不平衡的，重构完又发现该结点还是不平衡的，于是再次重构，而事实上只需重构该结点即可），我们引入替罪羊结点goat。goat表示深度最小的不平衡的结点，这样我们只需对goat进行重构即可。

  1. 	void update(node* &now)
  2. 	{
  3. 		now->tot=now->cnt+now->lc->tot+now->rc->tot;
  4. 		if(std::max(now->lc->tot,now->rc->tot)>alpha*now->tot)
  5. 			goat=&now;
  6. 	}

        值得注意的是，这里选取子结点的tot（每个结点记cnt次）作为子结点大小，从而判断该结点是否平衡。事实上，还可以选取csiz（每个结点记1次）作为子结点大小，而且这种选取方式显得更加直观。可以证明，这两种选取方式均可保证树高是log级别的，具体证明留给读者思考。

        重构分为两步——unfold（按中序遍历展开并存入数组）和rebuild（二分重建成树）。

  1. 	void balance(node* &now)
  2. 	{
  3. 		vector<node*> v;
  4. 		unfold(v,now);
  5. 		now=rebuild(v,0,v.size()-1);
  6. 	}
  7. 	void unfold(vector<node*> &v,node *now)
  8. 	{
  9. 		if(now==null)
  10. 			return;
  11. 		unfold(v,now->lc);
  12. 		if(now->cnt)
  13. 			v.push_back(now);
  14. 		unfold(v,now->rc);
  15. 		if(!now->cnt)
  16. 		    delete now;
  17. 	}
  18. 	node* rebuild(vector<node*> &v,int l,int r)
  19. 	{
  20. 		if(l>r)
  21. 			return null;
  22. 		int mid=l+r>>1;
  23. 		v[mid]->lc=rebuild(v,l,mid-1);
  24. 		v[mid]->rc=rebuild(v,mid+1,r);
  25. 		update(v[mid]);
  26. 		return v[mid];
  27. 	}

3.2.3  替罪羊树的插入

        插入时，到达“空”结点则新建结点，找到对应结点则cnt++。return后，再update该结点即可（update已包含对goat的更新）。

  1. 	void __insert(node* &now,int x)
  2. 	{
  3. 		if(now==null)
  4. 		{
  5. 			now=new node(x,1,1);
  6. 			now->lc=now->rc=null;
  7. 			return;
  8. 		}
  9. 		if(x==now->val)
  10. 			now->cnt++;
  11. 		else if(x<now->val)
  12. 			__insert(now->lc,x);
  13. 		else
  14. 			__insert(now->rc,x);
  15. 		update(now);
  16. 	}

3.2.4  替罪羊树的删除

        删除时，我们可以采用惰性删除，找到对应结点时直接cnt--，实际上并没有真的删除该结点（指cnt=0时）。那么何时删除该结点呢？当然是在unfold的时候了，若遇到一个cnt=0的结点，则不用将其存入数组，并delete它。

  1. 	void __erase(node* &now,int x)
  2. 	{
  3. 		if(x==now->val)
  4. 			now->cnt--;
  5. 		else if(x<now->val)
  6. 			__erase(now->lc,x);
  7. 		else
  8. 			__erase(now->rc,x);
  9. 		update(now);
  10. 	}

        这时，你也许会问——若已删除结点过多，会不会影响效率？这个疑问是很自然的，毕竟这些结点占着地方，却是些空点，在插入/删除等操作中又难免要经过它们，不仅浪费时间，还浪费空间。

        但是，我们不要忘了一件非常重要的事——替罪羊树是一棵平衡树。我们先前讲了那么多关于重构的知识，就是为了使替罪羊树成为一棵平衡树。

        既然替罪羊树是一棵平衡树，那我们还有什么可担心的呢？树高可是log级别的啊！即使我们不去实时删除它们，也无非是多一点常数因子罢了。

        如果你对这一点常数因子还是非常介意，那么这里提供两种解决思路：

        （1）采用实时删除。既然问题是惰性删除带来的，那么我们不用惰性删除就好了。具体操作可以参考2.7.4。

        （2）在结点中引入子树当前大小csiz（current size，每个结点记1次）和子树真实大小tsiz（true size，每个结点记1次）。若删除时发现cnt=0，则tsiz--。这样在update的时候，若发现tsiz占csiz的比例低于\alpha​，则该结点亦应重构（即更新goat）。

3.2.5  替罪羊树的其他基本操作

        其他基本操作与普通二叉排序树无异，下面给出完整代码实现。

  1. #include<bits/stdc++.h>
  2. using std::vector;
  3. struct tree
  4. {
  5. private:
  6. 	static constexpr double alpha=0.75;
  7. 	struct node
  8. 	{
  9. 		int val,cnt,tot;
  10. 		node *lc,*rc;
  11. 		node(int _val=0,int _cnt=0,int _tot=0)
  12. 		{
  13. 			val=_val,cnt=_cnt,tot=_tot;
  14. 			lc=rc=NULL;
  15. 		}
  16. 	}*root,*null,**goat;
  17. 	void update(node* &now)
  18. 	{
  19. 		now->tot=now->cnt+now->lc->tot+now->rc->tot;
  20. 		if(std::max(now->lc->tot,now->rc->tot)>alpha*now->tot)
  21. 			goat=&now;
  22. 	}
  23. 	void __insert(node* &now,int x)
  24. 	{
  25. 		if(now==null)
  26. 		{
  27. 			now=new node(x,1,1);
  28. 			now->lc=now->rc=null;
  29. 			return;
  30. 		}
  31. 		if(x==now->val)
  32. 			now->cnt++;
  33. 		else if(x<now->val)
  34. 			__insert(now->lc,x);
  35. 		else
  36. 			__insert(now->rc,x);
  37. 		update(now);
  38. 	}
  39. 	void __erase(node* &now,int x)
  40. 	{
  41. 		if(x==now->val)
  42. 			now->cnt--;
  43. 		else if(x<now->val)
  44. 			__erase(now->lc,x);
  45. 		else
  46. 			__erase(now->rc,x);
  47. 		update(now);
  48. 	}
  49. 	int __rank(node *now,int x)
  50. 	{
  51. 		if(now==null)
  52. 			return 1;
  53. 		if(now->cnt&&x==now->val)
  54. 			return now->lc->tot+1;
  55. 		if(x<now->val)
  56. 			return __rank(now->lc,x);
  57. 		return now->lc->tot+now->cnt+__rank(now->rc,x); 
  58. 	}
  59. 	int __kth(node *now,int k)
  60. 	{
  61. 		if(k<=now->lc->tot)
  62. 			return __kth(now->lc,k);
  63. 		if(k>now->lc->tot+now->cnt)
  64. 			return __kth(now->rc,k-now->lc->tot-now->cnt);
  65. 		return now->val;
  66. 	}
  67. 	void balance(node* &now)
  68. 	{
  69. 		vector<node*> v;
  70. 		unfold(v,now);
  71. 		now=rebuild(v,0,v.size()-1);
  72. 	}
  73. 	void unfold(vector<node*> &v,node *now)
  74. 	{
  75. 		if(now==null)
  76. 			return;
  77. 		unfold(v,now->lc);
  78. 		if(now->cnt)
  79. 			v.push_back(now);
  80. 		unfold(v,now->rc);
  81. 		if(!now->cnt)
  82. 		    delete now;
  83. 	}
  84. 	node* rebuild(vector<node*> &v,int l,int r)
  85. 	{
  86. 		if(l>r)
  87. 			return null;
  88. 		int mid=l+r>>1;
  89. 		v[mid]->lc=rebuild(v,l,mid-1);
  90. 		v[mid]->rc=rebuild(v,mid+1,r);
  91. 		update(v[mid]);
  92. 		return v[mid];
  93. 	}
  94. public:
  95. 	tree()
  96. 	{
  97. 		root=null=new node;
  98. 	}
  99. 	void insert(int x)//插入
  100. 	{
  101. 		goat=&null;
  102. 		__insert(root,x);
  103. 		balance(*goat);
  104. 	}
  105. 	void erase(int x)//删除
  106. 	{
  107. 		goat=&null;
  108. 		__erase(root,x);
  109. 		balance(*goat);
  110. 	}
  111. 	int rank(int x)//查排名
  112. 	{
  113. 		return __rank(root,x);
  114. 	}
  115. 	int kth(int k)//查k大
  116. 	{
  117. 		return __kth(root,k);
  118. 	}
  119. 	int prev(int x)//求前驱
  120. 	{
  121. 		return kth(rank(x)-1);
  122. 	}
  123. 	int next(int x)//求后继
  124. 	{
  125. 		return kth(rank(x+1));
  126. 	}
  127. };

第3节    Treap

第4节    Splay

第5节    SBT

第6节    AVL树

第7节    红黑树

第8节    WBLT

第9节    权值线段树

        1.插入一个整数x：单点+1。

        2.删除一个整数x：单点-1。

        3.查询整数x的排名：查询x左边的数字的个数，即区间求和。

        4.查询排名为x的数：在线段树上维护size，然后每次看往左还是往右，直到单点为止。

        5.求x的前驱：综合3、4操作。

        6.求x的后继：综合3、4操作。

        复杂度分析：（n代表操作数，R代表值域大小）

实现方式离散化动态开点
时间复杂度O(n*log n)O(n*log R)
空间复杂度O(n)O(n*log R)
是否支持在线否是

        值得注意的是，由于离散化实现的常数因子较大，故在实际表现中其时间效率不如动态开点，但其空间效率总是优于动态开点。

  1. #include<bits/stdc++.h>
  2. #define INF 10000000
  3. const int maxn=1e5+5;
  4. struct tree
  5. {
  6. private:
  7. 	int tot;
  8. 	struct node
  9.     {
  10. 	    int l,r;
  11. 	    int lc,rc;
  12. 	    int cnt;
  13. 	    node(int _l=0,int _r=0)
  14. 	    {
  15. 		    l=_l,r=_r;
  16. 		    lc=rc=0;
  17. 		    cnt=0;
  18. 	    }
  19.     }a[maxn<<2];
  20. 	void modify(int now,int pos,int k)
  21. 	{
  22. 		if(a[now].l==a[now].r)
  23. 		{
  24. 			a[now].cnt=std::max(a[now].cnt+k,0);	
  25. 			return;
  26. 		}
  27. 		int mid=a[now].l+a[now].r>>1;
  28. 		if(pos<=mid)
  29. 		{
  30. 			if(!a[now].lc)
  31. 				a[a[now].lc=++tot]=node(a[now].l,mid);
  32. 			modify(a[now].lc,pos,k);	
  33. 		}
  34. 		else
  35. 		{
  36. 			if(!a[now].rc)
  37. 				a[a[now].rc=++tot]=node(mid+1,a[now].r);
  38. 			modify(a[now].rc,pos,k);
  39. 		}
  40. 		a[now].cnt=a[a[now].lc].cnt+a[a[now].rc].cnt;
  41. 	}
  42. 	int query_cnt(int now,int l,int r)
  43. 	{
  44. 		if(!now||a[now].r<l||r<a[now].l)
  45. 			return 0;
  46. 		if(l<=a[now].l&&a[now].r<=r)
  47. 			return a[now].cnt;
  48. 		return query_cnt(a[now].lc,l,r)+query_cnt(a[now].rc,l,r);
  49. 	}
  50. 	int query_val(int now,int x)
  51. 	{
  52. 		if(a[now].l==a[now].r)
  53. 			return a[now].l;
  54. 		if(x<=a[a[now].lc].cnt)
  55. 			return query_val(a[now].lc,x);
  56. 		return query_val(a[now].rc,x-a[a[now].lc].cnt);
  57. 	}
  58. public:
  59. 	tree()
  60. 	{
  61. 		a[++tot]=node(-INF,INF);
  62. 	}
  63. 	void insert(int x)
  64. 	{
  65. 		modify(1,x,1);
  66. 	}
  67. 	void erase(int x)
  68. 	{
  69. 		modify(1,x,-1);
  70. 	}
  71. 	int x_rank(int x)
  72. 	{
  73. 		return query_cnt(1,-INF,x-1)+1;
  74. 	}
  75. 	int rank_x(int x)
  76. 	{
  77. 		return query_val(1,x);
  78. 	}
  79. 	int prev(int x)
  80. 	{
  81. 		return rank_x(x_rank(x)-1);
  82. 	}
  83. 	int next(int x)
  84. 	{
  85. 		int cnt=query_cnt(1,x,x);
  86. 		return rank_x(x_rank(x)+cnt);
  87. 	}
  88. };
声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号