• C++红黑树--110203

    红黑树

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

    性质

    1. 每个节点，非黑即红。
    2. 根节点必须为黑。
    3. 如果一个结点是红色的，它的两个子节点一定是黑色的。（树中没有连续的红色节点）
    4. 对于每一条路径而言，黑色节点的个数都是相同的。（AVL树的性质遭到破坏时，一定会发生旋转操作。红黑树在某些情况可以只变色）
    5. 每个叶子节点都是黑色的。（指的是空节点）

    红黑树节点

    1. enum Color
    2. {
    3. 	RED,
    4. 	BLACK
    5. };
    6.  
    7. //红黑树节点结构体
    8. template<class K,class V>
    9. class RBTreeNode
    10. {
    11. public:
    12. 	RBTreeNode* _left;
    13. 	RBTreeNode* _right;
    14. 	RBTreeNode* _parent;
    15. 	pair _kv;
    16. 	Color _col;
    17.  
    18. 	RVTreeNode(const pair& kv)
    19. 		:_left(nullptr)
    20. 		, _right(nullptr)
    21. 		, _parent(nullptr)
    22. 		, _kv(kv)
    23. 	{}
    24.  
    25. };

    红黑树的插入实现

    1. template<class K, class V>
    2. struct RBTree
    3. {
    4. 	typedef RBTreeNode Node;
    5. public:
    6.     bool Insert(const pair& kv);
    7.     /...
    8. private:
    9.     Node* _root=nullptr;
    10. };

    问题：

    插入节点时，红黑树需要调整颜色/或者旋转，那我插入的新节点应该是默认红色还是黑色呢？

     默认红色，可能违反规则3。默认黑色，一定违反规则4。而且想要调节规则四更为麻烦，所以默认插入的新节点都是红色。

    发现：

    只有当parent为红时，才会有变色/旋转等操作。

    若parent为黑，直接插入一个红节点，最后将_root置黑即可。

    情况一：单纯变色

    1.p为红，g为黑，u存在且为红 ，cur是新插入的，且为红

    2.p为红，g为黑，u存在且为红 ，cur是变红的。

    此时 c  d e 可以为以下四种

     处理方案：p和u变黑，g变红。再将g赋给cur，继续向上调整

    1. bool Insert(const pair&kv) 
    2. {
    3.     //查找新节点位置与之前二叉搜索树和AVL树相似，具体代码会在最后
    4.     //....
    5. //省略了找了位置 并创建了cur节点 链接到了parent 
    6. //如果parent不是红色的 直接放就行了 最后把根节点置黑
    7. while (parent && parent->_col == RED)
    8. {
    9. 	Node* grandfater = parent->_parent;
    10. 	assert(grandfater);
    11. 	assert(grandfater->_col == BLACK);
    12. 	// 关键看叔叔
    13. 	if (parent == grandfater->_left)
    14. 	{
    15. 		Node* uncle = grandfater->_right;
    16. 		// 情况一 : uncle存在且为红，变色+继续往上处理
    17. 			if (uncle && uncle->_col == RED)
    18. 			{
    19. 				parent->_col = uncle->_col = BLACK;
    20. 				grandfater->_col = RED;
    21. 				// 继续往上处理
    22. 				cur = grandfater;
    23. 				parent = cur->_parent;
    24. 			}
    25. 			else 
    26. 			{
    27. 				//其他情况
    28. 			}
    29.     }
    30. }
    31. _root->_col=BLACK;
    32. return true;
    33. }

    情况二：单选+变色

    cur为红，p为红，p为黑，u不存在或存在为黑。抽象图如下

    1.u不存在。因为保证红黑树的相关规则，abcde必须全为空，此时cur是新插入的且为红

     2.u存在且为黑，此时cur是变红的

    2的A情况： cur在较高左子树的左边

     未插入时 （左边）c是四种情况之一，d、e要么红要么空

    插入后（右边）a、b、c一定有黑

    处理：单选+变色

    对g进行右单选，p变黑，g变红

     代码

    1. bool Insert(const pair&kv) 
    2. {
    3.     //...
    4.     while (parent && parent->_col == RED)
    5.     {
    6. 	    //...
    7. 	    if (parent == grandfater->_left)
    8. 	    {
    9. 		    Node* uncle = grandfater->_right;
    10. 		        if (uncle && uncle->_col == RED)
    11. 			    {
    12. 				   //...
    13. 			    }
    14. 			    else 
    15. 			    {
    16. 				    // 情况二：右单旋+变色
    17. 					//     g 
    18. 					//   p   u
    19. 					// c
    20. 					if (cur == parent->_left)
    21. 					{
    22. 						RotateR(grandfater);
    23. 						parent->_col = BLACK;
    24. 						grandfater->_col = RED;
    25. 					}
    26.                     else
    27.                     { 
    28.                         //情况三 ：双旋+变色
    29.                         //   g
    30.                         // p   u
    31.                         //  c
    32.                         RotateL(parent);
    33. 					    RotateR(grandfater);
    34. 					    cur->_col = BLACK;
    35. 					    grandfater->_col = RED;
    36.                     }
    37. 			    }
    38.         }
    39.         else
    40.         {    
    41.             //无非是cur跑到右树了  parent==grandfather->_right 思想是一样的
    42.         }
    43.     }
    44. _root->_col=BLACK;
    45. return true;
    46. }

    情况三：双旋+变色

    cur为红，p为红，p为黑，u不存在或存在为黑。抽象图如下

    1.u不存在  所以a、b、c、d、e均不存在 cur是新增节点且为红

    2.u存在且为黑  cur是变红的

     

     代码：

    1. bool Insert(const pair&kv) 
    2. {
    3.     //...
    4.     while (parent && parent->_col == RED)
    5.     {
    6. 	    //...
    7. 	    if (parent == grandfater->_left)
    8. 	    {
    9. 		    Node* uncle = grandfater->_right;
    10. 		        if (uncle && uncle->_col == RED)
    11. 			    {
    12. 				   //...
    13. 			    }
    14. 			    else 
    15. 			    {
    16. 					if (cur == parent->_left)
    17. 					{
    18.                     //...
    19. 					}
    20.                     else
    21.                     { 
    22.                         //情况三 ：双旋+变色
    23.                         //   g
    24.                         // p   u
    25.                         //  c
    26.                         RotateL(parent);
    27. 					    RotateR(grandfater);
    28. 					    cur->_col = BLACK;
    29. 					    grandfater->_col = RED;
    30.                     }
    31. 			    }
    32.         }
    33.         else
    34.         {    
    35.             //无非是cur跑到右树了  parent==grandfather->_right 思想是一样的
    36.         }
    37.     }
    38. _root->_col=BLACK;
    39. return true;
    40. }

    红黑树的插入实现完整版

    1. bool Insert(const pair& kv)
    2. 	{
    3. 		if (_root == nullptr)
    4. 		{
    5. 			_root = new Node(kv);
    6. 			_root->_col = BLACK;
    7. 			return true;
    8. 		}
    9.  
    10. 		Node* parent = nullptr;
    11. 		Node* cur = _root;
    12. 		while (cur)
    13. 		{
    14. 			if (cur->_kv.first < kv.first)
    15. 			{
    16. 				parent = cur;
    17. 				cur = cur->_right;
    18. 			}
    19. 			else if (cur->_kv.first > kv.first)
    20. 			{
    21. 				parent = cur;
    22. 				cur = cur->_left;
    23. 			}
    24. 			else
    25. 			{
    26. 				return false;
    27. 			}
    28. 		}
    29.  
    30. 		cur = new Node(kv);
    31. 		cur->_col = RED;
    32.  
    33. 		if (parent->_kv.first < kv.first)
    34. 		{
    35. 			parent->_right = cur;
    36. 		}
    37. 		else
    38. 		{
    39. 			parent->_left = cur;
    40. 		}
    41.  
    42. 		cur->_parent = parent;
    43.  
    44. 		while (parent && parent->_col == RED)
    45. 		{
    46. 			Node* grandfater = parent->_parent;
    47. 			assert(grandfater);
    48. 			assert(grandfater->_col == BLACK);
    49. 			// 关键看叔叔
    50. 			if (parent == grandfater->_left)
    51. 			{
    52. 				Node* uncle = grandfater->_right;
    53. 				// 情况一 : uncle存在且为红，变色+继续往上处理
    54. 				if (uncle && uncle->_col == RED)
    55. 				{
    56. 					parent->_col = uncle->_col = BLACK;
    57. 					grandfater->_col = RED;
    58. 					// 继续往上处理
    59. 					cur = grandfater;
    60. 					parent = cur->_parent;
    61. 				}// 情况二+三：uncle不存在 + 存在且为黑
    62. 				else
    63. 				{
    64. 					// 情况二：右单旋+变色
    65. 					//     g 
    66. 					//   p   u
    67. 					// c
    68. 					if (cur == parent->_left)
    69. 					{
    70. 						RotateR(grandfater);
    71. 						parent->_col = BLACK;
    72. 						grandfater->_col = RED;
    73. 					}
    74. 					else
    75. 					{
    76. 						// 情况三：左右单旋+变色
    77. 						//     g 
    78. 						//   p   u
    79. 						//     c
    80. 						RotateL(parent);
    81. 						RotateR(grandfater);
    82. 						cur->_col = BLACK;
    83. 						grandfater->_col = RED;
    84. 					}
    85.  
    86. 					break;
    87. 				}
    88. 			}
    89. 			else // (parent == grandfater->_right)
    90. 			{
    91. 				Node* uncle = grandfater->_left;
    92. 				// 情况一
    93. 				if (uncle && uncle->_col == RED)
    94. 				{
    95. 					parent->_col = uncle->_col = BLACK;
    96. 					grandfater->_col = RED;
    97. 					// 继续往上处理
    98. 					cur = grandfater;
    99. 					parent = cur->_parent;
    100. 				}
    101. 				else
    102. 				{
    103. 					// 情况二：左单旋+变色
    104. 					//     g 
    105. 					//   u   p
    106. 					//         c
    107. 					if (cur == parent->_right)
    108. 					{
    109. 						RotateL(grandfater);
    110. 						parent->_col = BLACK;
    111. 						grandfater->_col = RED;
    112. 					}
    113. 					else
    114. 					{
    115. 						// 情况三：右左单旋+变色
    116. 						//     g 
    117. 						//   u   p
    118. 						//     c
    119. 						RotateR(parent);
    120. 						RotateL(grandfater);
    121. 						cur->_col = BLACK;
    122. 						grandfater->_col = RED;
    123. 					}
    124.  
    125. 					break;
    126. 				}
    127. 			}
    128.  
    129. 		}
    130.  
    131. 		_root->_col = BLACK;
    132. 		return true;
    133. 	}

    左旋和右旋

    和AVL树的差不多 只是把修改平衡因子的代码删掉了

    1. 	void RotateL(Node* parent)
    2. 	{
    3. 		Node* subR = parent->_right;
    4. 		Node* subRL = subR->_left;
    5.  
    6. 		parent->_right = subRL;
    7. 		if (subRL)
    8. 			subRL->_parent = parent;
    9.  
    10. 		Node* ppNode = parent->_parent;
    11.  
    12. 		subR->_left = parent;
    13. 		parent->_parent = subR;
    14.  
    15. 		if (_root == parent)
    16. 		{
    17. 			_root = subR;
    18. 			subR->_parent = nullptr;
    19. 		}
    20. 		else
    21. 		{
    22. 			if (ppNode->_left == parent)
    23. 			{
    24. 				ppNode->_left = subR;
    25. 			}
    26. 			else
    27. 			{
    28. 				ppNode->_right = subR;
    29. 			}
    30.  
    31. 			subR->_parent = ppNode;
    32. 		}
    33.  
    34. 	}
    35.  
    36. 	void RotateR(Node* parent)
    37. 	{
    38. 		Node* subL = parent->_left;
    39. 		Node* subLR = subL->_right;
    40.  
    41. 		parent->_left = subLR;
    42. 		if (subLR)
    43. 		{
    44. 			subLR->_parent = parent;
    45. 		}
    46.  
    47. 		Node* ppNode = parent->_parent;
    48.  
    49. 		subL->_right = parent;
    50. 		parent->_parent = subL;
    51.  
    52. 		if (_root == parent)
    53. 		{
    54. 			_root = subL;
    55. 			subL->_parent = nullptr;
    56. 		}
    57. 		else
    58. 		{
    59. 			if (ppNode->_left == parent)
    60. 			{
    61. 				ppNode->_left = subL;
    62. 			}
    63. 			else
    64. 			{
    65. 				ppNode->_right = subL;
    66. 			}
    67.  
    68. 			subL->_parent = ppNode;
    69. 		}
    70.  
    71. 	}

     红黑树的检验方法

    1. template<class K, class V>
    2. struct RBTree
    3. {
    4. 	typedef RBTreeNode Node;
    5. public:
    6.     bool Insert(const pair& kv)
    7.     {    //...
    8.     }
    9. 	bool IsBalance()
    10. 	{
    11. 		if (_root == nullptr)
    12. 		{
    13. 			return true;
    14. 		}
    15.  
    16. 		if (_root->_col == RED)
    17. 		{
    18. 			cout << "根节点不是黑色" << endl;
    19. 			return false;
    20. 		}
    21.  
    22. 		// 黑色节点数量基准值
    23. 		int benchmark = 0;
    24. 		Node* cur = _root;
    25. 		while (cur)
    26. 		{
    27. 		if (cur->_col == BLACK)
    28. 		++benchmark;
    29.  
    30. 		cur = cur->_left;
    31. 		}
    32.  
    33. 		return PrevCheck(_root, 0, benchmark);
    34. 	}
    35. private:
    36.     void RotateL(Node* parent)
    37.     {//...}
    38.     void RotateR(Node* parent)
    39.     {//...}
    40. 	bool PrevCheck(Node* root, int blackNum, int benchmark)
    41. 	{
    42. 		if (root == nullptr)
    43. 		{
    44. 			if (blackNum != benchmark)
    45. 			{
    46. 				cout << "某条黑色节点的数量不相等" << endl;
    47. 				return false;
    48. 			}
    49. 			else
    50. 			{
    51. 				return true;
    52. 			}
    53. 		}
    54.  
    55. 		if (root->_col == BLACK)
    56. 		{
    57. 			++blackNum;
    58. 		}
    59.  
    60. 		if (root->_col == RED && root->_parent->_col == RED)
    61. 		{
    62. 			cout << "存在连续的红色节点" << endl;
    63. 			return false;
    64. 		}
    65.  
    66. 		return PrevCheck(root->_left, blackNum, benchmark)
    67. 			&& PrevCheck(root->_right, blackNum, benchmark);
    68. 	}
    69. };
    1. void TestRBTree1()
    2. {
    3. 	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 0,5,30,25,20,4,13,30,28,27 };  // 测试双旋平衡因子调节
    4. 	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    5. 	RBTree<int, int> t1;
    6. 	for (auto e : a)
    7. 	{
    8. 		t1.Insert(make_pair(e, e));
    9. 	}
    10.  
    11. 	t1.InOrder();
    12. 	cout << "IsBalance:" << t1.IsBalance() << endl;
    13. }

     

  • 相关阅读:
    Python-正则表达式使用
    TensorFlow开发者认证通过心得
    C++速通LeetCode简单第9题-二叉树的最大深度
    DNS基础之使用dig查询DNS解析过程
    Java学习笔记 --- IO流
    【数据库】事务与并发控制
    惠普打印机驱动安装
    [附源码]Python计算机毕业设计Django儿童早教课程管理系统论文2022
    [附源码]Java计算机毕业设计SSM儿童闲置物品交易网站
    数据集学习笔记(六)：目标检测和图像分割标注软件介绍和使用，并转换成YOLO系列可使用的数据集格式
  • 原文地址：https://blog.csdn.net/qq_68741368/article/details/127667226