• C++ - 红黑树 介绍 和 实现

    前言

     前面 学习了 AVL树，AVL树虽然在 查找方面始终拥有 O(log N ）的极高效率，但是，AVL 树在插入 ,删除等等 修改的操作当中非常的麻烦，尤其是 删除操作，在实现当中细节非常多，在实现上非常难掌控。具体可以看以下两篇文章：
    C++ - AVL 树 介绍 和 实现 （上篇）_chihiro1122的博客-CSDN博客

    C++ - AVL树实现（下篇）- 调试小技巧_chihiro1122的博客-CSDN博客

     而 红黑树 在构建就下个对容易一些了。

    红黑树 介绍 

    红黑树和 AVL树一样，都是 二叉平衡搜索树，红黑树的构建是在 每个结点除了 孩子的链接关系，和值以外，加一个位置存储该结点的颜色，一个结点的颜色只有   red 和 black 两种。红黑树通过对 任意一条路径上的各个结点的颜色限制，确保没有一条路径会比其他路径长出两倍。

     相比于 AVL树，红黑树对于平衡的要求更加宽松，他只是要求最长路径最多是 最短路径的两倍；

    而 AVL树 是严格限死了 左右子树高度不能超过 2 。

    也就是说，红黑树在高度上 要比 AVL树要高一些。

    虽然 红黑树 在平衡上更加的宽松，但是实际的效率却依旧非常的高，并不比 AVL树差，至于为什么我们在下述来验证。

    而且 ，红黑树不会进行 旋转，尽管在 AVL树当中旋转是常量级的，但是，数量多了之后，还是有很多的消耗。

    在AVL树当中，插入和删除都要经过很多次的旋转。也就造成不小的消耗。

    而 AVL树 相比于 红黑树 多出来的消耗在 红黑树看来是没有必要的。

     如下图当中的分析：

    红黑树树的性质（规则）

    • 每个结点不是红色就是黑色
    •  根节点是黑色的
    • 如果一个节点是红色的，则它的两个孩子结点必须是黑色的 。（每一条从根结点开始的路径，没有重复的红色结点）
    • 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点。（红黑树当中每一条路径上，黑色结点数是相同的）（在一条路径当中，黑色结点的占比一定 大于 或 等于 1 /2 ）
    • 每一个 “叶子结点” 都是黑色的，注意：此处的叶子结点不是我们以前理解的 最后一个结点，在红黑树当中的 这里的 “叶子结点” 实际上是最后一个 NULL 结点（所有的 NIL 结点都是 黑色的）。如下图所示：
       

     在红黑树当中，对 这个 NULL 结点进行了重新定义，取名为 NIL 结点，而且我们上述所说的路径，是指：从根结点到最后的 NIL 结点，为一条路径。

     就比如上述，如果不加上 NULL ，那么计算出来的路径数目就是 5 条；但是如果加上 NULL ，来计算的话就是 11 条，而11 跳才是正确。

     也就是说，如果你不加上最后一个 NULL 结点来用 红黑树的规则来判断 一颗树是不是红黑树的话，机会出错，比如下述例子:
     

     如果，你按照我们以前认为，最后一个结点就是叶子结点，而且在算上路径时候没有加上最后的NULL。那么你就会认为，这是一颗红黑树；

    但，实际上这不是一颗红黑树。 

     其实，按照上述 的 第五条性质，其实就是在每一条路径的后面都加上了 一个 黑色结点。

    insert（）插入函数 

     首先我们来想一下，当一颗红黑树当中已经有结点了，如下所示，那么当我们插入一个结点是插入红色的结点还是 插入一个黑色的结点好呢？

     如果插入 黑色结点就会违反 条件4,；如果插入 红色结点就会违反 条件3；

    如果要违反条件的话，可能是违反 条件3更好。

    因为 ，如果违反条件4，就会影响全部路径；而如果 违反条件3 就只会 影响一个路径，不会是全部路径。

    如下所示，我们插入一个黑色结点：
     

     在插入A结点之后，到A结点的这条路径的 黑色结点的个数就 +1了，但是其他路径上都没有变化，此时就影响到其他 路径了。

    但是如果插入的是一个红色的结点，只影响一个路径，所以，当发生错误的时候我们可以修正：

     上述插入的B结点，在 22 的下面，22 是红色结点，这个位置就不行但是如果是插入在 15 的下面，15 是一个黑色的结点，是可以的。

     如果 红色结点 B 插入到 22 的下面，此时 B 的父亲结点是 红色的，说明B 一定会有 父亲的父亲，也就是说 grandfather。因为 整棵树只有根结点才没有父亲，而根结点必须是 黑色的：

     如上所示，红色结点一定有 父亲。也就是说，出现上述情况的话，grandfather 结点是肯定存在的。

     红黑树的插入，修改过程

     我们上述讨论了，插入的结点必须是红色的结点，插入红色的结点的话，就会影响到父亲（新插入结点的路径）。

     具体例子理解

    所以，此时我们要从该路径上进行修改。

     此时违法的规则就是 B 和 22 两个红色结点连在一起了，所以我们就想着把 22 边黑，但是变黑的话，就会影响这棵树当中的黑节点个数。

    所以，在更新完 25 这颗子树之后，可能会像 AVL 树当中的平衡因子一样往上更新的。

    如上述图，单次对于子树的修改：
    需要先找到 新插入结点 父亲的 亲兄弟（uncle）。

    如果 uncle 存在且为 红，那么就把 parent 和 uncle 都变 黑：

     但是此时我们发现，变黑之后，对于 22 和 27 这两条路径来说，黑色结点个数相比于其他路径，在增多了一个，所以，此时我们在让 grandfather 结点变红，就可以解决黑色结点个数问题：

     但是，对于 grandfather 结点不一定都是这种的处理方法：

    • 如果 grandfather 结点没有父亲，说明此时 grandfather 结点是 整棵树的根结点，那么把 grandfather 结点变红就行。
    • 如果 grandfather 有父亲，grandfather 是 黑色，就结束了。
    • 如果 grandfather 有父亲，grandfather 是 红色，有和上述问题一样了，需要找 uncle。

     我们继续来看上述例子：
     

     在上述修改之后， 发现 17 和 25 又是两个红色结点链接在一起了，此时就要对这个链接关系进行修改，此时就好比是 新插入了 25 结点。

    找 uncle（8），uncle 为红，就把 parent 和 uncle 一起改为黑，此时的 grandfather 没有父亲结点了，就不用再变黑了：

     如果按照上述的过程来修改的话，我们发现，相当于是在每一条路径当中都增加了一个 黑色结点。

    黑色结点其实是有好处的，比如上述的例子的那种，我们插入的新结点一定是 红色的，那么插入在黑色结点后面就不用像上述一样进行修改，如上图所示，我们只有在 6 后面和在 B 后面插入结点才会像上述一样进行修改。

     上述是 有uncle的情况，如果 parent 没有亲兄弟，也就是 cur 没有 uncle的话，应该怎么办呢？

     如上述所示，cur 没有 uncle，我们不能直接把 parent 变黑，因为会多出一个 黑色结点；有人又说，多出来一个黑色结点的话，把 grandfather 在变 红不就行了，但是 如果把 grandfather 变红的话，指向 uncle 的路径上就少一个 黑色结点了。

    而且我们发现，如果在 cur 位置插入的话，13 的右子树的上的路径长度已经比 左子树 上的路径长度多出 2 倍了。

    所以，不管是否 多出 2 倍，在没有 uncle的情况下，我们应该进行旋转来调整位置。

    判断旋转方式还是和在 AVL树当中判断方式一样，旋转方式请看一下博客:

    C++ - AVL 树 介绍 和 实现 （上篇）_chihiro1122的博客-CSDN博客

     像上述，就是发生了的右单旋，但是旋转之后发现，颜色上还是 违反了规则。

    所以此时要变色。

    所以，当uncle 不存在的时候，处理规则就是 旋转 + 变色。 

     uncle存在且为红的情况，在修改之后也有可能会出现 最长路径和最短路径 长度超过两倍的情况（uncle 为黑的情况）：
     

     修改：

     此时我们发现，如果我们单纯的把 17 变黑，已经不能解决问题了，此时也是需要旋转的。

    13 的右子树已经明显的高了，要对右子树进行旋转，此时发生左单旋。如果是下述情况就是 双旋：
     

     cur ， parent ， grandfather 构成折线，就要发生双旋。

    但是，在 AVL 树当中我们判断旋转的方式是利用 平衡因子的方式来判断的，但是在红黑树当中没有平衡因子，我们需要判断  cur ， parent ， grandfather 三者的链接关系来 确认要哪一种旋转。

     我没发现，红黑树优势不仅仅在于旋转变少了，他是在修改过程当中就会把很多结点变黑，那么在以后插入当中，插入到黑节点后面就不必再进行修改了。

     小总结：

    红黑树的插入，关键看 uncle。

    • 如果 uncle 存在且为红，变色+ 往上进行处理
    • 如果 uncle存在且为黑，旋转+变色+往上进行处理
    • 如果 uncle不存在，旋转 + 变色 + 往上进行处理

     抽象图理解 红黑树插入过程

     按照上述说明，出现需要修改的情况，都是 红红黑的结构，也就是 cur 为红， parent 为红，grandfather 为黑的情况，而修改过程当中，判别不用的修改方式，是看 uncle 的。

    我们先来总结一下 解决方案：

    • 情况一: cur为红，p为红，g为黑，u存在且为红。                                                                                                                                                                                                                                       解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。                                  
    • 情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑。                                                                                                                                                                                                                         解决方法：p为g的左孩子，cur为p的左孩子，则进行右单旋转；                                                               p为g的右孩子，cur为p的右孩子，则进行左单旋转。                                                               p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；                                                           p为g的右孩子，cur为p的左孩子，则针对p做右单旋转

    具体情况分析：

    情况一：

     比如上述是 的抽象图，他可能是 一颗子树，也可能是 整棵树。

    那么，当我们在 a ，b 后面插入的话，可能就会应发 情况一：

    当 c/d/e 子树每条路径当中只有 一个 黑色结点：

     如上述情况我们就要使用 情况一的处理方式了。

     对于情况一，因为不旋转，对于新结点的插入位置，是不管的，主要是 在 a 和 b 的四个位置插入都是引发情况一，或者不引发。

    至于 cur 可能本来就是 grandfather 的黑色结点，只是在 a，b当中没有个进行修改，把 grandfather 修改为了 红色。

    当然，还有 cur 本来就是 新增结点的情况，也就是 a  和 b 两个子树都是 空：

     但是处理方式还是情况一的方式。

     当 c/d/e 子树每条路径当中有两个黑色结点：

     

     c/d/e 子树每条路径当中有两个黑色结点的情况太多了，上图当中只是简单列出一些。

    在 上述 只有一个黑结点的路径当中，只用一层就修改，就修改到了 cur 结点；而在当前 路径当中有两个黑结点，就是修改两层，才修改到 cur 结点的颜色的。（这里的层，一层就是 一个 cur parent grandfather 组合子树）

     反正就是 路径当中有两个黑色结点的情况，要比 只有一个黑结点的情况复杂得多，但是最终还是属于情况一，都是使用 情况一的方式来进行解决。

     情况二：

     情况二当中的uncle有两种情况：
    一种是 uncle不存在：

     如果 uncle 不存在，那么 cur 一定是新插入的结点，因为如果 cur 不是新插入结点，那么 cur 和 p 当中一定至少有一个是 黑色的。

     另一种是 uncle 的颜色是 黑色：

     如果 uncle 是黑色的话，cur 这个结点一定不是 新插入的结点，因为，假设在插入之前，也就相当于是没有 cur 这个结点，g - > p -> null 路径 和  g -> u -> ········ 路径 两个路径上 黑色结点个数不一样。所以，插入之前的树不可能是红黑树。

    所以，uncle 为黑的这种情况，一定是  cur 当中的子树发生了修改，往上修改的时候影响到了 cur ：

     修改过程如下：都是旋转 + 变色的方式。只不过旋转当中有四种方式，具体要看 cur parent grandfather 三者之间的链接关系。

      像上述这种情况， c 子树的路径当中每条之后一个黑结点，d 和 e 可能为空，也可能有一个 红结点。

     同样的，c  d  e 三个子树当中的黑色结点可以按照上述的规律增加，那么就是不同的具体例子。

    比如，c是 两个黑色结点的红黑树，那么 d 和 e 就是一个结点的红黑树。

     红黑树的结果是无穷无尽的，每一种结构也相对复杂，但是上述都是属于 情况二，解决方式都是一样的。

    • 情况二当中，旋转+变色之后，就不需要网上进行处理了，为在旋转+变色之后，这棵子树的根结点一定是 黑色的，不会是 红色的，那么黑色的结点不管和 红色的结点还是和 黑色的结点链接都是不会出现问题的。
    • 在情况一当中之所以要继续往上更新，是因为，情况一修改出来的根结点是红色的。

     红黑树的验证

     红黑树的检测分为两步：

    • 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
    •  检测其是否满足红黑树的性质

     检测是否满足红黑树性质：
     

    1.  
    2. 	bool CheckColor(Node* root, int blacknum, int benchamark)
    3. 	{
    4. 		// 当走到叶子结点的 null 指针处，也就是 NIL结点处
    5. 		if (root == nullptr)
    6. 		{
    7. 			// 如果计算出的路径黑色结点长度 和 外部计算的不一样
    8. 			// 说明不是红黑树
    9. 			if (blacknum != benchamark)
    10. 			{
    11. 				cout << "路径黑色结点个数不一样" << endl;
    12. 				return false;
    13. 			}
    14. 			return true;
    15. 		}
    16.  
    17. 		// 用于递归计算 路径的黑色结点个数
    18. 		if (root->_color == BLACK)
    19. 			blacknum++;
    20.  
    21. 		// 如果当前结点为 红色，且当前结点的父亲也是红色，就不是红黑树
    22. 		if (root->_parent && root->_parent->_color == RED && root->_color == RED)
    23. 		{
    24. 			cout << "有连续红色" << endl;
    25. 			return false;
    26. 		}
    27.  
    28. 		// 左右子树递归
    29. 		return CheckColor(root->_left, blacknum, benchamark)
    30. 			&& CheckColor(root->_right , blacknum, benchamark);
    31. 	}
    32.  
    33. 	// 外部调用接口
    34. 	bool isBalance()
    35. 	{
    36. 		return isBalance(_root);
    37. 	}
    38.  
    39. 	// 内部封装函数
    40. 	bool isBalance(Node* root)
    41. 	{
    42. 		if (root == nullptr)
    43. 			return true;
    44.  
    45. 		// 如果整棵树的 根结点不是 黑色的就不是红黑树
    46. 		if (root->_color != BLACK)
    47. 		{
    48. 			cout << "根结点不是黑色" << endl;
    49. 			return false;
    50. 		}
    51.  
    52. 		// 基准值
    53. 		// 在递归外部计算出左路第一条路径的 黑色结点值
    54. 		int benchmark = 0;
    55. 		Node* cur = root;
    56. 		while(cur)
    57. 		{
    58. 			if (cur->_color == BLACK)
    59. 				benchmark++;
    60. 			cur = cur->_left;
    61. 		}
    62.  
    63. 		return CheckColor(root, 0, benchmark);
    64. 	}

    我们使用两个函数相互调用来实现，外层函数判断整棵树的根结点是不是 黑色的；

    而且计算左边第一条路径的黑色结点个数。其实可以随便找一条路径，因为这个只是一个基准值，不需要是正确的，因为红黑树当中的每一条路径都需要黑色结点数相同。

    然后用内层函数递归遍历红黑树。

    内层函数当中，计算出每一条黑色结点的个数；判断是否有连续的红色结点；

    检测其是否满足二叉搜索树，就直接中序遍历打印就行了，这里就不实现了。

     红黑树的删除

    红黑树的删除和 AVL树一样，都比插入要复杂，可以看下面这个博客来了解：
    红黑树 - _Never_ - 博客园 (cnblogs.com)

    完整代码实现

     

    1. #pragma once
    2.  
    3. // 节点的颜色
    4. enum Color { RED, BLACK };
    5.  
    6. // 红黑树节点的定义
    7. template<class K, class V>
    8. struct RBTreeNode
    9. {
    10. 	RBTreeNode(pair kv  , Color color = RED)
    11. 		: _left(nullptr), _right(nullptr), _parent(nullptr)
    12. 		, _kv(kv), _color(color)
    13. 	{}
    14. 	RBTreeNode* _left; // 节点的左孩子
    15. 	RBTreeNode* _right; // 节点的右孩子
    16. 	RBTreeNode* _parent; // 节点的双亲(红黑树需要旋转，为了实现简单给出该字段)
    17. 	pair _kv; // 节点的值域
    18. 	Color _color; // 节点的颜色
    19. };
    20.  
    21. template<class K ,class V>
    22. class RBTree
    23. {
    24. 	typedef RBTreeNode Node;
    25. public:
    26. 	bool insert(pair kv)
    27. 	{
    28. 		// 搜索二叉树的插入逻辑
    29. 		// 
    30. 		// 如果当前树为空，直接用头指针只想新结点
    31. 		if (_root == nullptr)
    32. 		{
    33. 			_root = new Node(kv);
    34. 			_root->_color = BLACK;
    35. 			return true;
    36. 		}
    37.  
    38. 		// 不为空接着走
    39. 		Node* cur = _root;    // 用于首次插入时候指针的迭代
    40. 		Node* parent = nullptr;
    41.  
    42. 		while (cur)
    43. 		{
    44. 			// 如果当前新插入的 key 值比 当前遍历的结点 key 值大
    45. 			if (cur->_kv.first < kv.first)
    46. 			{
    47. 				// 往右迭代器
    48. 				parent = cur;
    49. 				cur = cur->_right;
    50. 			}
    51. 			// 反之
    52. 			else if (cur->_kv.first > kv.first)
    53. 			{
    54. 				parent = cur;
    55. 				cur = cur->_left;
    56. 			}
    57. 			else
    58. 			{
    59. 				// 如果相等，就不插入，即插入失败
    60. 				return false;
    61. 			}
    62. 		}
    63.  
    64. 		// 此时已经找到 应该插入的位置
    65. 		cur = new Node(kv);
    66. 		cur->_color = RED;
    67. 		// 再次判断大小，判断 cur应该插入到 parent 的那一边
    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 指针
    78. 		cur->_parent = parent;
    79.  
    80. 		// 红黑树调整高度（平衡高度）的逻辑
    81. 		while (parent && parent->_color == RED)
    82. 		{
    83. 			// parent 为 红，parent->_parent 一定不为空
    84. 			Node* grandfather = parent->_parent;
    85. 			// 如果父亲是在 祖父的左
    86. 			if (parent == grandfather->_left)
    87. 			{
    88. 				Node* uncle = grandfather->_right;
    89.  
    90. 				// 叔叔存在且为红
    91. 				if (uncle && uncle->_color == RED)
    92. 				{
    93. 					// 变色
    94. 					parent->_color = uncle->_color = BLACK;
    95. 					grandfather->_color = RED;
    96.  
    97. 					// 向上迭代
    98. 					cur = grandfather;
    99. 					parent = cur->_parent;
    100. 				}
    101. 				// uncle 不存在 或者 存在且为黑
    102. 				else
    103. 				{
    104. 					if (cur == parent->_left)
    105. 					{
    106. 						//       g
    107. 						//     p
    108. 						//  c
    109. 						RotateR(grandfather);
    110. 						parent->_color = BLACK;
    111. 						grandfather->_color = RED;
    112. 					}
    113. 					else  // cur == parent->_right
    114. 					{
    115. 						//       g
    116. 						//     p
    117. 						//         c
    118. 						RotateL(parent);
    119. 						RotateR(grandfather);
    120.  
    121. 						cur->_color = BLACK;
    122. 						grandfather->_color = RED;
    123. 					}
    124.  
    125. 					break; // 不需要再往上更新
    126. 				}
    127. 				
    128. 			}
    129.  
    130. 			else  // parent = grandfather->_right
    131. 			{
    132. 				Node* uncle = grandfather->_left;
    133. 				// uncle 存在 且 uncle 的颜色是红色
    134. 				if (uncle && uncle->_color == RED)
    135. 				{
    136. 					parent->_color = uncle->_color = BLACK;
    137. 					grandfather->_color = RED;
    138.  
    139. 					cur = grandfather;
    140. 					parent = cur->_parent;
    141. 				}
    142. 				else // 不存在 或者 存在且为黑色
    143. 				{
    144. 					if (cur == parent->_right)
    145. 					{
    146. 						//  g
    147. 						//     p
    148. 						//        c
    149. 						RotateL(grandfather);
    150. 						parent->_color = BLACK;
    151. 						grandfather->_color = RED;
    152. 					}
    153. 					else // cur = parent->_left
    154. 					{
    155. 						//   g
    156. 						//     p
    157. 						//  c
    158. 						RotateR(parent);
    159. 						RotateL(grandfather);
    160.  
    161. 						cur->_color = BLACK;
    162. 						grandfather->_color = RED;
    163. 					}
    164.  
    165. 					break; // 不用再往上更新
    166. 				}
    167. 			}
    168. 		}
    169.  
    170. 		// 不管上述如何修改，红黑树的根结点永远是黑的
    171. 		// 所以我们这里既直接硬性处理
    172. 		_root->_color = BLACK;
    173. 		return true;
    174.  
    175. 	}
    176.  
    177. 	void RotateL(Node* parent)
    178. 	{
    179. 		Node* cur = parent->_right; // 存储 parent 的右孩子
    180. 		Node* curleft = cur->_left; // 存储 cur 的左孩子
    181.  
    182. 		parent->_right = curleft;
    183. 		if (curleft)                // 判断 cur 的左孩子是否为空
    184. 		{
    185. 			curleft->_parent = parent;  // 不为空就 修改 cur 的左孩子的_parent 指针
    186. 		}
    187.  
    188. 		cur->_left = parent;
    189. 		// 留存一份 根结点指针
    190. 		Node* ppnode = parent->_parent;
    191.  
    192. 		parent->_parent = cur;
    193.  
    194. 		// 如果parent 是根结点
    195. 		if (parent == _root)
    196. 		{
    197. 			_root = cur;
    198. 			cur->_parent = nullptr;
    199. 		}
    200. 		else
    201. 		{
    202. 			if (ppnode->_left == parent)
    203. 			{
    204. 				ppnode->_left = cur;
    205. 			}
    206. 			else
    207. 			{
    208. 				ppnode->_right = cur;
    209.  
    210. 			}
    211.  
    212. 			cur->_parent = ppnode;
    213. 		}
    214. 	}
    215.  
    216. 	void RotateR(Node* parent)
    217. 	{
    218. 		Node* cur = parent->_left;
    219. 		Node* curRight = cur->_right;
    220.  
    221. 		parent->_left = curRight;
    222. 		if (curRight)
    223. 		{
    224. 			curRight->_parent = parent;
    225. 		}
    226.  
    227. 		cur->_right = parent;
    228. 		Node* ppnode = parent->_parent;
    229. 		parent->_parent = cur;
    230.  
    231. 		if (parent == _root)
    232. 		{
    233. 			_root = cur;
    234. 			cur->_parent = nullptr;
    235. 		}
    236. 		else
    237. 		{
    238. 			if (ppnode->_left == parent)
    239. 			{
    240. 				ppnode->_left = cur;
    241. 			}
    242. 			else
    243. 			{
    244. 				ppnode->_right = cur;
    245. 			}
    246.  
    247. 			cur->_parent = ppnode;
    248. 		}
    249. 	}
    250.  
    251. 	bool CheckColor(Node* root, int blacknum, int benchamark)
    252. 	{
    253. 		// 当走到叶子结点的 null 指针处，也就是 NIL结点处
    254. 		if (root == nullptr)
    255. 		{
    256. 			// 如果计算出的路径黑色结点长度 和 外部计算的不一样
    257. 			// 说明不是红黑树
    258. 			if (blacknum != benchamark)
    259. 			{
    260. 				cout << "路径黑色结点个数不一样" << endl;
    261. 				return false;
    262. 			}
    263. 			return true;
    264. 		}
    265.  
    266. 		// 用于递归计算 路径的黑色结点个数
    267. 		if (root->_color == BLACK)
    268. 			blacknum++;
    269.  
    270. 		// 如果当前结点为 红色，且当前结点的父亲也是红色，就不是红黑树
    271. 		if (root->_parent && root->_parent->_color == RED && root->_color == RED)
    272. 		{
    273. 			cout << "有连续红色" << endl;
    274. 			return false;
    275. 		}
    276.  
    277. 		// 左右子树递归
    278. 		return CheckColor(root->_left, blacknum, benchamark)
    279. 			&& CheckColor(root->_right , blacknum, benchamark);
    280. 	}
    281.  
    282. 	// 外部调用接口
    283. 	bool isBalance()
    284. 	{
    285. 		return isBalance(_root);
    286. 	}
    287.  
    288. 	// 内部封装函数
    289. 	bool isBalance(Node* root)
    290. 	{
    291. 		if (root == nullptr)
    292. 			return true;
    293.  
    294. 		// 如果整棵树的 根结点不是 黑色的就不是红黑树
    295. 		if (root->_color != BLACK)
    296. 		{
    297. 			cout << "根结点不是黑色" << endl;
    298. 			return false;
    299. 		}
    300.  
    301. 		// 基准值
    302. 		// 在递归外部计算出左路第一条路径的 黑色结点值
    303. 		int benchmark = 0;
    304. 		Node* cur = root;
    305. 		while(cur)
    306. 		{
    307. 			if (cur->_color == BLACK)
    308. 				benchmark++;
    309. 			cur = cur->_left;
    310. 		}
    311.  
    312. 		return CheckColor(root, 0, benchmark);
    313. 	}
    314. private:
    315. 	Node* _root = nullptr;
    316. };

  • 相关阅读:
    can 接口调试am3352
    最新友盟微信，QQ与微博分享集成方案
    (STM32)从零开始的RT-Thread之旅--基础项目构建与时钟配置
    用openhub无法拿到query里面信息对象的文本
    封装一个websocket，支持断网重连、心跳检测，拿来开箱即用
    Gitlab升级记录（12.10.0-13.0.6）
    heapdump泄露Shiro key从而RCE
    linux-day01
    小程序 | 小程序后端用什么语言开发比较好
    VC中对话框的句柄均为NULL
  • 原文地址：https://blog.csdn.net/chihiro1122/article/details/133135161