• 红黑树详解+模拟实现

    目录

    1.红黑树概念

    2.红黑树的性质

    3.红黑树结点定义

    4.红黑树的插入

    5.红黑树验证

    6.红黑树的查找

    7.红黑树和AVL树比较

    1.红黑树概念

    • 红黑树是一种二叉搜索树，但在每个结点上增加了一个存储位用于表示结点的颜色，这个颜色可以是红色的，也可以是黑色的，因此我们称之为红黑树。
    • 红黑树通过对任何一条从根到叶子的路径上各个结点着色方式的限制，确保没有一条路径会比其他路径长出两倍，因此红黑树是近似平衡的。

                     

                                                    

    2.红黑树的性质

    (1)红黑树有以下五点性质：

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

                                     

     (2)红黑树如何确保从根到叶子的最长可能路径不会超过最短可能路径的两倍？

    • 根据没有连续的红色节点和每条路径上有相同的黑色节点
    • 最短路径:全是黑的
    • 最长路径:一黑一红，红色节点和黑色节点的数量相同
    • 正常红黑树中，不—定有全黑的最短路径和一黑—红的最长路径这个只是我们理想情况。
       

                                    

                                     

     3.红黑树结点定义

    • 这里直接实现KV模型的红黑树，为了方便后序的旋转操作，将红黑树的结点定义为三叉链结构，除此之外还新加入了一个成员变量，用于表示结点的颜色
    1. template<class K, class V>
    2. struct RBTreeNode
    3. {
    4. 	//三叉链
    5. 	RBTreeNode* _left;
    6. 	RBTreeNode* _right;
    7. 	RBTreeNode* _parent;
    8.  
    9. 	//存储的键值对
    10. 	pair _kv;
    11.  
    12. 	//结点的颜色
    13. 	int _col; //红/黑
    14.  
    15. 	//构造函数
    16. 	RBTreeNode(const pair& kv)
    17. 		:_left(nullptr)
    18. 		, _right(nullptr)
    19. 		, _parent(nullptr)
    20. 		, _kv(kv)
    21. 		, _col(RED)
    22. 	{}
    23. };
    • 使用枚举来定义结点的颜色，这样可以增加代码的可读性和可维护性，并且便于后序的调试操作。
    1. //枚举定义结点的颜色
    2. enum Colour
    3. {
    4. 	RED,
    5. 	BLACK
    6. };

                                                    

    为什么构造结点时，默认将结点的颜色设置为红色？

    • 若我们插入的是黑色结点，那么插入路径上黑色结点的数目就比其他路径上黑色结点的数目多了一个，即破坏了红黑树的性质4，此时我们就需要对红黑树进行调整。
    • 若我们插入红黑树的结点是红色的，此时如果其父结点也是红色的，那么表明出现了连续的红色结点，即破坏了红黑树的性质3，此时我们需要对红黑树进行调整；但如果其父结点是黑色的，那我们就无需对红黑树进行调整，插入后仍满足红黑树的要求。
       
    • 插入黑色结点，一定破坏红黑树的性质4，必须对红黑树进行调整。(影响很大)
    • 插入红色结点，可能破坏红黑树的性质3，可能对红黑树进行调整。(影响不大)

                    

                                                    

    4.红黑树的插入

    红黑树插入结点的逻辑分为三步：

    1. 按二叉搜索树的插入方法，找到待插入位置。
    2. 将待插入结点插入到树中。
    3. 若插入结点的父结点是红色的，则需要对红黑树进行调整。

    其中前两步与二叉搜索树插入结点时的逻辑相同，红黑树的关键在于第三步对红黑树的调整。

                                     

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

    注意:此处所看到的树可能是一颗完整的树，也可能是一颗子树

    红黑树在插入结点后是如何调整

    • parent颜色是黑色，不需要调整，插入完成
    • parent颜色是红色，违反规则3，需要处理
    • 因为插入结点的父结点是红色的，说明父结点不是根结点（根结点是黑色的），因此插入结点的祖父结点（父结点的父结点）就一定存在。
    • 红黑树调整时具体应该如何调整，主要是看插入结点的叔叔（插入结点的父结点的兄弟结点），根据插入结点叔叔的不同，可将红黑树的调整分为三种情况。

                                     

    (1)叔叔存在且为红 ，cur为红，p为红，g为黑

    • 此时为了避免出现连续的红色结点，我们可以将父结点变黑，但为了保持每条路径黑色结点的数目不变，因此我们还需要将祖父结点变红，再将叔叔变黑。这样一来既保持了每条路径黑色结点的数目不变，也解决了连续红色结点的问题。(p,u变黑，g变红)
    • 但调整还没有结束，因为此时祖父结点变成了红色，如果祖父结点是根结点，那我们直接再将祖父结点变成黑色即可，此时相当于每条路径黑色结点的数目都增加了一个。
    • (如果g是根节点，调整完成后，需要将g改为黑色)
    • 但如果祖父结点不是根结点的话，我们就需要将祖父结点当作新插入的结点，再判断其父结点是否为红色，若其父结点也是红色，那么又需要根据其叔叔的不同，进而进行不同的调整操作。
    • (如果g是子树，g一定有双亲，且g的双亲如果是红色，需要继续向上调整)

                                     

    (2) 叔叔存在且为黑/不存在，cur为红，p为红，g为黑

     说明: u的情况有两种

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

                                             

     (3)叔叔存在且为黑/不存在，cur为红，p为红，g为黑

    • 情况2,3其实是一样的，只不过: 2是直线，3是折线 
    • p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；
    • p为g的右孩子，cur为p的左孩子，则针对p做右单旋转;
    • 最后转化为了情况2

                             

     (4)代码

    1. //插入函数
    2. pairbool> Insert(const pair& kv)
    3. {
    4. 	if (_root == nullptr) //若红黑树为空树，则插入结点直接作为根结点
    5. 	{
    6. 		_root = new Node(kv);
    7. 		_root->_col = BLACK; //根结点必须是黑色
    8. 		return make_pair(_root, true); //插入成功
    9. 	}
    10.  
    11. 	//1、按二叉搜索树的插入方法，找到待插入位置
    12. 	Node* cur = _root;
    13. 	Node* parent = nullptr;
    14. 	while (cur)
    15. 	{
    16. 		if (kv.first < cur->_kv.first) //待插入结点的key值小于当前结点的key值
    17. 		{
    18. 			//往该结点的左子树走
    19. 			parent = cur;
    20. 			cur = cur->_left;
    21. 		}
    22. 		else if (kv.first > cur->_kv.first) //待插入结点的key值大于当前结点的key值
    23. 		{
    24. 			//往该结点的右子树走
    25. 			parent = cur;
    26. 			cur = cur->_right;
    27. 		}
    28. 		else //待插入结点的key值等于当前结点的key值
    29. 		{
    30. 			return make_pair(cur, false); //插入失败
    31. 		}
    32. 	}
    33.  
    34. 	//2、将待插入结点插入到树中
    35. 	cur = new Node(kv); //根据所给值构造一个结点
    36. 	Node* newnode = cur; //记录新插入的结点（便于后序返回）
    37. 	if (kv.first < parent->_kv.first) //新结点的key值小于parent的key值
    38. 	{
    39. 		//插入到parent的左边
    40. 		parent->_left = cur;
    41. 		cur->_parent = parent;
    42. 	}
    43. 	else //新结点的key值大于parent的key值
    44. 	{
    45. 		//插入到parent的右边
    46. 		parent->_right = cur;
    47. 		cur->_parent = parent;
    48. 	}
    49.  
    50. 	//3、若插入结点的父结点是红色的，则需要对红黑树进行调整
    51. 	while (parent&&parent->_col == RED)
    52. 	{
    53. 		Node* grandfather = parent->_parent; //parent是红色，则其父结点一定存在
    54. 		if (parent == grandfather->_left) //parent是grandfather的左孩子
    55. 		{
    56. 			Node* uncle = grandfather->_right; //uncle是grandfather的右孩子
    57. 			if (uncle&&uncle->_col == RED) //情况1：uncle存在且为红
    58. 			{
    59. 				//颜色调整
    60. 				parent->_col = uncle->_col = BLACK;
    61. 				grandfather->_col = RED;
    62.  
    63. 				//继续往上处理
    64. 				cur = grandfather;
    65. 				parent = cur->_parent;
    66. 			}
    67. 			else //情况2+情况3：uncle不存在 + uncle存在且为黑
    68. 			{
    69. 				if (cur == parent->_left)
    70. 				{
    71. 					RotateR(grandfather); //右单旋
    72.  
    73. 					//颜色调整
    74. 					grandfather->_col = RED;
    75. 					parent->_col = BLACK;
    76. 				}
    77. 				else //cur == parent->_right
    78. 				{
    79. 					RotateLR(grandfather); //左右双旋
    80.  
    81. 					//颜色调整
    82. 					grandfather->_col = RED;
    83. 					cur->_col = BLACK;
    84. 				}
    85. 				break; //子树旋转后，该子树的根变成了黑色，无需继续往上进行处理
    86. 			}
    87. 		}
    88. 		else //parent是grandfather的右孩子
    89. 		{
    90. 			Node* uncle = grandfather->_left; //uncle是grandfather的左孩子
    91. 			if (uncle&&uncle->_col == RED) //情况1：uncle存在且为红
    92. 			{
    93. 				//颜色调整
    94. 				uncle->_col = parent->_col = BLACK;
    95. 				grandfather->_col = RED;
    96.  
    97. 				//继续往上处理
    98. 				cur = grandfather;
    99. 				parent = cur->_parent;
    100. 			}
    101. 			else //情况2+情况3：uncle不存在 + uncle存在且为黑
    102. 			{
    103. 				if (cur == parent->_left)
    104. 				{
    105. 					RotateRL(grandfather); //右左双旋
    106.  
    107. 					//颜色调整
    108. 					cur->_col = BLACK;
    109. 					grandfather->_col = RED;
    110. 				}
    111. 				else //cur == parent->_right
    112. 				{
    113. 					RotateL(grandfather); //左单旋
    114.  
    115. 					//颜色调整
    116. 					grandfather->_col = RED;
    117. 					parent->_col = BLACK;
    118. 				}
    119. 				break; //子树旋转后，该子树的根变成了黑色，无需继续往上进行处理
    120. 			}
    121. 		}
    122. 	}
    123. 	_root->_col = BLACK; //根结点的颜色为黑色（可能被情况一变成了红色，需要变回黑色）
    124. 	return make_pair(newnode, true); //插入成功
    125. }
    126.  
    127.  
    128.  
    129. //左单旋
    130. void RotateL(Node* parent)
    131. {
    132. 	Node* subR = parent->_right;
    133. 	Node* subRL = subR->_left;
    134. 	
    135.  
    136. 	//1、建立parent和subRL之间的关系
    137. 	parent->_right = subRL;
    138. 	if (subRL) //subRL可能为空
    139. 		subRL->_parent = parent;
    140.     
    141.     //2.记录pparent
    142.     Node* pparent = parent->_parent;
    143.    
    144.     //3.建立parent和subR的关系
    145.     subR->_left = parent;
    146.     parent->_parent = subR;
    147.  
    148. 	//4.建立pparent和subR的关系
    149. 	if (pparent == nullptr) //parent为根，是一颗单独的树
    150. 	{
    151. 		_root = subR;
    152. 		subR->_parent = nullptr; //subR的_parent指向需改变
    153. 	}
    154. 	else
    155. 	{
    156. 		if (parent == pparent->_left)
    157. 		{
    158. 			pparent->_left = subR;
    159. 		}
    160. 		else //parent == pparent->_right
    161. 		{
    162. 			pparent->_right = subR;
    163. 		}
    164. 		subR->_parent = pparent;
    165. 	}
    166.  
    167. }
    168.  
    169.   //右单旋
    170.     void RotateR(Node* parent)
    171. 	{
    172.  
    173.         
    174. 		Node* subL = parent->_left;
    175. 		Node* subLR = subL->_right;
    176.  
    177.         //1.建立parent和subLR的关系
    178. 		parent->_left = subLR;           
    179. 		if (subLR) //subLR可能为空
    180. 		{
    181. 			subLR->_parent = parent;
    182. 		}
    183. 		
    184.         //2.记录pparent
    185. 		Node* pparent = parent->_parent;
    186.        
    187.         //3.建立subL和parent的关系
    188. 		subL->_right = parent;             
    189. 		parent->_parent = subL;
    190.  
    191.         
    192.         //4.建立pparen和subL的关系
    193. 		if (parent == _root) //parent是一颗独立的树      
    194. 		{
    195. 			_root = subL;
    196. 			_root->_parent = nullptr;
    197. 		}
    198. 		else //parent是一颗子树，
    199. 		{
    200. 			if (pparent->_left == parent)
    201. 			{
    202. 				pparent->_left = subL;
    203. 			}
    204. 			else
    205. 			{
    206. 				pparent->_right = subL;
    207. 			}
    208.              subL->parent = pparent;
    209. 		}
    210. 		
    211. 	}
    212.  
    213. //左右双旋
    214. void RotateLR(Node* parent)
    215. {
    216. 	RotateL(parent->_left);
    217. 	RotateR(parent);
    218. }
    219.  
    220. //右左双旋
    221. void RotateRL(Node* parent)
    222. {
    223. 	RotateR(parent->_right);
    224. 	RotateL(parent);
    225. }

                    

                            

    5.红黑树验证

    (1)验证二叉树

    • 红黑树也是一种特殊的二叉搜索树，获取二叉树的中序遍历序列，来判断该二叉树是否满足二叉搜索树的性质。 
    1. //中序遍历
    2. void Inorder()
    3. {
    4. 	_Inorder(_root);
    5. }
    6.  
    7. //中序遍历子函数
    8. void _Inorder(Node* root)
    9. {
    10. 	if (root == nullptr)
    11. 		return;
    12. 	_Inorder(root->_left);
    13. 	cout << root->_kv.first << " ";
    14. 	_Inorder(root->_right);
    15. }

                     

    (2)验证红黑树，是否满足那几个性质

    1. //判断是否为红黑树
    2. bool ISRBTree()
    3. {
    4. 	if (_root == nullptr) //空树是红黑树
    5. 	{
    6. 		return true;
    7. 	}
    8.  
    9. 	if (_root->_col == RED)
    10. 	{
    11. 		cout << "error：根结点为红色" << endl;
    12. 		return false;
    13. 	}
    14. 	
    15. 	//找最左路径作为黑色结点数目的参考值
    16. 	Node* cur = _root;
    17. 	int BlackCount = 0;
    18. 	while (cur)
    19. 	{
    20. 		if (cur->_col == BLACK)
    21. 			BlackCount++;
    22.  
    23. 		cur = cur->_left;
    24. 	}
    25.  
    26. 	int count = 0;
    27. 	return _ISRBTree(_root, count, BlackCount);
    28. }
    29.  
    30. //判断是否为红黑树的子函数
    31. bool _ISRBTree(Node* root, int count, int BlackCount)
    32. {
    33. 	if (root == nullptr) //该路径已经走完了
    34. 	{
    35. 		if (count != BlackCount)
    36. 		{
    37. 			cout << "error：黑色结点的数目不相等" << endl;
    38. 			return false;
    39. 		}
    40. 		return true;
    41. 	}
    42.  
    43. 	if (root->_col == RED&&root->_parent->_col == RED)
    44. 	{
    45. 		cout << "error：存在连续的红色结点" << endl;
    46. 		return false;
    47. 	}
    48.  
    49. 	if (root->_col == BLACK)
    50. 	{
    51. 		count++;
    52. 	}
    53. 	return _ISRBTree(root->_left, count, BlackCount) 
    54.         && _ISRBTree(root->_right, count, BlackCount);
    55. }

                            

                     

    6.红黑树的查找

    • 本质还是搜索二叉树的查找
    1. 若树为空树，则查找失败，返回nullptr。
    2. 若key值小于当前结点的值，则应该在该结点的左子树当中进行查找。
    3. 若key值大于当前结点的值，则应该在该结点的右子树当中进行查找。
    4. 若key值等于当前结点的值，则查找成功，返回对应结点。
    1. //查找函数
    2. Node* Find(const K& key)
    3. {
    4. 	Node* cur = _root;
    5. 	while (cur)
    6. 	{
    7. 		if (key < cur->_kv.first) //key值小于该结点的值
    8. 		{
    9. 			cur = cur->_left; //在该结点的左子树当中查找
    10. 		}
    11. 		else if (key > cur->_kv.first) //key值大于该结点的值
    12. 		{
    13. 			cur = cur->_right; //在该结点的右子树当中查找
    14. 		}
    15. 		else //找到了目标结点
    16. 		{
    17. 			return cur; //返回该结点
    18. 		}
    19. 	}
    20. 	return nullptr; //查找失败
    21. }

                            

                     

    7.红黑树和AVL树比较

    红黑树和AVL树都是高效的平衡二叉树，增删查改的时间复杂度都是O(logN)，但红黑树和AVL树控制二叉树平衡的方式不同：

    • AVL树是通过控制左右高度差不超过1来实现二叉树平衡的，实现的是二叉树的严格平衡。
    • 红黑树是通过控制结点的颜色，从而使得红黑树当中最长可能路径不超过最短可能路径的2倍，实现的是近似平衡。

    相对于AVL树来说，红黑树降低了插入结点时需要进行的旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，实际运用时也大多用的是红黑树。
     

                             

  • 相关阅读:
    python命名空间字典
    算法---水壶问题（DFS）
    ActiveMQ、RabbitMQ、Kafka、RocketMQ在事务性消息、性能、高可用和容错、定时消息、负载均衡、刷盘策略的区别
    Centos安装Redis
    Linux--网络编程
    nginx 开机自启(脚本+命令)
    洛谷P5142 区间方差 题解
    基于间隔密度的概念漂移检测算法mdm-DDM
    第三章《数组与循环》第7节：break与continue关键字
    Linux查看磁盘命令df-h详解
  • 原文地址：https://blog.csdn.net/m0_52169086/article/details/126657836