• 【数据结构】红黑树实现详解

    在本篇博客中，作者将会带领你使用C++来实现一棵红黑树，此红黑树的实现是基于二叉搜索树和AVLTree一块来讲的，所以在看本篇博客之前，你可以先看看下面这两篇博客

    【C++】二叉搜索树-CSDN博客

    【数据结构】AVLTree实现详解-CSDN博客

    在这棵红黑树中，我们用到了二叉搜索树的插入规则和AVLTree的旋转，所以在本篇博客中，在旋转部分可以直接看AVLTree的博客。

    目录

    一.什么是红黑树 

     1.红黑树的性质

    二.红黑树的实现 

    1.红黑树结点的定义

    2.红黑树类的定义

    3.红黑树的插入 

    ①按二叉搜索树的规则进行插入 

    ②判断红黑树的性质是否被破坏

    ③如果被破坏，则进行调整 

    cur为红，cur_parent为红，grandparent为黑，uncle为红

    cur为红，cur_parent为红，grandparent为黑，uncle为黑\uncle不存在

    uncle不存在 

    uncle存在且为黑

    cur为红，cur_parent为红，grandparent为红，uncle为黑\uncle不存在 

    uncle不存在

    uncle存在且为黑 

    ④ 调整代码

    ⑤最终插入代码 

    ⑥代码分析

    4.红黑树的查找

    5.红黑树的修改 

    三.测试

    四.所有源代码

    blog_RBTree.h

    test.cpp 

    一.什么是红黑树 

    红黑树是一棵二叉搜索树，它的结点不是黑的就是红的，其中它有一个非常重要的特点：

    通过对任何一条从根到叶子的路径上各个结点的着色控制，保证了红黑树没有一条路径会比最短路径长出两倍，达到接近平衡的特点。 

    看到这句话，可能你还云里雾里的，但是不要怕，简单的来说，红黑树的特点就是：找出树中最短的路径和最长的路径，其中这条最长路径的长度不会大于最短路径长度的两倍。

    如下图所示：

    在这棵红黑树中，最短的路径是最左边的那条，长度为3，最长的路径是最右边的那条，长度为4，即4 < 2*3，最长的路径不会大于最短路径的两倍。

     1.红黑树的性质

    那么红黑树是怎么做到上面的这个特点的呢？

    那是因为红黑树需要遵循下面这5条性质：

    1.每个结点不是红的就是黑的

    2.根节点是黑色的

    3.如果一个结点是红色的，那么它的两个孩子一定是黑色的

    4.对于每个结点，从该结点到其所有后代叶结点的路径上，均包含相同数量的黑色结点

    5.每个叶子结点都是黑色的（此处的我叶子结点指的是空结点）

    对于这5条性质来说，可能有一些很难理解，但是不用怕，我们来解释一下。

    对于1、2这两条性质来说，很好理解就字面意思，这里就不做过多的解释，其中最重要的是3、4这两条性质，在下面的红黑树插入讲解中，我们都将会围绕着3、4这两条性质来进行。

    3.如果一个结点是红色的，那么它的两个孩子一定是黑色的。

            其实这个也很好理解，但是这个很重要。其规则如下图所示。

    4.对于每个结点，从该结点到其所有后代叶结点的路径上，均包含相同数量的黑色结点。

             这条规则说的是，从任意一个结点开始，一直往下走，走遍所有可能，这其中会有很多条可能的路径，但是这些路径都有一个特点，就是每条路径上的黑色结点的个数相同。如下图所示。

    5.每个叶子结点都是黑色的（这里的叶子结点指的是空结点），如下图所示。 但是其实这个并不是那么重要，理解就行了。

    那么为什么只要遵循上面这五条性质，就能做到红黑树的特点的呢？红黑树的特点是，最长路径的长度不会大于最短路径的长度的两倍。

    既然红黑树的特点与最短路径和最长路径有关，那么我们来把这两条路径分析一下。

    最短路径：通过这五条性质，我们可以知道在一棵红黑树中，最短路径上，一定全是黑结点。不会再有情况比这种情况要短了。

    最长路径： 对于最长路径来说，由于有性质4，所以在最长路径上，它的黑色结点的个数一定和最短路径的黑色结点个数相同。又由于有性质3，对于最长的路径来说，它一定是黑结点，红结点交替的。所以最长的路径的长度不会大于最短路径的两倍。

    如下图所示

    二.红黑树的实现 

    知道了红黑树的性质和特点，接下来我们可以来实现一棵红黑树了。 

    1.红黑树结点的定义

    在定义红黑树的结点时，与普通的树结点不同的是，这里多了一个_parent指针和一个记录结点颜色的变量。 

    1. 	enum Color
    2. 	{
    3. 		BLACK,
    4. 		RED
    5. 	};
    6.  
    7. 	template<class T>
    8. 	struct TreeNode
    9. 	{
    10. 		//成员变量
    11. 		T _data;//数据
    12. 		TreeNode* _left;
    13. 		TreeNode* _right;
    14. 		TreeNode* _parent;
    15. 		Color _col;//保存结点的颜色
    16.  
    17. 		//构造函数
    18. 		TreeNode(const T& data)
    19. 			:_data(data)
    20. 			,_left(nullptr)
    21. 			,_right(nullptr)
    22. 			,_parent(nullptr)
    23. 			,_col(RED)//每生成一个新结点，都将结点的颜色默认给红色，至于为什么，后面会解释
    24. 		{}
    25. 	};

    2.红黑树类的定义

    对于红黑树类的定义，我们先简单的给出一个构造函数，并将_root根结点赋值为nullptr即可。 

    1. 	template<class T>
    2. 	class RBTree
    3. 	{
    4. 		typedef TreeNode Node;
    5. 	public:
    6. 		//构造函数
    7. 		RBTree()
    8. 			:_root(nullptr)//给根结点一个nullptr
    9. 		{}
    10.  
    11. 	private:
    12. 		Node* _root;
    13. 	};

    3.红黑树的插入 

    接下来就是最重要的部分了，红黑树的插入，对于红黑树的插入，我们可以分为两个过程： 

    1.先按二叉搜索树的插入规则把新结点插入进去先。

    2.插入新结点后，判断红黑树的性质有没有被破坏，如果没有被破坏，则插入直接结束，如果有被破坏，则进行调整处理。

    由于插入结点的函数有点长，所以这里把插入函数分开来实现 。下面是函数的名称以及参数

    bool insert(const T& data)

    ①按二叉搜索树的规则进行插入 

    二叉搜索树的插入规则就是，先不管三七二十一，先把新结点插入进去再说。 

    对于二叉搜索树的插入规则，这里不在多讲，不是很理解的，可以看下面这篇博客，这里面讲到了二叉搜索树的插入实现。我们在这里直接给出代码。

    【C++】二叉搜索树-CSDN博客

    1. 			//如果树为NULL，则直接将新结点给到_root
    2. 			if (_root == nullptr)
    3. 			{
    4. 				_root = new Node(data);
    5. 				_root->_col = BLACK;//把新结点给_root后，要记得把颜色给位BLACK
    6. 				return true;
    7. 			}
    8.  
    9. 			Node* cur = _root;
    10. 			Node* cur_parent = nullptr;
    11. 			while (cur != nullptr)
    12. 			{
    13. 				if (data > cur->_data)
    14. 				{
    15. 					cur_parent = cur;
    16. 					cur = cur->_right;
    17. 				}
    18. 				else if (data < cur->_data)
    19. 				{
    20. 					cur_parent = cur;
    21. 					cur = cur->_left;
    22. 				}
    23. 				else//说明该值已经存在，不进行插入
    24. 				{
    25. 					return false;	
    26. 				}
    27. 			}
    28.  
    29. 			//将新结点插入
    30. 			Node* newnode = new Node(data);
    31. 			if (cur_parent->_data > data)
    32. 			{
    33. 				cur_parent->_left = cur;
    34. 				cur->_parent = cur_parent;
    35. 			}
    36. 			else
    37. 			{
    38. 				cur_parent->_right = cur;
    39. 				cur->_parent = cur_parent;
    40. 			}

    ②判断红黑树的性质是否被破坏

    当插入完结点后，就要判断红黑树的性质是否被破坏，如没有，则插入结束，如果有，则进行调整处理。 

    对于前者没有什么好讨论的，我们在着重于讨论后者。

    红黑树的性质：

    1.每个结点不是红的就是黑的

    2.根节点是黑色的

    3.如果一个结点是红色的，那么它的两个孩子一定是黑色的

    4.对于每个结点，从该结点到其所有后代叶结点的路径上，均包含相同数量的黑色结点

    5.每个叶子结点都是黑色的（此处的我叶子结点指的是空结点）

    首先我们来思考一个问题，如果新增了一个结点，你希望这个新增的结点是红色的还是黑色的呢？

    其实我们希望这个新增的结点是红色的，为什么，我们来从红黑树的性质来分析。

    当我们新插入一个结点的时候，性质1、2、5是绝对不会被破坏的，这应该很好理解。

    被破坏的只有3或者4，当我们插入一个红结点，有可能会破坏性质3，当我们插入一个黑结点，会破坏性质4，如下图所示。

    既然不管插入的是红结点还是黑结点，都会破坏红黑树的性质，那么为什么我们要选择插入红结点呢？

    其实大家凭感觉来判断，应该都会感觉性质3的破坏更好的调整，而性质4的破坏不好调整，因为对于性质4的破坏，我们去给其他路径新增黑结点显然不合理，所以只有给当前路径减少一个黑结点来解决，那么我们把这个新增的结点给成红色即可。

    既然这里已经确定了新增的结点一定为红色，所以对于红黑树的调整，我们都围绕着这个来讲解。 

    ③如果被破坏，则进行调整 

    对于性质3的破坏，我们可以分为下面着三种情况。 

    cur为红，cur_parent为红，grandparent为黑，uncle为红

    上图是其中的一种插入的情况，其中cur刚好是叶子，但是cur也有可能不是叶子，所以我们可以给出这种情况的抽象图。

    对于这种情况，我们的调整过程是这样的：

    把cur_parent和uncle的颜色变为黑色，grandparent的颜色变为红色。如下图所示。

    但是这样的处理后，还会有可能会发生性质破坏，例如grandparent的父结点还是红色，对于这样的情况，我们只需要把grandparent给cur，继续向上处理即可。如下图所示。  

    cur为红，cur_parent为红，grandparent为黑，uncle为黑\uncle不存在

    在这种情况中，又可以分为两种小情况，一种是uncle存在且为黑，一种是uncle不存在。

    uncle不存在 

    先来说说第一种情况，uncle不存在的情况，我们先来看图。 

    对于这种情况来说，cur一定是新插入的结点，因为如果cur不是新插入的结点，那么说明是由情况一调整而来的，那么既然是从情况一调整而来的，那么cur的孩子肯定是黑色，但是这样就不符合性质4：从任意结点开始，每条路径的黑色结点的数量相同。 

    uncle存在且为黑

    接着第二种情况，uncle存在且为黑色，我们先来看图。 

    对于这种情况来说，cur一定不是新插入的结点，因为如果cur是新插入的结点，那么在插入cur之前，这棵红黑树违反了性质4：从任意结点开始，每条路径的黑色结点的个数相同。 

    基于这两种情况，我们可以给出这它们的抽象图，同时它们的调整方法是一样的。 

    对于情况二，我们的处理是对grandparent进行一个右单旋，后调整cur_parent和grandparent的颜色即可。如下图所示。

     

    cur为红，cur_parent为红，grandparent为红，uncle为黑\uncle不存在 

    情况三看上去与情况二类似，其实可以说是，也可以说不是，首先同样的，情况三也可以分为两种情况，一种是uncle不存在，一种是uncle存在且为黑色。 

    uncle不存在

    我们直接来看图。

    也情况二不同的是，它是一个折线。同样的如果uncle不存在，那么cur一定是新插入的结点。 

    uncle存在且为黑 

    同样的，我们直接来看图。 

    对于这种情况来说，cur一定不是新插入的结点，它是由情况一调整过来的 

    基于这两种情况，我们可以给出它的抽象图处理，如下图所示。  

    对于情况三，我们的处理是，先对cur_parent进行一个左单旋，左单旋后，要交换cur和cur_parent，后再对grandparent进行一个右单旋，最后再调整颜色，如下图所示。

     

     

    走到这里，我们所有的情况都已经讲完了，接下来可以编写我们的调整代码了。 

    ④ 调整代码

    注意，我们上面讲到的三种情况没有覆盖到全部情况，因为还有另外三种情况是上面这三种情况的反方向，如情况一的反方向，如下图所示。 

    同样的情况二和情况三也有它们的反方向，这里就不在多讲了，逻辑都是一样的。接下来我们可以来编写我们的调整代码了，我们的调整代码可以分为如上图所示的正反向和反方向来编写。   

    1. 			//调整结点代码
    2. 			while (cur_parent != nullptr && cur_parent->_col == RED)
    3. 			{
    4. 				Node* grandparent = cur_parent->_parent;
    5. 				if (grandparent->_left == cur_parent)//正方向
    6. 				{
    7. 					Node* uncle = grandparent->_right;
    8. 					if (uncle != nullptr && uncle->_col == RED)//情况一,uncle存在且为红
    9. 					{
    10. 						cur_parent->_col = uncle->_col = BLACK;
    11. 						grandparent->_col = RED;
    12. 						//继续向上处理
    13. 						cur = grandparent;
    14. 						cur_parent = cur->_parent;
    15. 					}
    16. 					else//情况二和情况三
    17. 					{
    18. 						//这里情况三经过第一次旋转后可以变成情况二，所以可以先判断是否是情况三
    19. 						if (cur_parent->_right == cur)//这种情况就是情况三
    20. 						{
    21. 							//先进行一个左单旋
    22. 							RotateL(cur_parent);
    23. 							swap(cur, cur_parent);//这里一定要进行交换，不然如果是情况二的，会出现逻辑错误
    24. 						}
    25. 						//代码走到这里就一定是情况二了
    26. 						RotateR(grandparent);
    27. 						cur_parent->_col = BLACK;
    28. 						grandparent->_col = RED;
    29. 						break;
    30. 					}
    31. 				}
    32. 				else if (grandparent->_right == cur_parent)//反方向
    33. 				{
    34. 					Node* uncle = grandparent->_left;
    35. 					if (uncle != nullptr && uncle->_col == RED)//反方向的情况一
    36. 					{
    37. 						cur_parent->_col = uncle->_col = BLACK;
    38. 						grandparent->_col = RED;
    39.  
    40. 						cur = grandparent;
    41. 						cur_parent = cur->_parent;
    42. 					}
    43. 					else//反方向的情况二和情况三
    44. 					{
    45. 						if (cur_parent->_left == cur)
    46. 						{
    47. 							RotateR(cur_parent);
    48. 							swap(cur, cur_parent);
    49. 						}
    50. 						RotateL(grandparent);
    51. 						cur_parent->_col = BLACK;
    52. 						grandparent->_col = RED;
    53. 						break;
    54. 					}
    55. 				}
    56. 			}
    57. 			_root->_col = BLACK;

    ⑤最终插入代码 

    1. 		//插入结点
    2. 		bool insert(const T& data)
    3. 		{
    4. 			//如果树为NULL，则直接将新结点给到_root
    5. 			if (_root == nullptr)
    6. 			{
    7. 				_root = new Node(data);
    8. 				_root->_col = BLACK;//把新结点给_root后，要记得把颜色给位BLACK
    9. 				return true;
    10. 			}
    11.  
    12. 			Node* cur = _root;
    13. 			Node* cur_parent = nullptr;
    14. 			while (cur != nullptr)
    15. 			{
    16. 				if (data > cur->_data)
    17. 				{
    18. 					cur_parent = cur;
    19. 					cur = cur->_right;
    20. 				}
    21. 				else if (data < cur->_data)
    22. 				{
    23. 					cur_parent = cur;
    24. 					cur = cur->_left;
    25. 				}
    26. 				else//说明该值已经存在，不进行插入
    27. 				{
    28. 					return false;	
    29. 				}
    30. 			}
    31.  
    32. 			//将新结点插入
    33. 			cur = new Node(data);
    34. 			if (cur_parent->_data > data)
    35. 			{
    36. 				cur_parent->_left = cur;
    37. 				cur->_parent = cur_parent;
    38. 			}
    39. 			else
    40. 			{
    41. 				cur_parent->_right = cur;
    42. 				cur->_parent = cur_parent;
    43. 			}
    44.  
    45. 			//调整结点代码
    46. 			while (cur_parent != nullptr && cur_parent->_col == RED)
    47. 			{
    48. 				Node* grandparent = cur_parent->_parent;
    49. 				if (grandparent->_left == cur_parent)//正方向
    50. 				{
    51. 					Node* uncle = grandparent->_right;
    52. 					if (uncle != nullptr && uncle->_col == RED)//情况一,uncle存在且为红
    53. 					{
    54. 						cur_parent->_col = uncle->_col = BLACK;
    55. 						grandparent->_col = RED;
    56. 						//继续向上处理
    57. 						cur = grandparent;
    58. 						cur_parent = cur->_parent;
    59. 					}
    60. 					else//情况二和情况三
    61. 					{
    62. 						//这里情况三经过第一次旋转后可以变成情况二，所以可以先判断是否是情况三
    63. 						if (cur_parent->_right == cur)//这种情况就是情况三
    64. 						{
    65. 							//先进行一个左单旋
    66. 							RotateL(cur_parent);
    67. 							swap(cur, cur_parent);
    68. 						}
    69. 						//代码走到这里就一定是情况二了
    70. 						RotateR(grandparent);
    71. 						cur_parent->_col = BLACK;
    72. 						grandparent->_col = RED;
    73. 						break;
    74. 					}
    75. 				}
    76. 				else if (grandparent->_right == cur_parent)//反方向
    77. 				{
    78. 					Node* uncle = grandparent->_left;
    79. 					if (uncle != nullptr && uncle->_col == RED)//反方向的情况一
    80. 					{
    81. 						cur_parent->_col = uncle->_col = BLACK;
    82. 						grandparent->_col = RED;
    83.  
    84. 						cur = grandparent;
    85. 						cur_parent = cur->_parent;
    86. 					}
    87. 					else//反方向的情况二和情况三
    88. 					{
    89. 						if (cur_parent->_left == cur)
    90. 						{
    91. 							RotateR(cur_parent);
    92. 							swap(cur, cur_parent);
    93. 						}
    94. 						RotateL(grandparent);
    95. 						cur_parent->_col = BLACK;
    96. 						grandparent->_col = RED;
    97. 						break;
    98. 					}
    99. 				}
    100. 			}
    101. 			_root->_col = BLACK;
    102. 		}

    ⑥代码分析

    在我们的插入函数的调整部分中，有下面这段逻辑

    1. 			//调整结点代码
    2. 			while (cur_parent != nullptr && cur_parent->_col == RED)
    3. 			{
    4. 				Node* grandparent = cur_parent->_parent;
    5. 				if (grandparent->_left == cur_parent)//正方向
    6.                 {
    7.                     
    8.                   
    9.                 }

    有的人可能会有个疑问，就是在这里的grandparent指针中，没有进行做判空处理，不会出现grandparent是个空指针的错误吗？

    答案是不会的，原因如下： 

    首先我们可以确定的是，cur和cur_parent指针不会是空指针，不然这个while循环也不会进入，且进去这个循环后，cur和cur_parent结点的颜色一定为红色。那么既然cur_parent为红色，那么cur_parent就一定不是根结点，因为在红黑树的性质中，根结点一定是黑色的，但是这个时候cur_parent是红色的，说明cur_parent一定有父结点，所以不会出现grandparent为空指针的情况。

    4.红黑树的查找

    红黑树的查找就比较简单了，就是普通的二叉搜索树的查找方式，这里就不在多解释，不了解的可以去看前面的二叉搜索树的博客。 

    1.  
    2. 		//查找结点
    3. 		Node* find(const T& data)
    4. 		{
    5. 			Node* cur = _root;
    6. 			if (data > cur->_data)
    7. 			{
    8. 				cur = cur->_right;
    9. 			}
    10. 			else if (data < cur->_data)
    11. 			{
    12. 				cur = cur->_left;
    13. 			}
    14. 			else
    15. 			{
    16. 				return cur;
    17. 			}
    18. 			return nullptr;
    19. 		}

    5.红黑树的修改 

    不是所有红黑树的结点都是可以修改的，只有模型的红黑树才能修改，例如STL中的map，而key模型的红黑树是不能修改的，例如STL中的set，我们这里默认实现的是key模型的红黑树，所以在这里是不能修改的，但是如果想要做到修改，可以把这棵红黑树改成模型即可，即在TreeNode结构体中，多加一个参数即可。 

    三.测试

    看到这里，我们的这棵红黑树除了删除都已经搞定了，那么我们如果判断我们写的代码是对的呢？即我们写的这棵红黑树到底是不是红黑树，判断这棵树是不是红黑树的方法就是用红黑树的性质去检查它即可。 

    首先，我们再来看一下红黑树的五条性质： 

    1.每个结点不是红的就是黑的

    2.根节点是黑色的

    3.如果一个结点是红色的，那么它的两个孩子一定是黑色的

    4.对于每个结点，从该结点到其所有后代叶结点的路径上，均包含相同数量的黑色结点

    5.每个叶子结点都是黑色的（此处的我叶子结点指的是空结点） 

    通过下面这个代码，可以测试一个红黑树是否正确。 

    1. 		//判断是否符合红黑树的性质
    2. 		bool JudgeTree()
    3. 		{
    4. 			//空树也是红黑树
    5. 			if (_root == nullptr)
    6. 			{
    7. 				return true;
    8. 			}
    9. 			//性质1：树结点不是红的就是黑的
    10. 			//这条性质就没必要检查的了
    11.  
    12. 			//性质2：根结点一定是黑色的
    13. 			if (_root->_col != BLACK)
    14. 			{
    15. 				cout << "违反性质2：根结点一定是黑色的" << endl;
    16. 				return false;
    17. 			}
    18.  
    19. 			//性质5:所有叶子结点都是黑色的
    20. 			//这个性质也没必要检查
    21.  
    22. 			size_t blackcount = 0;
    23. 			Node* cur = _root;
    24. 			while (cur != nullptr)//先求出一条路径中的黑色结点的个数
    25. 			{
    26. 				if (cur->_col == BLACK)
    27. 				{
    28. 					blackcount++;
    29. 				}
    30. 				cur = cur->_left;
    31. 			}
    32. 			size_t k = 0;//用来存储黑色结点的个数
    33. 			return _JudgeTree(_root, k, blackcount);//判断性质3和性质4
    34.  
    35. 			//性质3：如果一个结点是红色的，那么它的孩子一定是黑色的
    36. 			//性质4：每条路径上的黑色结点的个数都相同
    37. 		}
    38.  
    39. 		//判断是否红黑树的子函数
    40. 		bool _JudgeTree(Node* root, size_t k, size_t blackcount)
    41. 		{
    42. 			//当root走到NULL的时候，判断这条路径的黑色结点个数是否==blackcount
    43. 			if (root == nullptr)
    44. 			{
    45. 				if (k == blackcount)
    46. 				{
    47. 					return true;
    48. 				}
    49. 				else
    50. 				{
    51. 					cout << "违反性质4：每条路径上的黑结点个数相同" << endl;
    52. 					return false;
    53. 				}			
    54. 			}
    55.  
    56. 			//如果结点是红色的，判断它的父结点是否也为红色
    57. 			Node* root_parent = root->_parent;
    58. 			if (root_parent != nullptr && root->_col == RED)
    59. 			{
    60. 				if (root_parent->_col == RED)
    61. 				{
    62. 					cout << "违反性质3：如果一个结点是红色的，那么它的孩子一定是黑色的" << endl;
    63. 					return false;
    64. 				}
    65. 			}
    66.  
    67. 			//如果结点是黑色的，则k++
    68. 			if (root->_col == BLACK)
    69. 			{
    70. 				k++;
    71. 			}
    72.  
    73. 			return _JudgeTree(root->_left, k, blackcount) && _JudgeTree(root->_right, k, blackcount);
    74. 		}

    四.所有源代码

    blog_RBTree.h

    1. #pragma once
    2. #include
    3. #include
    4. using namespace std;
    5. namespace blog_RBTree
    6. {
    7. 	enum Color
    8. 	{
    9. 		BLACK,
    10. 		RED
    11. 	};
    12.  
    13. 	template<class T>
    14. 	struct TreeNode
    15. 	{
    16. 		//成员变量
    17. 		T _data;//数据
    18. 		TreeNode* _left;
    19. 		TreeNode* _right;
    20. 		TreeNode* _parent;
    21. 		Color _col;//保存结点的颜色
    22.  
    23. 		//构造函数
    24. 		TreeNode(const T& data)
    25. 			:_data(data)
    26. 			,_left(nullptr)
    27. 			,_right(nullptr)
    28. 			,_parent(nullptr)
    29. 			,_col(RED)//每生成一个新结点，都将结点的颜色默认给红色，至于为什么，后面会解释
    30. 		{}
    31. 	};
    32.  
    33. 	template<class T>
    34. 	class RBTree
    35. 	{
    36. 		typedef TreeNode Node;
    37. 	public:
    38. 		//构造函数
    39. 		RBTree()
    40. 			:_root(nullptr)//给根结点一个nullptr
    41. 		{}
    42.  
    43. 		//插入结点
    44. 		bool insert(const T& data)
    45. 		{
    46. 			//如果树为NULL，则直接将新结点给到_root
    47. 			if (_root == nullptr)
    48. 			{
    49. 				_root = new Node(data);
    50. 				_root->_col = BLACK;//把新结点给_root后，要记得把颜色给位BLACK
    51. 				return true;
    52. 			}
    53.  
    54. 			Node* cur = _root;
    55. 			Node* cur_parent = nullptr;
    56. 			while (cur != nullptr)
    57. 			{
    58. 				if (data > cur->_data)
    59. 				{
    60. 					cur_parent = cur;
    61. 					cur = cur->_right;
    62. 				}
    63. 				else if (data < cur->_data)
    64. 				{
    65. 					cur_parent = cur;
    66. 					cur = cur->_left;
    67. 				}
    68. 				else//说明该值已经存在，不进行插入
    69. 				{
    70. 					return false;	
    71. 				}
    72. 			}
    73.  
    74. 			//将新结点插入
    75. 			cur = new Node(data);
    76. 			if (cur_parent->_data > data)
    77. 			{
    78. 				cur_parent->_left = cur;
    79. 				cur->_parent = cur_parent;
    80. 			}
    81. 			else
    82. 			{
    83. 				cur_parent->_right = cur;
    84. 				cur->_parent = cur_parent;
    85. 			}
    86.  
    87. 			//调整结点代码
    88. 			while (cur_parent != nullptr && cur_parent->_col == RED)
    89. 			{
    90. 				Node* grandparent = cur_parent->_parent;
    91. 				if (grandparent->_left == cur_parent)//正方向
    92. 				{
    93. 					Node* uncle = grandparent->_right;
    94. 					if (uncle != nullptr && uncle->_col == RED)//情况一,uncle存在且为红
    95. 					{
    96. 						cur_parent->_col = uncle->_col = BLACK;
    97. 						grandparent->_col = RED;
    98. 						//继续向上处理
    99. 						cur = grandparent;
    100. 						cur_parent = cur->_parent;
    101. 					}
    102. 					else//情况二和情况三
    103. 					{
    104. 						//这里情况三经过第一次旋转后可以变成情况二，所以可以先判断是否是情况三
    105. 						if (cur_parent->_right == cur)//这种情况就是情况三
    106. 						{
    107. 							//先进行一个左单旋
    108. 							RotateL(cur_parent);
    109. 							swap(cur, cur_parent);
    110. 						}
    111. 						//代码走到这里就一定是情况二了
    112. 						RotateR(grandparent);
    113. 						cur_parent->_col = BLACK;
    114. 						grandparent->_col = RED;
    115. 						break;
    116. 					}
    117. 				}
    118. 				else if (grandparent->_right == cur_parent)//反方向
    119. 				{
    120. 					Node* uncle = grandparent->_left;
    121. 					if (uncle != nullptr && uncle->_col == RED)//反方向的情况一
    122. 					{
    123. 						cur_parent->_col = uncle->_col = BLACK;
    124. 						grandparent->_col = RED;
    125.  
    126. 						cur = grandparent;
    127. 						cur_parent = cur->_parent;
    128. 					}
    129. 					else//反方向的情况二和情况三
    130. 					{
    131. 						if (cur_parent->_left == cur)
    132. 						{
    133. 							RotateR(cur_parent);
    134. 							swap(cur, cur_parent);
    135. 						}
    136. 						RotateL(grandparent);
    137. 						cur_parent->_col = BLACK;
    138. 						grandparent->_col = RED;
    139. 						break;
    140. 					}
    141. 				}
    142. 			}
    143. 			_root->_col = BLACK;
    144. 		}
    145.  
    146. 		//查找结点
    147. 		Node* find(const T& data)
    148. 		{
    149. 			Node* cur = _root;
    150. 			if (data > cur->_data)
    151. 			{
    152. 				cur = cur->_right;
    153. 			}
    154. 			else if (data < cur->_data)
    155. 			{
    156. 				cur = cur->_left;
    157. 			}
    158. 			else
    159. 			{
    160. 				return cur;
    161. 			}
    162. 			return nullptr;
    163. 		}
    164.  
    165. 		//判断是否符合红黑树的性质
    166. 		bool JudgeTree()
    167. 		{
    168. 			//空树也是红黑树
    169. 			if (_root == nullptr)
    170. 			{
    171. 				return true;
    172. 			}
    173. 			//性质1：树结点不是红的就是黑的
    174. 			//这条性质就没必要检查的了
    175.  
    176. 			//性质2：根结点一定是黑色的
    177. 			if (_root->_col != BLACK)
    178. 			{
    179. 				cout << "违反性质2：根结点一定是黑色的" << endl;
    180. 				return false;
    181. 			}
    182.  
    183. 			//性质5:所有叶子结点都是黑色的
    184. 			//这个性质也没必要检查
    185.  
    186. 			size_t blackcount = 0;
    187. 			Node* cur = _root;
    188. 			while (cur != nullptr)//先求出一条路径中的黑色结点的个数
    189. 			{
    190. 				if (cur->_col == BLACK)
    191. 				{
    192. 					blackcount++;
    193. 				}
    194. 				cur = cur->_left;
    195. 			}
    196. 			size_t k = 0;//用来存储黑色结点的个数
    197. 			return _JudgeTree(_root, k, blackcount);//判断性质3和性质4
    198.  
    199. 			//性质3：如果一个结点是红色的，那么它的孩子一定是黑色的
    200. 			//性质4：每条路径上的黑色结点的个数都相同
    201. 		}
    202.  
    203. 	private:
    204. 		//左单旋	
    205. 		void RotateL(Node* cur_parent)
    206. 		{
    207. 			Node* cur = cur_parent->_right;
    208. 			Node* cur_left = cur->_left;
    209.  
    210. 			//改变指针的链接关系
    211. 			cur_parent->_right = cur_left;
    212. 			if (cur_left != nullptr)
    213. 			{
    214. 				cur_left->_parent = cur_parent;
    215. 			}
    216.  
    217. 			cur->_left = cur_parent;
    218. 			Node* cur_parent_parent = cur_parent->_parent;
    219. 			cur_parent->_parent = cur;
    220.  
    221. 			//旋转完成后要判断cur_parent是否为根
    222. 			if (cur_parent_parent != nullptr)//说明cur_parent不是根
    223. 			{
    224. 				if (cur_parent_parent->_data < cur_parent->_data)
    225. 				{
    226. 					cur_parent_parent->_right = cur;
    227. 					cur->_parent = cur_parent_parent;
    228. 				}
    229. 				else
    230. 				{
    231. 					cur_parent_parent->_left = cur;
    232. 					cur->_parent = cur_parent_parent;
    233. 				}
    234. 			}
    235. 			else//说明cur_parent是根
    236. 			{
    237. 				_root = cur;
    238. 				cur->_parent = nullptr;
    239. 			}
    240.  
    241. 		}
    242.  
    243. 		//右单旋
    244. 		void RotateR(Node* cur_parent)
    245. 		{
    246. 			Node* cur = cur_parent->_left;
    247. 			Node* cur_right = cur->_right;
    248.  
    249. 			cur_parent->_left = cur_right;
    250. 			if (cur_right != nullptr)
    251. 			{
    252. 				cur_right->_parent = cur_parent;
    253. 			}
    254.  
    255. 			cur->_right = cur_parent;
    256. 			Node* cur_parent_parent = cur_parent->_parent;
    257. 			cur_parent->_parent = cur;
    258.  
    259. 			if (cur_parent_parent != nullptr)
    260. 			{
    261. 				if (cur_parent_parent->_data > cur_parent->_data)
    262. 				{
    263. 					cur_parent_parent->_left = cur;
    264. 					cur->_parent = cur_parent_parent;
    265. 				}
    266. 				else
    267. 				{
    268. 					cur_parent_parent->_right = cur;
    269. 					cur->_parent = cur_parent_parent;
    270. 				}
    271. 			}
    272. 			else
    273. 			{
    274. 				_root = cur;
    275. 				cur->_parent = nullptr;
    276. 			}
    277.  
    278. 		}
    279.  
    280. 		//获取根节点
    281. 		Node* GetRoot()
    282. 		{
    283. 			return _root;
    284. 		}
    285.  
    286. 		//判断是否红黑树的子函数
    287. 		bool _JudgeTree(Node* root, size_t k, size_t blackcount)
    288. 		{
    289. 			//当root走到NULL的时候，判断这条路径的黑色结点个数是否==blackcount
    290. 			if (root == nullptr)
    291. 			{
    292. 				if (k == blackcount)
    293. 				{
    294. 					return true;
    295. 				}
    296. 				else
    297. 				{
    298. 					cout << "违反性质4：每条路径上的黑结点个数相同" << endl;
    299. 					return false;
    300. 				}
    301. 					
    302.  
    303. 			}
    304.  
    305. 			//如果结点是红色的，判断它的父结点是否也为红色
    306. 			Node* root_parent = root->_parent;
    307. 			if (root_parent != nullptr && root->_col == RED)
    308. 			{
    309. 				if (root_parent->_col == RED)
    310. 				{
    311. 					cout << "违反性质3：如果一个结点是红色的，那么它的孩子一定是黑色的" << endl;
    312. 					return false;
    313. 				}
    314. 			}
    315.  
    316. 			//如果结点是黑色的，则k++
    317. 			if (root->_col == BLACK)
    318. 			{
    319. 				k++;
    320. 			}
    321.  
    322. 			return _JudgeTree(root->_left, k, blackcount) && _JudgeTree(root->_right, k, blackcount);
    323. 		}
    324.  
    325. 	private:
    326. 		Node* _root;
    327. 	};
    328.  
    329. 	void Test1()
    330. 	{
    331. 		srand(time(0));
    332. 		RBTree<int> root;
    333. 		const int n = 10000;
    334. 		for (int i = 0; i < n; i++)
    335. 		{
    336. 			int input = rand();
    337. 			root.insert(input);
    338. 		}
    339. 		cout << root.JudgeTree() << endl;
    340. 	}
    341. }

    test.cpp  

    1. #include"blog_RBTree.h"
    2.  
    3. int main()
    4. {
    5. 	blog_RBTree::Test1();
    6.  
    7. 	return 0;
    8. }
  • 相关阅读:
    阿里云添加端口
    痞子衡嵌入式：MCUBootUtility v5.3发布，利用XMCD轻松使能外部RAM
    RPC 基础系列
    海外代理IP是什么？如何使用？
    中移链共识机制介绍
    ZLMediaKit拉取海康威视摄像头RTSP视频流时拉流失败
    微信小程序｜基于小程序+C#实现聊天功能
    OAuth 2.1 框架
    moonligh串流教程以及3大问题解决
    Android ImageView 四个角自定义角度，以及角度的变换
  • 原文地址：https://blog.csdn.net/EWIAW_ilove/article/details/139623039