• 手撕红黑树 | 变色+旋转你真的明白了吗？【超用心超详细图文解释 | 一篇学会Red_Black_Tree】

    说在前面

    我们也很久没有更新数据结构系列了，半年前博主重新深入学习了红黑树这个数据结构，一直想更新呈现给大家，最近也一直没有时间，今天红黑树它来了！

    博主为了这篇博客，做了很多准备，试了很多画图软件，就是为了让大家看得明白！希望大家不要吝啬一键三连啊！！

    前言

    那么这里博主先安利一下一些干货满满的专栏啦！

    手撕数据结构https://blog.csdn.net/yu_cblog/category_11490888.html?spm=1001.2014.3001.5482这里包含了博主很多的数据结构学习上的总结，每一篇都是超级用心编写的，有兴趣的伙伴们都支持一下吧！
    算法专栏https://blog.csdn.net/yu_cblog/category_11464817.html这里是STL源码剖析专栏，这个专栏将会持续更新STL各种容器的模拟实现。

    STL源码剖析https://blog.csdn.net/yu_cblog/category_11983210.html?spm=1001.2014.3001.5482

    什么是红黑树？

    在学习红黑树之前，我们必须先了解和熟悉AVL树：

    万字手撕AVL树 | 上百行的旋转你真的会了吗？【超用心超详细图文解释 | 一篇学会AVL】https://blog.csdn.net/Yu_Cblog/article/details/127698306?spm=1001.2014.3001.5501红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。

    因此，红黑树不是直接通过检验【没有一条路径会比其他路径长出2倍】而维护平衡的，而是通过对根到叶子路径上节点的着色的限制！它不是像AVL一样直接控制平衡，而是间接控制平衡。

    红黑树的性质

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

    红黑树节点结构

    同样，红黑树也是使用三叉链进行构造

    1. enum Colour {
    2. 	RED,BLACK
    3. };
    4. template<class K,class V>
    5. struct __Red_Black_TreeNode {
    6. 	__Red_Black_TreeNode* _left;
    7. 	__Red_Black_TreeNode* _right;
    8. 	__Red_Black_TreeNode* _parent;
    9. 	pair_kv;
    10. 	Colour _col;
    11. 	__Red_Black_TreeNode(const pair& kv)
    12. 		:_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv) {}
    13. };

    红黑树的插入（重点）

    首先插入节点，前面的部分和搜索树和AVL一样，找位置插入即可：

    1. 	bool insert(const pair& kv) {
    2. 		if (_root == nullptr) {
    3. 			_root = new Node(kv);
    4. 			_root->_col = BLACK;
    5. 			return true;
    6. 		}
    7. 		Node* parent = nullptr;
    8. 		Node* cur = _root;
    9. 		while (cur) {
    10. 			if (cur->_kv.first < kv.first) {
    11. 				parent = cur;
    12. 				cur = cur->_right;
    13. 			}
    14. 			else if (cur->_kv.first > kv.first) {
    15. 				parent = cur;
    16. 				cur = cur->_left;
    17. 			}
    18. 			else return false;
    19. 		}
    20. 		cur = new Node(kv);
    21. 		cur->_col = RED;//一开始尽量先变红
    22. 		if (parent->_kv.first < kv.first) {
    23. 			parent->_right = cur;
    24. 		}
    25. 		else {
    26. 			parent->_left = cur;
    27. 		}
    28. 		cur->_parent = parent;
    29.  
    30.         //判断是否需要调整颜色或旋转
    31. 		while (...) {
    32. 			//...
    33. 		}
    34.         //根据规则，最后的根节点一定是黑色的
    35. 		_root->_col = BLACK;//最后无论根是红是黑 -- 都处理成黑
    36. 		return true;
    37. 	}

    在插入这部分，我们要牢牢记住红黑树的两个规则，这是我们插入节点最根本的根据！

    • 规则三:如果一个节点是红色的，那它的孩子是黑色的
    • 规则四:对于每一个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点

    插入的新节点默认是红色

    现在我们要插入一个新的节点

    我们可以分为两种情况：

    • 插入节点的父亲是黑色的
    • 插入节点的父亲是红色的 

    如果插入节点的父亲是黑色的，我们插入黑色节点就会违反规则4，插入红节点并不违反规则，所以我们应该插入的节点应该设置成红色。

    如果插入节点的父亲是红色的，我们插入黑色节点就会违反规则4，插入红节点违反规则3。此时我们应该插入什么颜色的节点呢？

    答案是我们应该插入红色节点，再做后续的变色工作。

    原因：如果插入黑色节点，我们违反规则4，相当于整棵树违法了规则。而我们违反规则3，我们可以通过局部的调整颜色或者旋转解决问题，因此我们选择先把新节点设置成红色，再做变色（+旋转）的处理。

    因此，在红黑树中插入一个新节点，无论什么情况，先设置成红色！

    变色和旋转

    当我们插入一个红节点之后，我们就要检查这颗红黑树是否符合规则了。

    如果插入节点的父亲是黑色，是不违反红黑树规则的，我们不需要做处理。

    下面我们重点讨论：插入节点的父亲为红色的情况。

    红黑树处理情况分类所要关注的节点：父亲、祖父和叔叔（叔叔为父亲的兄弟节点）

    我们把握好父亲祖父和叔叔，就能处理红黑树的所有状况。其中，叔叔的颜色最为关键！

    下面是红黑树调整的三种情况：

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

    情况一：cur为红，p为红，g为黑，u存在且为红

    处理如下：

    tips：我们可以发现，这个情况是不需要看左右的，cur在p的左或右，处理的方式其实都是一样的。

    情况二: cur为红，p为红，g为黑，u不存在/u为黑（且cur,p,g在同一直线上）

    在情况一中，我们把父亲变黑的时候，可以把叔叔一起拉下水，让叔叔也变黑，这样我们就能保证路径上的黑色节点个数保持一致。

    但是现在，叔叔不存在或叔叔已经是黑色的了，此时只能旋转了。

    说明: u的情况有两种

    1. 如果u节点不存在，则cur一定是新插入节点，因为如果cur不是新插入节点则cur和p一定有一个节点的颜色是黑色，就不满足性质4: 每条路径黑色节点个数相同
    2. 如果u节点存在，则其一定是黑色的，那么cur节点原来的颜色一定是黑色的现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色。

    p为g的左孩子，cur为p的左孩子，则进行右单旋转;

    相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转

    p、g变色--p变黑，g变红 

    因为cur,p,g在同一直线上，所以情况二只需要单旋！下面这种情况就需要双旋了！

    情况三: cur为红，p为红，g为黑，u不存在/u为黑（且cur,p,g不在同一直线上）

    p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，
    p为g的右孩子，cur为p的左孩子，则针对p做右单旋转
    则转换成了情况2 

    红黑树的删除等

    讲到这里有伙伴可能会问,为什么讲红黑树,不讲删除那些接口呢?

    因为,校招,公司面试,以后工作中都基本不会考察到AVL树和红黑树的删除接口，我们只需要掌握插入接口就行了。

    AVL树,红黑树我们都是做了解性学习,我们并不需要去手撕它的全部代码,这样时间成本很大,意义不大.我们学习红黑树,我们需要深入的去理解它的结构,学习一个插入接口,我们已经可以很好的做到这一点了。

    检查红黑树是否合法

    思路：找到最左向下路径的黑色节点数作为基准值，检查每条路径黑色节点数目是否与基准值相等。

    1.     bool prev_check(Node* root, int blackNum,int bench_mark) {
    2. 		if (root == nullptr) {
    3. 			if (blackNum != bench_mark)return false;
    4. 			return true;
    5. 		}
    6. 		if (root->_col == BLACK) {
    7. 			blackNum++;
    8. 		}
    9. 		if (root->_col == RED && root->_parent->_col == RED) {
    10. 			//存在连续的红节点，return false
    11. 			return false;
    12. 		}
    13. 		return prev_check(root->_left, blackNum, bench_mark) &&
    14. 			prev_check(root->_right, blackNum, bench_mark);
    15. 	}
    16. 	bool is_balance() {
    17. 		if (_root == nullptr)return true;
    18. 		if (_root->_col == RED)return false;
    19. 		//黑色节点数量基准值
    20. 		int bench_mark = 0;
    21. 		Node* cur = _root;
    22. 		while (cur) {
    23. 			if (cur->_col == BLACK)++bench_mark;
    24. 			cur = cur->_left;
    25. 		}
    26. 		return prev_check(this->_root, 0, bench_mark);
    27. 	}

    RBTree.h

    1. #pragma once
    2. //#include
    3. #include
    4. #include
    5. using namespace std;
    6.  
    7.  
    8. enum Colour {
    9. 	RED,BLACK
    10. };
    11. template<class K,class V>
    12. struct __Red_Black_TreeNode {
    13. 	__Red_Black_TreeNode* _left;
    14. 	__Red_Black_TreeNode* _right;
    15. 	__Red_Black_TreeNode* _parent;
    16. 	pair_kv;
    17. 	Colour _col;
    18. 	__Red_Black_TreeNode(const pair& kv)
    19. 		:_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv) {}
    20. };
    21.  
    22.  
    23. template<class K, class V>
    24. struct RBTree {
    25. 	typedef __Red_Black_TreeNodeNode;
    26. private:
    27. 	Node* _root = nullptr;
    28. private:
    29. 	//左单旋
    30. 	void rotate_left(Node* parent) {
    31. 		Node* subR = parent->_right;
    32. 		Node* subRL = subR->_left;
    33. 		parent->_right = subRL;
    34. 		if (subRL) {
    35. 			subRL->_parent = parent;
    36. 		}
    37. 		Node* ppNode = parent->_parent;//记录一下原先parent的parent
    38. 		subR->_left = parent;
    39. 		parent->_parent = subR;
    40. 		if (_root == parent) {
    41. 			_root = subR;
    42. 			subR->_parent = nullptr;
    43. 		}
    44. 		else {
    45. 			//如果ppNode==nullpt，是不会进来这里的
    46. 			if (ppNode->_left == parent) {
    47. 				ppNode->_left = subR;
    48. 			}
    49. 			else {
    50. 				ppNode->_right = subR;
    51. 			}
    52. 			subR->_parent = ppNode;
    53. 		}
    54. 	}
    55. 	//右单旋
    56. 	void rotate_right(Node* parent) {
    57. 		Node* subL = parent->_left;
    58. 		Node* subLR = subL->_right;
    59. 		parent->_left = subLR;
    60. 		if (subLR) {
    61. 			subLR->_parent = parent;
    62. 		}
    63. 		Node* ppNode = parent->_parent;
    64. 		subL->_right = parent;
    65. 		parent->_parent = subL;
    66. 		if (_root == parent) {
    67. 			_root = subL;
    68. 			subL->_parent = nullptr;
    69. 		}
    70. 		else {
    71. 			if (ppNode->_left == parent) {
    72. 				ppNode->_left = subL;
    73. 			}
    74. 			else {
    75. 				ppNode->_right = subL;
    76. 			}
    77. 			subL->_parent = ppNode;
    78. 		}
    79. 	}
    80. 	void _inorder(Node* root) {
    81. 		if (root == nullptr)return;
    82. 		_inorder(root->_left);
    83. 		cout << root->_kv.first << endl;
    84. 		_inorder(root->_right);
    85. 	}
    86. 	bool prev_check(Node* root, int blackNum,int bench_mark) {
    87. 		if (root == nullptr) {
    88. 			if (blackNum != bench_mark)return false;
    89. 			return true;
    90. 		}
    91. 		if (root->_col == BLACK) {
    92. 			blackNum++;
    93. 		}
    94. 		if (root->_col == RED && root->_parent->_col == RED) {
    95. 			//存在连续的红节点，return false
    96. 			return false;
    97. 		}
    98. 		return prev_check(root->_left, blackNum, bench_mark) &&
    99. 			prev_check(root->_right, blackNum, bench_mark);
    100. 	}
    101. public:
    102. 	bool is_balance() {
    103. 		if (_root == nullptr)return true;
    104. 		if (_root->_col == RED)return false;
    105. 		//黑色节点数量基准值
    106. 		int bench_mark = 0;
    107. 		Node* cur = _root;
    108. 		while (cur) {
    109. 			if (cur->_col == BLACK)++bench_mark;
    110. 			cur = cur->_left;
    111. 		}
    112. 		return prev_check(this->_root, 0, bench_mark);
    113. 	}
    114. public:
    115. 	void inorder() {
    116. 		this->_inorder(this->_root);
    117. 		cout << "\n";
    118. 	}
    119. 	//前面插入的过程和搜索树一样的
    120. 	bool insert(const pair& kv) {
    121. 		if (_root == nullptr) {
    122. 			_root = new Node(kv);
    123. 			_root->_col = BLACK;
    124. 			return true;
    125. 		}
    126. 		Node* parent = nullptr;
    127. 		Node* cur = _root;
    128. 		while (cur) {
    129. 			if (cur->_kv.first < kv.first) {
    130. 				parent = cur;
    131. 				cur = cur->_right;
    132. 			}
    133. 			else if (cur->_kv.first > kv.first) {
    134. 				parent = cur;
    135. 				cur = cur->_left;
    136. 			}
    137. 			else return false;
    138. 		}
    139. 		cur = new Node(kv);
    140. 		cur->_col = RED;//一开始尽量先变红
    141. 		if (parent->_kv.first < kv.first) {
    142. 			parent->_right = cur;
    143. 		}
    144. 		else {
    145. 			parent->_left = cur;
    146. 		}
    147. 		cur->_parent = parent;
    148.  
    149. 		while (parent && parent->_col == RED) {
    150. 			Node* grandparent = parent->_parent;
    151. 			assert(grandparent && grandparent->_col == BLACK);
    152. 			//关键看叔叔
    153. 			//判断一下左右
    154. 			if (parent == grandparent->_left) {
    155. 				Node* uncle = grandparent -> _right;
    156. 				//情况1（不看方向）
    157. 				if (uncle && uncle->_col == RED) {
    158. 					parent->_col = uncle->_col = BLACK;
    159. 					grandparent->_col = RED;
    160. 					//继续向上处理
    161. 					cur = grandparent;
    162. 					parent = cur->_parent;
    163. 				}
    164. 				//情况2+3
    165. 				//uncle不存在/存在且为黑
    166. 				else {
    167. 					//情况2
    168. 					//   g
    169. 					//  p  u
    170. 					// c
    171. 					//右单旋+变色
    172. 					if (cur == parent->_left) {
    173. 						rotate_right(grandparent);
    174. 						parent->_col = BLACK;//父亲变黑
    175. 						grandparent->_col = RED;//祖父变红
    176. 					}
    177. 					//情况3
    178. 					//   g
    179. 					//  p  u
    180. 					//   c
    181. 					//左右双旋+变色
    182. 					else {
    183. 						rotate_left(parent);
    184. 						rotate_right(grandparent);
    185. 						//看着图写就行了
    186. 						cur->_col = BLACK;
    187. 						grandparent->_col = RED;
    188. 					}
    189. 					break;
    190. 				}
    191. 			}
    192. 			else {
    193. 				Node* uncle = grandparent->_left;
    194. 				//情况1（不看方向）
    195. 				if (uncle && uncle->_col == RED) {
    196. 					parent->_col = uncle->_col = BLACK;
    197. 					grandparent->_col = RED;
    198. 					//继续向上处理
    199. 					cur = grandparent;
    200. 					parent = cur->_parent;
    201. 				}
    202. 				else {
    203. 					//情况2
    204. 					//   g
    205. 					//  u  p
    206. 					//      c 
    207. 					//左单旋+变色
    208. 					if (cur == parent->_right) {
    209. 						rotate_left(grandparent);
    210. 						parent->_col = BLACK;//父亲变黑
    211. 						grandparent->_col = RED;//祖父变红
    212. 					}
    213. 					//情况3
    214. 					//   g
    215. 					//  u  p
    216. 					//    c
    217. 					//右左双旋+变色
    218. 					else {
    219. 						rotate_right(parent);
    220. 						rotate_left(grandparent);
    221. 						//看着图写就行了
    222. 						cur->_col = BLACK;
    223. 						grandparent->_col = RED;
    224. 					}
    225. 					break;
    226. 				}
    227. 			}
    228. 		}
    229. 		_root->_col = BLACK;//最后无论根是红是黑 -- 都处理成黑
    230. 		return true;
    231. 	}
    232. };
    233.  
    234.  
    235. void test1() {
    236. 	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    237. 	RBTree<int, int>t1;
    238. 	for (auto e : a) {
    239. 		t1.insert(make_pair(e, e));
    240. 	}
    241. 	t1.inorder();
    242. 	cout << "is_balance():" << t1.is_balance() << endl;
    243. }
    244. void test2() {
    245. 	size_t N = 10000;
    246. 	srand((unsigned)time(nullptr));
    247. 	RBTree<int, int>t1;
    248. 	for (size_t i = 0; i < N; ++i) {
    249. 		int x = rand();
    250. 		t1.insert(make_pair(x, i));
    251. 	}
    252. 	cout << "is_balance():" << t1.is_balance() << endl;
    253. }

    总结

    看到这里,大家应该对红黑树的实现,重点是它的旋转有了比较深入的了解了。这篇博客博主花了很多心思在画图上，也投入了很多时间到画图上。下期给大家带来map/set的封装。希望大家可以多多支持，一键三连，点赞关注收藏评论后在离开哦!

    ( 转载时请注明作者和出处。未经许可，请勿用于商业用途 )
    更多文章请访问我的主页

    @背包https://blog.csdn.net/Yu_Cblog?type=blog

  • 相关阅读:
    python数学建模--sympy三维图像绘制
    2024.7.31 Spyglass lint tcl 使用总结
    QT day4
    系统方向学习9--android 10.0 去掉未知来源弹窗 默认授予安装未知来源权限
    Redis 会被Dragonfly替代？
    SSM_Mybatis（下）
    选专业，适合理科女生的大学专业有哪些？
    Egg 封装接口返回信息
    气相色谱质谱仪样品传输装置中电动针阀和微泄漏阀的解决方案
    uniapp 中 vuex 的使用
  • 原文地址：https://blog.csdn.net/Yu_Cblog/article/details/128210260