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

【数据结构】平衡树之红黑树_红黑树的平衡调整过程

作者：Guff_9hys | 2024-06-27 12:11:15

赞

踩

红黑树的平衡调整过程

        AVL树解决了二叉搜索树退化为单支树而引发的效率问题，是一种绝对平衡的二叉搜索树，其性质（每个节点的左右子树高度差绝对值都不超过1）使其在对数据进行搜索时始终能保持高效（详见【数据结构】平衡树之AVL树）。但是，当涉及一些结构上的修改场景（例如增删），因为要频繁通过旋转来维护其绝对平衡的结构特性，代价较高，使得其在这样的场景中性能十分低下。

        为了继续优化效率问题，后来又不断有大佬提出新的解决方案。1972年，Rudolf Bayer发明了最初红黑树（当时被称为平衡二叉B树）。而后在1978年， Leo J. Guibas 和 Robert Sedgewick 将其修改成了如今的红黑树。 

       红黑树（RBTree）是一种特殊的二叉平衡搜索树，通过一种特殊的“手法”来控制着二叉搜索树的平衡，使其效率与AVL树相当，且在应用和维护等方面整体优于AVL树。

        对于平衡的控制，红黑树放弃了AVL树中调整平衡因子的方式（任一节点的左右子树高度差的绝对值不大于1），而是在树的每个节点上增加了一个用于表示节点的颜色（可以是Red或Black）的存储位，通过对任意一条从根到某个叶子节点的路径上，各个节点着色方式的限制，确保最长路径不超过最短路径的2倍，以此来使一整棵树接近平衡。

        红黑树的应用十分的广泛，例如Java的集合框架 (HashMap、TreeMap、TreeSet)、C++ 的 STL（map/set、mutil_map/mutil_set）、linux内核等等，都将红黑树作为底层结构来使用过。

        本篇博客将通过，对红黑树性质的梳理和主要功能的模拟实现，来帮助读者更加全面地了解红黑树。

目录

一、红黑树的性质 

二、红黑树的模拟实现

1 - 树的构建

2 - 插入

3 - 完整代码

补、一些迷思

1.控制节点的红和黑，怎么就做到了“最长路径不超过最短路径的2倍”？

2.由红黑树与AVL树的性能比较，来说明为什么放弃绝对平衡

3.为什么新创建的节点/新插入的节点默认为红色？

4.对两种需控制平衡的情景的更多说明

5.插入构建红黑树的过程图解

一、红黑树的性质 

        红黑树是因其维护平衡的手段而得名的，通过对树节点颜色的控制，来实现“最长路径不超过最短路径的2倍”的近似平衡。它主要具备以下性质（或者说是它的平衡规则），且这些性质与维护平衡息息相关：

  1. 任意一个树节点的颜色非红即黑；
  2. 根节点的颜色必为黑；  
  3. 任意一个颜色为红的树节点，其孩子节点均为黑，双亲节点为黑（这意味着任意路径上没有连续的红色节点）；  
  4. 对于任意一条从（不为空的叶节点下的）空节点通往根节点的路径，每条路径上黑色节点数量均相同； 
  5. 每个空节点默认为黑色。

（ps：NIL节点指的是空节点 ）

二、红黑树的模拟实现

1 - 树的构建

  1. //用枚举体来标识节点的颜色
  2. enum Colour
  3. {
  4. 	RED,    //0
  5. 	BLACK,  //1
  6. };
  7.  
  8. //创建一个树节点（三叉链结构）
  9. template<class K, class V>
  10. struct RBTreeNode
  11. {
  12. 	RBTreeNode<K, V>* _left;    //左孩子
  13. 	RBTreeNode<K, V>* _right;   //右孩子
  14. 	RBTreeNode<K, V>* _parent;  //双亲
  15. 	pair<K, V> _kv;             //节点的值
  16. 	Colour _col;                //放弃了AVL树的平衡因子，改用颜色标识来控制平衡
  17.  
  18. 	//一个树节点的构造函数
  19. 	RBTreeNode(const pair<K, V>&kv)
  20. 		: _left(nullptr)
  21. 		, _right(nullptr)
  22. 		, _parent(nullptr)
  23. 		, _kv(kv)
  24. 		, _col(RED)    //默认一个新节点为红色
  25. 	{}
  26. };
  27.  
  28. //创建一棵红黑树
  29. template<class K, class V>
  30. class RBTree
  31. {
  32. 	typedef RBTreeNode<K, V>Node;
  33. private:
  34. 	//根节点
  35. 	Node*_root = nullptr;
  36. };

2 - 插入

        红黑树可以看作是引入了颜色标识的二叉搜索树，与AVL树类似（详见【数据结构】平衡树之AVL树），它插入过程也大致分为两步：

  1. 按照二叉搜索树的方式插入新节点：利用插入的值创建一个新的树节点。树为空，就直接将新节点赋给根节点的指针；树不为空，就按二叉搜索树的性质查找到合适的插入位置，在合适位置插入新节点。
  2. 控制树的平衡：调整颜色+旋转。
  1. 	bool Insert(const pair<K, V>& kv)
  2. 	{
  3.         //1.按照二叉搜索树的方式插入新节点
  4.  
  5. 		if (_root == nullptr)
  6. 		{
  7. 			_root = new Node(kv);
  8. 			_root->_col = BLACK;
  9. 			return true;
  10. 		}
  11.  
  12. 		Node* parent = nullptr;
  13. 		Node* cur = _root;
  14. 		while (cur)
  15. 		{
  16. 			if (cur->_kv.first < kv.first)
  17. 			{
  18. 				parent = cur;
  19. 				cur = cur->_right;
  20. 			}
  21. 			else if (cur->_kv.first > kv.first)
  22. 			{
  23. 				parent = cur;
  24. 				cur = cur->_left;
  25. 			}
  26. 			else
  27. 			{
  28. 				return false;
  29. 			}
  30. 		}
  31.  
  32. 		cur = new Node(kv);
  33. 		cur->_col = RED;
  34. 		if (parent->_kv.first < kv.first)
  35. 		{
  36. 			parent->_right = cur;
  37. 		}
  38. 		else
  39. 		{
  40. 			parent->_left = cur;
  41. 		}
  42.  
  43. 		cur->_parent = parent;
  44.  
  45.         
  46.         //2.控制树的平衡
  47.  
  48.         //...
  49.  
  50.  
  51. }

        因为默认一个新插入的节点为红色（原因见下文“一些迷思”），所以插入后就存在两种情况：

  1. 新插入节点的双亲为黑色，则仍满足红黑树的平衡性质，无需控制平衡；
  2. 新插入节点的双亲为红色，则违背平衡性质三，需控制平衡。

        而当新插入节点的双亲为红色，该如何控制平衡呢？

       插入节点的双亲一定是红色的，双亲的双亲一定是黑色的，这两个节点的颜色是始终确定的。 插入的节点为红色，插入后出现了两个连续的红色节点，此时就需要调整节点的颜色。

        调整颜色既是控制树平衡的手段，也是检验是否需要旋转的途径。调整颜色的对象不是新插入的节点，而是其双亲、双亲的兄弟和双亲的双亲。

        详情见下图：

 【Tips】新节点插入后，平衡的控制具体取决于其双亲的兄弟节点：

  1. 双亲的兄弟节点存在且为红色，调整颜色后，继续向上更新；
  2. 双亲的兄弟节点不存在，或存在且为黑色，需先旋转，然后再调整颜色。

（关于将特殊情景下的结论推广到一般性结论的说明，以及旋转分类讨论的图解，见下文“一些迷思”）

 【Tips】旋转的分类讨论：

        设：c为当前节点，p为其双亲节点，g为其祖父节点，u为其双亲的兄弟节点，并且cur为红色，p为红色，g为黑色，u不存在或u存在且为黑色。

1、p为g的左孩子，c为p的左孩子，则针对g做右单旋转；

2、p为g的左孩子，c为p的右孩子，则针对p做左单旋转，再针对g做右单旋转；

3、p为g的右孩子，c为p的右孩子，则针对g做左单旋转；

4、p为g的右孩子，c为p的左孩子，则针对p做右单旋转；

  1. 	bool Insert(const pair<K, V>& kv)
  2. 	{
  3.         //1.按照二叉搜索树的方式插入新节点
  4.  
  5.         //...（见前文）
  6.  
  7.  
  8. 		
  9.         //2.控制平衡
  10.  
  11. 		while (parent && parent->_col == RED)//其双亲存在且双亲为红，才需要处理
  12. 		{
  13. 			Node* grandfather = parent->_parent;
  14. 			if (parent == grandfather->_left)//parent是grandfather的左孩子
  15. 			{
  16. 				Node* uncle = grandfather->_right;//则uncle是grandfather的右孩子
  17. 				//uncle存在且为红
  18. 				if (uncle && uncle->_col == RED)
  19. 				{
  20. 					//变色
  21. 					parent->_col = uncle->_col = BLACK;
  22. 					grandfather->_col = RED;
  23.  
  24. 					//继续向上处理
  25. 					cur = grandfather;
  26. 					parent = cur->_parent;
  27. 				}
  28. 				//uncle不存在，或存在且为黑
  29. 				else
  30. 				{
  31. 					if (cur == parent->_left)
  32. 					{
  33. 						//     g
  34. 						//   p
  35. 						// c
  36. 						//旋转
  37. 						RotateR(grandfather);
  38. 						//变色
  39. 						parent->_col = BLACK;
  40. 						grandfather->_col = RED;
  41.  
  42. 					}
  43. 					else
  44. 					{
  45. 						//     g
  46. 						//   p
  47. 						//		c
  48. 						//旋转
  49. 						RotateL(parent);
  50. 						RotateR(grandfather);
  51. 						//变色
  52. 						cur->_col = BLACK;
  53. 						grandfather->_col = RED;
  54. 					}
  55.  
  56. 					break;
  57. 				}
  58. 			}
  59. 			else //parent == grandfather->_right //parent是grandfather的右孩子
  60. 			{
  61. 				Node* uncle = grandfather->_left;//则uncle是grandfather的左孩子
  62. 				// uncle存在且为红
  63. 				if (uncle && uncle->_col == RED)
  64. 				{
  65. 					//变色
  66. 					parent->_col = uncle->_col = BLACK;
  67. 					grandfather->_col = RED;
  68.  
  69. 					//继续向上处理
  70. 					cur = grandfather;
  71. 					parent = cur->_parent;
  72. 				}
  73. 				//uncle不存在，或存在且为黑
  74. 				else 
  75. 				{
  76. 					if (cur == parent->_right)
  77. 					{
  78. 						// g
  79. 						//	  p
  80. 						//       c
  81. 						//旋转
  82. 						RotateR(grandfather);
  83. 						//变色
  84. 						parent->_col = BLACK;
  85. 						grandfather->_col = RED;
  86. 					}
  87. 					else 
  88. 					{
  89. 						// g
  90. 						//	  p
  91. 						// c
  92. 						//旋转
  93. 						RotateL(parent);
  94. 						RotateR(grandfather);
  95. 						//变色
  96. 						cur->_col = BLACK;
  97. 						grandfather->_col = RED;
  98. 					}
  99.  
  100. 					break;
  101. 				}
  102. 			}
  103. 		}
  104.  
  105. 		_root->_col = BLACK;//无论什么情况，根始终要置为黑
  106.  
  107.  
  108. 		return true;
  109. 	}

（旋转的细节详见【数据结构】平衡树之AVL树） 

  1.     //左单旋
  2. 	void RotateL(Node* parent)
  3. 	{        
  4. 		Node* cur = parent->_right;    //cur是parent的右孩子
  5. 		Node* curleft = cur->_left;    //curleft是cur的左孩子
  6.  
  7.         //将parent及其左子树整体旋转下来，并将parent与cur、curleft与parent、cur与ppnode一一正确链接
  8.  	
  9. 		parent->_right = curleft;
  10. 		if (curleft)
  11. 		{
  12. 			curleft->_parent = parent;    //curleft可能为空，若为空则无需将curleft->_parent与parent链接
  13. 		}
  14. 		cur->_left = parent;
  15.  
  16. 		//需要旋转的树，可能是一个局部的子树
  17.         //cur可能需要跟parent的双亲节点ppnode链接
  18. 		Node* ppnode = parent->_parent;
  19. 		parent->_parent = cur;
  20.  
  21. 		if (parent == _root /*ppnode==nullptr*/)    //旋转点在根，cur无需跟parent的双亲节点链接
  22. 		{
  23. 			_root = cur;
  24. 			cur->_parent = nullptr;
  25. 		}
  26. 		else		            //旋转点不在根，cur需要跟parent的双亲节点链接
  27. 		{
  28. 			if (ppnode->_left == parent)    //parent是ppnode的左孩子，就让cur代替其成为左孩子
  29. 			{
  30. 				ppnode->_left = cur;
  31. 			}
  32. 			else                            //parent是ppnode的右孩子，就让cur代替其成为右孩子
  33. 			{
  34. 				ppnode->_right = cur;
  35. 			}
  36.  
  37. 			cur->_parent = ppnode;        //将cur的双亲节点置为ppnode
  38. 		} 
  39. 	}
  40.  
  41.  
  42.     //右单旋
  43. 	void RotateR(Node* parent)
  44. 	{
  45. 		Node* cur = parent->_left;    //cur是parent的左孩子
  46. 		Node* curright = cur->_right; //curright是cur的右孩子
  47.  
  48.          //将parent及其右子树整体旋转下来，并将parent与cur、curleft与parent、cur与ppnode一一正确链接
  49.  
  50.         //链接curright与parent
  51. 		parent->_left = curright;
  52. 		if (curright)
  53. 		{
  54. 			curright->_parent = parent;
  55. 		}
  56.  
  57.         //链接cur与parent、cur与parent的双亲ppnode
  58. 		Node* ppnode = parent->_parent;
  59. 		cur->_right = parent;
  60. 		if (ppnode == nullptr)
  61. 		{
  62. 			_root = cur;
  63. 			cur->_parent = nullptr;
  64. 		}
  65. 		else
  66. 		{
  67. 			if (ppnode->_left == parent)
  68. 			{
  69. 				ppnode->_left = cur;
  70. 			}
  71. 			else
  72. 			{
  73. 				ppnode->_right = cur;
  74. 			}
  75.  
  76. 			cur->_parent = ppnode;
  77. 		}
  78. 	}
  79.

3 - 完整代码

  1. #pragma once
  2.  
  3. #include<iostream>
  4. using namespace std;
  5.  
  6.  
  7. enum Colour
  8. {
  9. 	RED,
  10. 	BLACK
  11. };
  12.  
  13. template<class K,class V>
  14. struct RBTreeNode
  15. {
  16. 	RBTreeNode<K, V>* _left;
  17. 	RBTreeNode<K, V>* _right;
  18. 	RBTreeNode<K, V>* _parent;
  19.  
  20. 	pair<K, V> _kv;
  21. 	Colour _col;
  22.  
  23. 	RBTreeNode(const pair<K, V>& kv)
  24. 		:_left(nullptr)
  25. 		,_right(nullptr)
  26. 		,_parent(nullptr)
  27. 		,_kv(kv)
  28. 		,_col(RED)
  29. 	{}
  30. };
  31.  
  32. template<class K, class V>
  33. struct RBTree
  34. {
  35. 	typedef RBTreeNode<K, V> Node;
  36. public:
  37. 	bool Insert(const pair<K, V>& kv)
  38. 	{
  39. 		if (_root == nullptr)
  40. 		{
  41. 			_root = new Node(kv);
  42. 			_root->_col = BLACK;
  43. 			return true;
  44. 		}
  45.  
  46. 		Node* parent = nullptr;
  47. 		Node* cur = _root;
  48. 		while (cur)
  49. 		{
  50. 			if (cur->_kv.first < kv.first)
  51. 			{
  52. 				parent = cur;
  53. 				cur = cur->_right;
  54. 			}
  55. 			else if (cur->_kv.first > kv.first)
  56. 			{
  57. 				parent = cur;
  58. 				cur = cur->_left;
  59. 			}
  60. 			else
  61. 			{
  62. 				return false;
  63. 			}
  64. 		}
  65.  
  66. 		cur = new Node(kv);
  67. 		cur->_col = RED;
  68. 		if (parent->_kv.first < kv.first)
  69. 		{
  70. 			parent->_right = cur;
  71. 		}
  72. 		else
  73. 		{
  74. 			parent->_left = cur;
  75. 		}
  76.  
  77. 		cur->_parent = parent;
  78.  
  79.     	//红黑树插入的关键是uncle
  80.     	//1、uncle存在且为红，则变色+继续向上更新
  81.     	//2、uncle不存在，或uncle存在且为黑，则旋转+变色
  82. 		
  83. 		while (parent && parent->_col == RED)
  84. 		{
  85. 			Node* grandfather = parent->_parent;
  86. 			if (parent == grandfather->_left)
  87. 			{
  88. 				Node* uncle = grandfather->_right;
  89. 				//uncle存在且为红
  90. 				if (uncle && uncle->_col == RED)
  91. 				{
  92. 					//变色
  93. 					parent->_col = uncle->_col = BLACK;
  94. 					grandfather->_col = RED;
  95.  
  96. 					//继续向上处理
  97. 					cur = grandfather;
  98. 					parent = cur->_parent;
  99. 				}
  100. 				//uncle不存在，或存在且为黑
  101. 				else
  102. 				{
  103. 					if (cur == parent->_left)
  104. 					{
  105. 						//     g
  106. 						//   p
  107. 						// c
  108. 						RotateR(grandfather);
  109. 						parent->_col = BLACK;
  110. 						grandfather->_col = RED;
  111.  
  112. 					}
  113. 					else
  114. 					{
  115. 						//     g
  116. 						//   p
  117. 						//		c
  118. 						RotateL(parent);
  119. 						RotateR(grandfather);
  120.  
  121. 						cur->_col = BLACK;
  122. 						grandfather->_col = RED;
  123. 					}
  124.  
  125. 					break;
  126. 				}
  127. 			}
  128. 			else // parent == grandfather->_right
  129. 			{
  130. 				Node* uncle = grandfather->_left;
  131. 				// uncle存在且为红
  132. 				if (uncle && uncle->_col == RED)
  133. 				{
  134. 					//变色
  135. 					parent->_col = uncle->_col = BLACK;
  136. 					grandfather->_col = RED;
  137.  
  138. 					//继续向上处理
  139. 					cur = grandfather;
  140. 					parent = cur->_parent;
  141. 				}
  142. 				//uncle不存在，或存在且为黑
  143. 				else 
  144. 				{
  145. 					if (cur == parent->_right)
  146. 					{
  147. 						// g
  148. 						//	  p
  149. 						//       c
  150. 						//旋转+变色
  151. 						RotateR(grandfather);
  152.  
  153. 						parent->_col = BLACK;
  154. 						grandfather->_col = RED;
  155. 					}
  156. 					else 
  157. 					{
  158. 						// g
  159. 						//	  p
  160. 						// c
  161. 						//旋转+变色
  162. 						RotateL(parent);
  163. 						RotateR(grandfather);
  164.  
  165. 						cur->_col = BLACK;
  166. 						grandfather->_col = RED;
  167. 					}
  168.  
  169. 					break;
  170. 				}
  171. 			}
  172. 		}
  173.  
  174. 		_root->_col = BLACK;
  175.  
  176.  
  177. 		return true;
  178. 	}
  179.  
  180. 	//左单旋
  181. 	void RotateL(Node* parent)
  182. 	{
  183. 		++_rotateCount;
  184.  
  185. 		Node* cur = parent->_right;
  186. 		Node* curleft = cur->_left;
  187.  
  188. 		parent->_right = curleft;
  189. 		if (curleft)
  190. 		{
  191. 			curleft->_parent = parent;
  192. 		}
  193.  
  194. 		cur->_left = parent;
  195.  
  196. 		Node* ppnode = parent->_parent;
  197.  
  198. 		parent->_parent = cur;
  199.  
  200.  
  201. 		if (parent == _root)
  202. 		{
  203. 			_root = cur;
  204. 			cur->_parent = nullptr;
  205. 		}
  206. 		else
  207. 		{
  208. 			if (ppnode->_left == parent)
  209. 			{
  210. 				ppnode->_left = cur;
  211. 			}
  212. 			else
  213. 			{
  214. 				ppnode->_right = cur;
  215.  
  216. 			}
  217.  
  218. 			cur->_parent = ppnode;
  219. 		}
  220. 	}
  221.     //右单旋
  222. 	void RotateR(Node* parent)
  223. 	{
  224. 		++_rotateCount;
  225.  
  226. 		Node* cur = parent->_left;
  227. 		Node* curright = cur->_right;
  228.  
  229. 		parent->_left = curright;
  230. 		if (curright)
  231. 			curright->_parent = parent;
  232.  
  233. 		Node* ppnode = parent->_parent;
  234. 		cur->_right = parent;
  235. 		parent->_parent = cur;
  236.  
  237. 		if (ppnode == nullptr)
  238. 		{
  239. 			_root = cur;
  240. 			cur->_parent = nullptr;
  241. 		}
  242. 		else
  243. 		{
  244. 			if (ppnode->_left == parent)
  245. 			{
  246. 				ppnode->_left = cur;
  247. 			}
  248. 			else
  249. 			{
  250. 				ppnode->_right = cur;
  251. 			}
  252.  
  253. 			cur->_parent = ppnode;
  254. 		}
  255. 	}
  256.  
  257.  
  258.     //验树的平衡
  259. 	bool CheckColourNum(Node* root, int blackNum,int benchmark)//递归查询连续的红色节点和验证黑色节点数量
  260. 	{
  261. 		if (root == nullptr)
  262. 		{
  263. 			if (blackNum != benchmark)//若某一条路径上的黑色节点数量与基准值不符，则说明树不平衡（无论基准值本身是否正确）
  264. 			{
  265. 				return false;
  266. 			}
  267. 			return true;
  268. 		}
  269. 			
  270.         //递归记录某一条路径上的黑色节点数量
  271. 		if (root->_col == BLACK)
  272. 		{
  273. 			++blackNum;
  274. 		}
  275.  
  276.         //出现两个连续的红色节点，则说明树不平衡
  277. 		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
  278. 		{
  279. 			cout << root->_kv.first << "RED show up" << endl;
  280. 			return false;
  281. 		}
  282.         
  283.         //递归至左子树和右子树里去验证平衡
  284. 		return CheckColourNum(root->_left,blackNum,benchmark)
  285. 			&& CheckColourNum(root->_right, blackNum, benchmark);
  286. 	}
  287. 	bool IsBalance()//封装一次“bool IsBalance(Node* root)”
  288. 	{
  289. 		return IsBalance(_root);
  290. 	}
  291. 	bool IsBalance(Node* root)//验树的平衡
  292. 	{
  293.         //空树是平衡的
  294. 		if (root == nullptr)
  295. 			return true;
  296.  
  297.         //根节点不是黑色的，则说明树不平衡				
  298. 		if (root->_col != BLACK)
  299. 		{
  300. 			return false;
  301. 		}
  302.  
  303. 		//取最左路径上的黑色节点数量作为基准值
  304. 		Node* cur = _root;
  305. 		int benchmark = 0;
  306. 		while (cur)
  307. 		{
  308. 			if (cur->_col == BLACK)
  309. 			{
  310. 				++benchmark;
  311. 			}
  312. 			cur = cur->_left;
  313. 		}
  314.         //查询连续的红色节点和验证黑色节点数量
  315. 		return CheckColourNum(root,0,benchmark);//参数：根节点，当前路径的黑节点数量，黑节点数量的基准值
  316. 	}
  317.  
  318. 	//求树的高度
  319. 	int Height()
  320. 	{
  321. 		return Height(_root);
  322. 	}
  323. 	int Height(Node* root)
  324. 	{
  325. 		if (root == nullptr)
  326. 			return 0;
  327.  
  328. 		int leftHeight = Height(root->_left);
  329. 		int rightHeight = Height(root->_right);
  330.  
  331. 		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
  332. 	}
  333.  
  334. private:
  335. 	Node* _root = nullptr;
  336. };

补、一些迷思

1.控制节点的红和黑，怎么就做到了“最长路径不超过最短路径的2倍”？

        如下图，是一棵满足“最长路径不超过最短路径的2倍”的合法红黑树，它的最长路径为4（例如13->17->25->22），最短路径为3（例如13->8->1）。

         同样的，下图中是一种极端情况下的红黑树，但它仍是合法的。它的最长路径为4（例如13->17->25->22），最短路径为2（例如13->8）。

        由此可见，控制节点的红和黑，保证最短路径全黑、最长路径是一黑一红相间的（或每条路径上黑色节点的总数占整棵树节点总数的1/2），就满足了“最长路径不超过最短路径的2倍”。

2.由红黑树与AVL树的性能比较，来说明为什么放弃绝对平衡

平衡树特点查找效率大致为创建一棵树的数据量创建后树的高度所需时间约为
AVL树高度差的绝对值不超过1O(logN)1000个值100.000001s
红黑树最长路径不超过最短路径的2倍O(2*logN)1000个值200.000002s

        对于红黑树与AVL树，两者的性能在同一量级上，效率差距并不大，虽然在维护平衡时均需旋转，但AVL树因控制平衡更加严格，需在插入和删除时频繁通过旋转维护其结构，会付出较大的代价，故红黑树整体优于AVL树。

3.为什么新创建的节点/新插入的节点默认为红色？

        当插入的节点为黑色，此时在所插入的路径上，黑色节点的数量比其他路径上多1，就违背了红黑树的性质四（对于任意一条从空节点通往根节点的路径，每条路径上黑色节点数量均相同）。

        当插入的节点为红色，若此时所插入位置的双亲为红色，即出现了连续的红色节点，就违背了红黑树的性质三（任意路径上没有连续的红色节点）。

        也就是说，插入的节点无论是什么颜色的，都会对红黑树的平衡有潜在的影响。

        不过具体而言，若插入的节点为黑色，则是“一定会因违背性质四而破坏平衡”，此时是必须对红黑树进行调整的，且要对多条路径进行调整；而插入的节点为红色，则是“可能会因性质三而破坏平衡”，此时既可能要进行调整，也可能不进行调整，且调整时仅对一条路径进行调整。

        基于这样的利弊，插入节点为红色时维护平衡的代价在理论上更小，故使插入的新节点/新创建的节点默认为红色。

4.对两种需控制平衡的情景的更多说明

        设：cur为当前节点，p为其双亲节点，g为其祖父节点，u为其双亲的兄弟节点。

        情景一：cur为红，p为红，g为黑，u存在且为红。cur和p均为红，违背了性质三。解决方法为，将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。

        当a/b/c/d/e为空树，cur是新插入的节点，情况较为简单，上述解决方法是适用的。 

        而当a/b/c/d/e不为空树，cur不是新插入的节点，尽管情况较为复杂，但上述解决方法仍适用。

        更复杂的情况又例如，c/d/e是每条路径都有两个黑色节点的子树...

        情景二：cur为红，p为红，g为黑，u不存在/u存在且为黑。 

        u不存在，做旋转的处理。

        u存在且为黑，做旋转和变色的处理。

【Tips】旋转的分类讨论：

1、p为g的左孩子，cur为p的左孩子，则针对g做右单旋转；

2、p为g的左孩子，cur为p的右孩子，则针对p做左单旋转，再针对g做右单旋转；

3、p为g的右孩子，cur为p的右孩子，则针对g做左单旋转；

4、p为g的右孩子，cur为p的左孩子，则针对p做右单旋转；

 

5.插入构建红黑树的过程图解

        升序构建红黑树

        降序构建红黑树

        随机插入构建红黑树 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Guff_9hys/article/detail/762480
推荐阅读
相关标签

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

  

闽ICP备14008679号