• C++红黑树

    本期我们来手撕红黑树，相信大家很早就听过红黑树的传说了吧，这里最好有AVL树的基础，我这里把AVL的相关博客贴在这里，没有看过的同学建议先看看

    C++AVL树_KLZUQ的博客-CSDN博客

    话不多说，我们直接进入正题

    目录

    红黑树的概念

    ​编辑 红黑树的性质

    代码实现

    完整代码

    红黑树的概念

    红黑树 ，是一种 二叉搜索树 ，但 在每个结点上增加一个存储位表示结点的颜色，可以是 Red 或 Black 。 通过对 任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路 径会比其他路径长出俩倍 ，因而是 接近平衡 的。

     红黑树的性质

    1. 每个结点不是红色就是黑色
    2. 根节点是黑色的 
    3. 如果一个节点是红色的，则它的两个孩子结点必须是黑色的 
    4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点 
    5. 每个叶子结点都是黑色的 ( 此处的叶子结点指的是空结点 )

    从上面的性质我们可以分析出，在红黑树中，任意一条路径都没有连续的红节点，我们再看上面的红黑树图片，这棵红黑树有11条路径，路径的尾部是NULL，也就是图里面的NIL节点，从根节点到NIL节点就是一条路径

    红黑树要根据这些条件来做到最长路径不超过最短路径的二倍，是怎么做到的呢？

    我们把8下面的节点去掉，再把8变为黑色，按照它的条件，大家想一想

    最短路径一定是全黑，最长路径就是一黑一红的重复，而且我们可以分析出，每条路径里黑色节点的占比一定是大于等于1/2的

    红黑树是比AVL更优的结构，在同样数量级下，红黑树的高度可能是AVL的二倍，但是一亿个数据也就是30和60的区别，对于cpu来说就是0.001秒和0.002秒的差距（我这里随便举的例），但是AVL树要插入这么多节点是需要进行大量旋转的，因为AVL树的左右高度差不能超过1，而红黑树就不用考虑那么多，所以总体而已红黑树是更优的，现实里也是一样，AVL树是几乎不用的，而红黑树缺被沿用了下来，这些大家了解即可

    下面我们来进行代码实现

    代码实现

    1. enum Colour
    2. {
    3. 	RED,
    4. 	BLACK
    5. };
    6. template<class K,class V>
    7. struct RBTreeNode
    8. {
    9. 	RBTreeNode* _left;
    10. 	RBTreeNode* _right;
    11. 	RBTreeNode* _parent;
    12. 	pair _kv;
    13. 	Colour _col;
    14.     RBTreeNode(const pair& kv)
    15. 		:_left(nullptr)
    16. 		, _right(nullptr)
    17. 		, _parent(nullptr)
    18. 		, _kv(kv)
    19. 		,_col(RED)
    20. 	{}
    21. };
    22.  
    23. template<class K, class V>
    24. struct RBTree
    25. {
    26. 	typedef RBTreeNode Node;
    27. public:
    28. 	bool Insert(const pair& kv)
    29. 	{
    30. 		if (_root == nullptr)
    31. 		{
    32. 			_root = new Node(kv);
    33.             _root->_col = BLACK;
    34. 			return true;
    35. 		}
    36. 		Node* cur = _root;
    37. 		Node* parent = nullptr;
    38. 		while (cur)
    39. 		{
    40. 			if (cur->_kv.first < kv.first)
    41. 			{
    42. 				parent = cur;
    43. 				cur = cur->_right;
    44. 			}
    45. 			else if (cur->_kv.first > kv.first)
    46. 			{
    47. 				parent = cur;
    48. 				cur = cur->_left;
    49. 			}
    50. 			else
    51. 			{
    52. 				return false;
    53. 			}
    54. 		}
    55. 		cur = new Node(kv);
    56. 		if (parent->_kv.first < kv.first)
    57. 		{
    58. 			parent->_right = cur;
    59. 		}
    60. 		else
    61. 		{
    62. 			parent->_left = cur;
    63. 		}
    64. 		cur->_parent = parent;
    65. 		//...
    66.  
    67. 		return true;
    68. 	}
    69. private:
    70. 	Node* _root = nullptr;
    71. };

    我们先写好框架和insert的部分，这里insert和AVL树没什么区别，我就直接复制过来了，和AVL树相比，这里还多了一个颜色，我们使用枚举类型即可

    下面我们想一想插入该怎么办？我们插入新的节点，是插入红色节点还是黑色呢？答案是红色，插入黑色节点，所有的路径都会受到影响（红黑树各路径上黑色节点数相同），而插入红色节点，只有当前路径会受到影响，两权相害取其轻

    并且左边这种插入是不受影响的，所以我们插入红色节点

    如果插入后，父亲节点是黑色，我们就插入结束，如果父亲是红色，我们就需要进行变化

    并且，如果父亲节点是红色，那么一定会有爷爷节点，而且是黑色，下面我们就需要分类讨论

     

    如果父亲有兄弟，并且兄弟是红色， 我们要先把父亲和叔叔变黑，爷爷变红

    这里父亲一定要变黑，不然是没有办法解决连续的红节点问题的 ，此时在这个局部的子树里，黑色节点数里不变，连续的红节点问题暂时解决

    再看下一步，这里分三种情况讨论

    1.如果祖父没有父亲，也就是祖父是根节点，我们就把祖父再变黑

    2.如果祖父有父亲，父亲是黑色，那么就结束

    3.如果有父亲并且父亲是红色，那么需要我们就把祖父当作新增节点继续向上处理

    比如此时，我们只需把parent和uncle变黑，再把grandfather变红，最后再把grandfather变黑即可

    不过这里是恰好uncle存在且为红，还有别的情况需要讨论

    我们先看现在的情况，此时插入完成，相比之前的树，相当于所有路径都多了一个黑色节点，黑色节点多是好的，我们插入时也会方便

    下面我们来看这种情况，uncle不存在，我们插入新节点后，最长路径超过了最短路径的二倍，此时就需要进行旋转

    这里是一个简单的右单旋，然后需要变色

    我们把25变红，22变黑即可，所以uncle不存在的话，我们需要旋转加变色

    所以总结一下红黑树的变化

    1.叔叔存在且为红，2.叔叔不存在，3.叔叔存在且为黑

    什么时候会有第三种情况？

    比如我们在下面两个红节点的四个位置随意插入一个新节点 ，就会出现叔叔存在且为黑

    此时，我们先把父亲和叔叔变黑，祖父变红

    然后grandfather变成cur，其他的依次改变，此时就是叔叔存在且为黑

    接着我们进行左旋，然后把parent变黑，grandfather变红即可

    我们对比前面的，就可以发现，这里parent都是要变黑的

    最后总结：1.红黑树插入的关键是看uncle，uncle存在且为红，则变色+继续向上处理，2.如果uncle不存在或者存在且为黑，则旋转+变色

    上面是具体的图，下面我们来看抽象图

     约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

    情况一 : cur 为红， p 为红， g 为黑， u 存在且为红
    解决方式：将 p,u 改为黑， g 改为红，然后把 g 当成 cur ，继续向上调整。
    我们在这里简单分析一下，第一种情况是abcde都是空，cur是新增，就是我们上面讲的
    第二种情况是c/d/e是每条路径有一个黑色节点的红黑树，有4种情况

     

    再推测，a和b就是红节点，在a和b的任意孩子位置新增节点，都会导致变色，出现叔叔存在且为红的情况 ，上面一共有4*4*4*3 = 256种情况（c/d/e每个4种，a和b4种），但无论是哪一种，处理方法都是这样的，再想一想，如果c/d/e是每条路径有两个黑色节点的呢？那情况就太恐怖了，和AVL树是一样的，这里也是无穷无尽的，所以我们需要抽象图来帮助我们理解

    1.         while (parent && parent->_col == RED)
    2. 		{
    3. 			Node* grandfather = parent->_parent;
    4. 			if (parent == grandfather->_left)
    5. 			{
    6. 				Node* uncle = grandfather->_right;
    7. 				if (uncle && uncle->_col == RED)//叔叔存在且为红
    8. 				{
    9. 					//变色
    10. 					uncle->_col = BLACK;
    11. 					parent->_col = BLACK;
    12. 					grandfather->_col = RED;
    13. 					//继续向上处理
    14. 					cur = grandfather;
    15. 					parent = cur->_parent;
    16. 				}
    17. 			}
    18. 		}
    19. 		_root->_col = BLACK;

    我们这里写出代码

    情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑

    uncle不存在的很简单，只需要旋转即可
    再看叔叔存在且为黑，首先这里cur一定不会是新增，否则这棵树就不是红黑树了，因为右边有两个黑色节点了
    所以我们可以确定cur应该是黑色的

    它的下面是两个红色节点，在它下面任意一个位置插入都会引发问题

    有上面的条件，我们可以推出，c是每条路径包含一个黑色节点的红黑树，这里c有四种情况（如上图所示），d和e可能是空，也可能是红节点（2种），这里要是排列组合的话会有4*2*2*4 = 64种情况，但不管是哪一种，这里都是旋转+变色，下面我们来看具体例子

    比如我们在最下面插入一个红色节点，我们需要把父亲和叔叔先变黑

    接着进行右旋，最后再把p变黑，g变红即可

    这里的旋转就是之前的4种，单旋和双旋各两种，所以我们直接把AVL树那块的左旋和右旋代码拷贝过来，再把平衡因子删掉即可

    1.                 else//叔叔不存在/存在且为黑
    2. 				{
    3. 					if (cur == parent->_left)
    4. 					{
    5. 						RotateR(grandfather);
    6. 						parent->_col = BLACK;
    7. 						grandfather->_col = RED;
    8. 					}
    9. 					else
    10. 					{
    11. 						RotateL(parent);
    12. 						RotateR(grandfather);
    13. 						cur->_col = BLACK;
    14. 						grandfather->_col = RED;
    15. 					}
    16. 					break;
    17. 				}

    我们上面举例只举了右旋，双旋也是一样的，这里就不再举例

    1. else//parent在grandfather的右边
    2. 			{
    3. 				Node* uncle = grandfather->_left;
    4. 				if (uncle && uncle->_col == RED)//叔叔存在且为红
    5. 				{
    6. 					uncle->_col = BLACK;
    7. 					parent->_col = BLACK;
    8. 					grandfather->_col = RED;
    9. 					cur = grandfather;
    10. 					parent = cur->_parent;
    11. 				}
    12. 				else//叔叔不存在/存在且为黑
    13. 				{
    14. 					if (cur == parent->_right)
    15. 					{
    16. 						RotateL(grandfather);
    17. 						parent->_col = BLACK;
    18. 						grandfather->_col = RED;
    19. 					}
    20. 					else
    21. 					{
    22. 						RotateR(parent);
    23. 						RotateL(grandfather);
    24. 						cur->_col = BLACK;
    25. 						grandfather->_col = RED;
    26. 					}
    27. 					break;
    28. 				}
    29. 			}

    接着我们再对称写出另一半代码即可

    下面我们来写一个IsBalance，来看看我们的红黑树是否正确

    1. bool IsBalance()
    2. 	{
    3. 		return IsBalance(_root);
    4. 	}
    5. 	bool CheckColour(Node* root,int blacknum,int benchmark)//检查节点颜色
    6. 	{
    7. 		if (root == nullptr)
    8. 		{
    9. 			if (benchmark != blacknum)//黑色节点数量不对
    10. 				return false;
    11. 			return true;
    12. 		}
    13. 		if (root->_col == BLACK)//检测黑色节点数量
    14. 		{
    15. 			++blacknum;
    16. 		}
    17. 		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
    18. 			cout << root->_kv.first << "连续红节点" << endl;
    19. 			return false;
    20. 		
    21. 		return CheckColour(root->_left,blacknum, benchmark)
    22. 			&& CheckColour(root->_right, blacknum, benchmark);
    23.  
    24. 	}
    25. 	bool IsBalance(Node* root)
    26. 	{
    27. 		if (root == nullptr)
    28. 			return true;
    29. 		if (root->_col != BLACK)
    30. 			return false;
    31. 		int benchmark = 0;//黑色节点基准值
    32. 		Node* cur = _root;
    33. 		while (cur)
    34. 		{
    35. 			if (cur->_col==BLACK)
    36. 				++benchmark;
    37. 			cur = cur->_left;
    38. 		}
    39. 		return CheckColour(root,0, benchmark);
    40. 	}

    这里我们判断是否有连续红节点，每条路径上的黑色节点数量，黑色节点数量我们使用一个基准值来判断，我们先计算这棵树的最左路径有多少黑色节点，把它作为基准值即可，后续如果不一样，那就说明树有问题

    我们简单测试一下，没有问题 ，然后我们再测试一下随机数

    这里也没有问题 

    同样的，红黑树这里我们也只实现insert，删除有点复杂了，如果大家想要去看看删除是如何实现的，可以在网上找一找，或者去看看算法导论这本书

    红黑树是非常重要的结构，现在很多地方都在使用红黑树，所以要求大家要掌握红黑树

    完整代码

    1. enum Colour
    2. {
    3. 	RED,
    4. 	BLACK
    5. };
    6. template<class K,class V>
    7. struct RBTreeNode
    8. {
    9. 	RBTreeNode* _left;
    10. 	RBTreeNode* _right;
    11. 	RBTreeNode* _parent;
    12. 	pair _kv;
    13. 	Colour _col;
    14. 	RBTreeNode(const pair& kv)
    15. 		:_left(nullptr)
    16. 		, _right(nullptr)
    17. 		, _parent(nullptr)
    18. 		, _kv(kv)
    19. 		,_col(RED)
    20. 	{}
    21. };
    22.  
    23. template<class K, class V>
    24. struct RBTree
    25. {
    26. 	typedef RBTreeNode Node;
    27. public:
    28. 	bool Insert(const pair& kv)
    29. 	{
    30. 		if (_root == nullptr)
    31. 		{
    32. 			_root = new Node(kv);
    33. 			_root->_col = BLACK;
    34. 			return true;
    35. 		}
    36. 		Node* cur = _root;
    37. 		Node* parent = nullptr;
    38. 		while (cur)
    39. 		{
    40. 			if (cur->_kv.first < kv.first)
    41. 			{
    42. 				parent = cur;
    43. 				cur = cur->_right;
    44. 			}
    45. 			else if (cur->_kv.first > kv.first)
    46. 			{
    47. 				parent = cur;
    48. 				cur = cur->_left;
    49. 			}
    50. 			else
    51. 			{
    52. 				return false;
    53. 			}
    54. 		}
    55. 		cur = new Node(kv);
    56. 		if (parent->_kv.first < kv.first)
    57. 		{
    58. 			parent->_right = cur;
    59. 		}
    60. 		else
    61. 		{
    62. 			parent->_left = cur;
    63. 		}
    64. 		cur->_parent = parent;
    65. 		
    66. 		while (parent && parent->_col == RED)
    67. 		{
    68. 			Node* grandfather = parent->_parent;
    69. 			if (parent == grandfather->_left)//parent在grandfather的左边
    70. 			{
    71. 				Node* uncle = grandfather->_right;
    72. 				if (uncle && uncle->_col == RED)//叔叔存在且为红
    73. 				{
    74. 					//变色
    75. 					uncle->_col = BLACK;
    76. 					parent->_col = BLACK;
    77. 					grandfather->_col = RED;
    78. 					//继续向上处理
    79. 					cur = grandfather;
    80. 					parent = cur->_parent;
    81. 				}
    82. 				else//叔叔不存在/存在且为黑
    83. 				{
    84. 					if (cur == parent->_left)
    85. 					{
    86. 						RotateR(grandfather);
    87. 						parent->_col = BLACK;
    88. 						grandfather->_col = RED;
    89. 					}
    90. 					else
    91. 					{
    92. 						RotateL(parent);
    93. 						RotateR(grandfather);
    94. 						cur->_col = BLACK;
    95. 						grandfather->_col = RED;
    96. 					}
    97. 					break;
    98. 				}
    99. 			}
    100. 			else//parent在grandfather的右边
    101. 			{
    102. 				Node* uncle = grandfather->_left;
    103. 				if (uncle && uncle->_col == RED)//叔叔存在且为红
    104. 				{
    105. 					uncle->_col = BLACK;
    106. 					parent->_col = BLACK;
    107. 					grandfather->_col = RED;
    108. 					cur = grandfather;
    109. 					parent = cur->_parent;
    110. 				}
    111. 				else//叔叔不存在/存在且为黑
    112. 				{
    113. 					if (cur == parent->_right)
    114. 					{
    115. 						RotateL(grandfather);
    116. 						parent->_col = BLACK;
    117. 						grandfather->_col = RED;
    118. 					}
    119. 					else
    120. 					{
    121. 						RotateR(parent);
    122. 						RotateL(grandfather);
    123. 						cur->_col = BLACK;
    124. 						grandfather->_col = RED;
    125. 					}
    126. 					break;
    127. 				}
    128. 			}
    129. 		}
    130. 		_root->_col = BLACK;
    131. 		return true;
    132. 	}
    133.  
    134. 	void RotateL(Node* parent)//左单旋
    135. 	{
    136. 		Node* cur = parent->_right;
    137. 		Node* curleft = cur->_left;
    138. 		parent->_right = curleft;
    139. 		if (curleft)
    140. 		{
    141. 			curleft->_parent = parent;
    142. 		}
    143. 		cur->_left = parent;
    144. 		Node* ppnode = parent->_parent;
    145. 		parent->_parent = cur;
    146. 		if (parent == _root)//parent是根节点
    147. 		{
    148. 			_root = cur;
    149. 			cur->_parent = nullptr;
    150. 		}
    151. 		else
    152. 		{
    153. 			if (ppnode->_left == parent)
    154. 			{
    155. 				ppnode->_left = cur;
    156. 			}
    157. 			else
    158. 			{
    159. 				ppnode->_right = cur;
    160. 			}
    161. 			cur->_parent = ppnode;
    162. 		}
    163. 	}
    164.  
    165. 	void RotateR(Node* parent)//右单旋
    166. 	{
    167. 		Node* cur = parent->_left;
    168. 		Node* curright = cur->_right;
    169. 		parent->_left = curright;
    170. 		if (curright)
    171. 		{
    172. 			curright->_parent = parent;
    173. 		}
    174. 		Node* ppnode = parent->_parent;
    175. 		cur->_right = parent;
    176. 		parent->_parent = cur;
    177. 		if (ppnode == nullptr)
    178. 		{
    179. 			_root = cur;
    180. 			cur->_parent = nullptr;
    181. 		}
    182. 		else
    183. 		{
    184. 			if (ppnode->_left == parent)
    185. 			{
    186. 				ppnode->_left = cur;
    187. 			}
    188. 			else
    189. 			{
    190. 				ppnode->_right = cur;
    191. 			}
    192. 			cur->_parent = ppnode;
    193. 		}
    194. 	}
    195. 	bool IsBalance()
    196. 	{
    197. 		return IsBalance(_root);
    198. 	}
    199. 	bool CheckColour(Node* root,int blacknum,int benchmark)//检查节点颜色
    200. 	{
    201. 		if (root == nullptr)
    202. 		{
    203. 			if (benchmark != blacknum)//黑色节点数量不对
    204. 				return false;
    205. 			return true;
    206. 		}
    207. 		if (root->_col == BLACK)//检测黑色节点数量
    208. 		{
    209. 			++blacknum;
    210. 		}
    211. 		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
    212. 		{
    213. 			cout << root->_kv.first << "连续红节点" << endl;
    214. 			return false;
    215. 		}
    216.  
    217. 		return CheckColour(root->_left,blacknum, benchmark)
    218. 			&& CheckColour(root->_right, blacknum, benchmark);
    219.  
    220. 	}
    221. 	bool IsBalance(Node* root)
    222. 	{
    223. 		if (root == nullptr)
    224. 			return true;
    225. 		if (root->_col != BLACK)
    226. 			return false;
    227. 		int benchmark = 0;//黑色节点基准值
    228. 		Node* cur = _root;
    229. 		while (cur)
    230. 		{
    231. 			if (cur->_col==BLACK)
    232. 				++benchmark;
    233. 			cur = cur->_left;
    234. 		}
    235. 		return CheckColour(root,0, benchmark);
    236. 	}
    237. private:
    238. 	Node* _root = nullptr;
    239. };

    以上即为本期全部内容，希望大家有所收获

    如有错误，还请指正

  • 相关阅读:
    如何保证Redis和数据库数据一致性
    红米k40s和红米note11pro哪个值得买 两者配置对比
    NEON优化3：矩阵转置的指令优化案例
    基于YOLOV8检测和OCR识别的车牌识别
    JVM(一)：jvm中的数据结构(内存模型)：Java Virtual Machine Specification Runtime Data Areas
    java-net-php-python-jspm学生课堂学习状态查看系统计算机毕业设计程序
    2022前端CSS经典面试题
    废柴勇士（据说没有人能坚持37秒）
    罗马数字转整数
    python基础语法(五)
  • 原文地址：https://blog.csdn.net/KLZUQ/article/details/132939004