• c++——红黑树

    目录

    一. 红黑树的概念

    二. 红黑树的性质

    三. 红黑树节点的定义

    四. 红黑树的插入（重要）

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

    情况二：cur为红，p为红，g为黑，u不存在/u存在且为黑

    情况1——u不存在

    情况2——u存在且为黑

    情况三：cur为红，p为红，g为黑，u不存在/u存在且为黑

    五. 红黑树的验证

    六. 红黑树与AVL树的比较

    不解析删除，解析插入，红黑树的删除参考：《算法导论》或者《STL源码剖析》

    红黑树的删除

    一. 红黑树的概念

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

    如下所示就是一颗红黑树：

    二. 红黑树的性质

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

    为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点 个数的两倍？

    根据红黑树的性质，当一颗子树中的节点全部为黑色节点时，路径最短；在另一颗包含红色节点的子树中，由于节点为一黑一红间隔，节点数量最多是全黑子树的两倍，路径最长

    三. 红黑树节点的定义

    1. //颜色
    2. enum color
    3. {
    4. 	RED,
    5. 	BLACK
    6. };
    7.  
    8. //红黑树节点的定义
    9. template<class K, class V>
    10. struct RBTreeNode
    11. {
    12. 	RBTreeNode* _left;
    13. 	RBTreeNode* _right;
    14. 	RBTreeNode* _parent;
    15. 	pair _kv;
    16. 	color _col;
    17.  
    18. 	//构造函数
    19. 	RBTreeNode(const pair& kv)
    20. 		:_left(nullptr)
    21. 		,_right(nullptr)
    22. 		,_parent(nullptr)
    23. 		,_kv(kv)
    24. 		,_col(RED)
    25. 	{}
    26. };

    在节点的定义中，为什么要将节点的默认颜色给成红色的？

    新插入节点的颜色只会影响性质3或者性质4（新插入的节点不是根节点的时候），

    如果新插入的节点是黑色的节点，那么一定会破坏性质4，破坏性质4要想让红黑树平衡最坏的情况需要将整颗树的节点都动一遍，很难维护。

    如果新插入的节点是红色的节点，可能会破坏性质3（红色节点的孩子一定是黑色，黑色节点的孩子不一定是红色），即使破坏了性质3，最坏的情况也就不过只要更改三个节点的颜色

    四. 红黑树的插入（重要）

    红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

    1. 按照二叉搜索的树规则插入新节点
    2. 检测新节点插入后，红黑树的性质是否造到破坏

    （注意：由于红黑树的插入也会涉及旋转等问题，所以随着高度的增加红黑树树子树的情况就会变得非常复杂，所以采用和AVL树一样的处理方法，使用具象图来表示）

    因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连 在一起的红色节点，此时需要对红黑树分情况来讨论：

    （cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点）

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

    cur和p均为红，违反了性质三，此处能否将p直接改为黑？

    切记不可，否则就会违反性质4，处理起来会很棘手。

     处理方式：将p，u改为黑，g改为红，然后把g当成cur，继续向上调整

    如果p是红色，由于新插入的节点默认是红色的，就会出现连续的红色节点，违反性质三，处理完后保证了性质四不会变。

    如果g是根节点，调整完成后，需要将g改为黑色（根节点一定为黑色）

    如果g是子树，一定有双亲，且g的双亲如果是红色，需要继续向上调整，如下图：

    经调整后是可能会出现上图情况，即本来g的p是红色的，所以需要继续往上调整，以上是当cur是新插入节点的情况，同理，我们调整的这部分也可能是下面调整上来导致，即a，b，c，d，e都不为0的情况，当在a或b新插入节点导致的连续红色节点，一路向上调整这，需要纵观全局，图上可能是一棵树的全部，或者是一棵树的顶部，也可能是一颗树的中部，甚至是一颗树的底部

    无论是哪一部分，无论是在哪颗子树，只要按处理方式处理，往上更新即可

    情况二：cur为红，p为红，g为黑，u不存在/u存在且为黑

    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变红

    有如上图的红黑树：

    情况1——u不存在

    当u不存在&&p是g的左&&cur是p的左，abcde子树都不应该存在（de肯定不存在，c若存在那么cur插入前就应该旋转过来了，cur不可能插在p的这个位置，cur若不是新插入节点p应该是黑色，那么违反红黑树性质4。），如下图：

    单纯的左子树的左高，以g为旋转点进行右单旋，旋转完成后，p变黑色g变红色：

    即平衡，就不用再做处理，不再往上更新

    当u不存在&&p是g的右&&cur是p的右，与上面同理，如下图：

     单纯的右子树的右高，以g为旋转点进行左单旋，旋转完成后，p变黑色g变红色：

     即平衡，就不用再做处理，不再往上更新

    情况2——u存在且为黑

    为什么cur节点原来的颜色一定是黑色的，现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色？

    分析如下：

    cur为红色有两种情况：

    一种情况是cur本来是红色，即cur为新插入的红色节点，但是新插入红色cur节点的情况不可能存在，因为如果是新插入红色cur节点无论如何都会违反红黑树的性质。

    一种情况由子树往上更新来导致cur变成红色，即由情况一向上更新演变到cur为红，u为黑

    由此分析发现只能是第二种情况

    以下更新情况都是由情况一向上更新演变到cur为红u为黑高度最少的情况即相差一层高度：

    （如果再少一层，即少cur下面一层（cur是新插入的红色节点），则该树一定违反红黑树性质）

    u存在&&u为黑&&p是g的左&&cur是p的左：

    上图经过情况一演变到下图：

    单纯的左子树的左高，以g为旋转点进行右单旋，旋转完成后，p变成黑色，g变成红色，如下图：

    经过旋转+变色以后该红黑树就平衡了，不用往上更新

    u存在&&u为黑&&p是g的右&&cur是p的右：

     上图经过情况一演变到下图：

    单纯的右子树的右高，以g为旋转点进行左单旋，旋转完成后，p变成黑色，g变成红色，如下图：

     经过旋转+变色以后该红黑树就平衡了，不用往上更新

    u存在&&u为黑&&p是g的左&&cur是p的左的模板：

    abdemnxy等子树是包含相同数量黑色节点的红黑子树，从xymn几个位置中某个位置子树插入红色节点，引发cur从黑变成红，进而引发左子树左高导致的右单旋

    u存在&&u为黑&&p是g的右&&cur是p的右的模板：

    abdemnxy等子树是包含相同数量黑色节点的红黑子树，从xymn几个位置中某个位置子树插入红色节点，引发cur从黑变成红，进而引发右子树右高导致的左单旋

    旋转+变色以后，这颗子树不违反红黑树规则，和插入前比较，黑色节点数量不变，不会影响上层，处理结束。

    情况三：cur为红，p为红，g为黑，u不存在/u存在且为黑

    情况三和情况二其实是一样的，只不过引发的双旋，除了处理旋转，其他都按情况二方式处理

    处理方式：

    • p为g的左孩子，cur为p的右孩子，针对p做左单旋转，再针对g做右单旋；
    • p为g的右孩子，cur为p的左孩子，针对p做右单旋转，再针对g做左单旋；
    • cur、g变色—>cur变黑，g变红

    以下直接给出模板：

    u存在&&u为黑&&p是g的左&&cur是p的右的模板：

    abdemnxy等子树是包含相同数量黑色节点的红黑子树，从ab两个位置中某个位置子树插入红色节点，引发cur从黑变成红，进而引发左子树右高导致的左右单双旋

    u存在&&u为黑&&p是g的右&&cur是p的左的模板：

    abdemnxy等子树是包含相同数量黑色节点的红黑子树，从ab两个位置中某个位置子树插入红色节点，引发cur从黑变成红，进而引发右子树左高导致的右左单双旋

    和情况二同理，旋转+变色以后，这颗子树不违反红黑树规则，和插入前比较，黑色节点数量不变，不会影响上层，处理结束

    插入代码实现如下：

    1. public:
    2.     bool insert(const pair& kv)
    3. 	{
    4. 		//树为空
    5. 		if (_root == nullptr)
    6. 		{
    7. 			_root = new Node(kv);
    8. 			_root->_col = BLACK;
    9. 			return true;
    10. 		}
    11.  
    12. 		//找到插入的位置
    13. 		Node* parent = nullptr;
    14. 		Node* cur = _root;
    15. 		while (cur)
    16. 		{
    17. 			parent = cur;
    18. 			if (cur->_kv.first < kv.first)
    19. 				cur = cur->_right;
    20. 			else if (cur->_kv.first > kv.first)
    21. 				cur = cur->_left;
    22. 			else
    23. 				return false;
    24. 		}
    25.  
    26. 		//将节点插入
    27. 		cur = new Node(kv);
    28. 		cur->_col = RED;
    29. 		if (parent->_kv.first < cur->_kv.first)
    30. 			parent->_right = cur;
    31. 		else
    32. 			parent->_left = cur;
    33.  
    34. 		cur->_parent = parent;
    35.  
    36. 		//连续的红色
    37. 		while (parent && parent->_col == RED)
    38. 		{
    39. 			Node* grandparent = parent->_parent;
    40. 			assert(grandparent);
    41.  
    42. 			//parent是grandparent的左
    43. 			if (parent == grandparent->_left)
    44. 			{
    45. 				Node* uncle = grandparent->_right;
    46.  
    47. 				//unlce存在且为红
    48. 				if (uncle && uncle->_col == RED)
    49. 				{
    50. 					//更新parent和uncle的颜色为黑色，grandparent为红色
    51. 					parent->_col = uncle->_col = BLACK;
    52. 					grandparent->_col = RED;
    53. 					//向上更新
    54. 					cur = grandparent;
    55. 					parent = cur->_parent;
    56. 				}
    57. 				//uncle不存在或者为黑
    58. 				else
    59. 				{
    60. 					//cur是parent的左，左高，右单旋，以grandparent为旋转点
    61. 					if (cur == parent->_left)
    62. 					{
    63. 						RotateR(grandparent);
    64. 						grandparent->_col = RED;
    65. 						parent->_col = BLACK;
    66. 					}
    67. 					//cur是parent的右，左右双旋的情况
    68. 					else
    69. 					{
    70. 						RotateL(parent);
    71. 						RotateR(grandparent);
    72. 						cur->_col = BLACK;
    73. 						grandparent->_col = RED;
    74. 					}
    75.  
    76. 					break;//旋转调整颜色后一定平衡，只是更改颜色未旋转不一定平衡
    77. 				}
    78. 			}
    79. 			//parent是grandparent的右
    80. 			else
    81. 			{
    82. 				Node* uncle = grandparent->_left;
    83.  
    84. 				//uncle存在且为红
    85. 				if (uncle && uncle->_col == RED)
    86. 				{
    87. 					//更新parent和uncle的颜色为黑色，grandparent为红色
    88. 					parent->_col = uncle->_col = BLACK;
    89. 					grandparent->_col = RED;
    90. 					//向上更新
    91. 					cur = grandparent;
    92. 					parent = cur->_parent;
    93. 				}
    94. 				//uncle不存在或者为黑
    95. 				else
    96. 				{
    97. 					//cur是parent的右，右高，左单旋
    98. 					if (cur == parent->_right)
    99. 					{
    100. 						RotateL(grandparent);
    101. 						parent->_col = BLACK;
    102. 						grandparent->_col = RED;
    103. 					}
    104. 					//cur是parent的左，右左双旋
    105. 					else
    106. 					{
    107. 						RotateR(parent);
    108. 						RotateL(grandparent);
    109. 						cur->_col = BLACK;
    110. 						grandparent->_col = RED;
    111. 					}
    112.  
    113. 					break;//旋转调整颜色后一定平衡，只是更改颜色未旋转不一定平衡
    114. 				}
    115. 			}
    116. 		}
    117.  
    118. 		_root->_col = BLACK;//根节点必须为黑色
    119.  
    120. 		//插入成功
    121. 		return true;
    122. 	}
    123. private:
    124.     //右边高左单旋
    125. 	void RotateL(Node* parent)
    126. 	{
    127. 		Node* subR = parent->_right;
    128. 		Node* subRL = subR->_left;
    129.  
    130. 		//将根的右子树的左子树赋值给根的右子树
    131. 		parent->_right = subRL;
    132. 		//subRL为空不能访问
    133. 		if (subRL)
    134. 			subRL->_parent = parent;
    135.  
    136. 		//将根节点变成根的右子树的左子树
    137. 		subR->_left = parent;
    138.  
    139. 		//更新根的右子树的父节点
    140. 		subR->_parent = parent->_parent;
    141. 		//如果parent是根节点需要更新根节点
    142. 		if (parent == _root)
    143. 		{
    144. 			_root = subR;
    145. 			subR->_parent = nullptr;
    146. 		}
    147. 		//如果parent上面还有祖先节点，需要更新祖先节点的左节点/右节点
    148. 		else
    149. 		{
    150. 			if (parent->_parent->_left == parent)
    151. 				parent->_parent->_left = subR;
    152. 			else
    153. 				parent->_parent->_right = subR;
    154. 		}
    155.  
    156. 		//更新根的父节点
    157. 		parent->_parent = subR;
    158. 	}
    159.  
    160. 	//左边高右单旋
    161. 	void RotateR(Node* parent)
    162. 	{
    163. 		Node* subL = parent->_left;
    164. 		Node* subLR = subL->_right;
    165.  
    166. 		//根节点的左指针指向左子树的右子树
    167. 		parent->_left = subLR;
    168. 		//如果根节点的左子树的右子树不为空则更新_parent
    169. 		if (subLR)
    170. 			subLR->_parent = parent;
    171.  
    172. 		//根节点的左子树的右指针指向parent
    173. 		subL->_right = parent;
    174. 		//更新subL的_parent
    175. 		subL->_parent = parent->_parent;
    176.  
    177. 		//处理parent是根节点和不是根节点的情况
    178. 		//如果parent是根节点，则赋值给_root
    179. 		if (parent == _root)
    180. 		{
    181. 			_root = subL;
    182. 			subL->_parent = nullptr;
    183. 		}
    184. 		//否则链接上祖先节点
    185. 		else
    186. 		{
    187. 			//确定是祖先节点的左还是右，并链接上
    188. 			if (parent->_parent->_left == parent)
    189. 				parent->_parent->_left = subL;
    190. 			else
    191. 				parent->_parent->_right = subL;
    192. 		}
    193.  
    194. 		//更新parent的_parent
    195. 		parent->_parent = subL;
    196. 	}

    五. 红黑树的验证

    红黑树的检测分为两步：

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

    分别从层序遍历（查看每层节点），中序遍历（二叉搜索树是有序的），树的最低高度和最高高度（红黑树的性质），是否平衡（红黑树的性质）四个角度判断，都满足即是红黑树。

    1. public:
    2.     //层序遍历
    3. 	vectorint>> levelOrder() {
    4. 		vectorint>> vv;
    5. 		if (_root == nullptr)
    6. 			return vv;
    7.  
    8. 		queue q;
    9. 		int levelSize = 1;
    10. 		q.push(_root);
    11.  
    12. 		while (!q.empty())
    13. 		{
    14. 			// levelSize控制一层一层出
    15. 			vector<int> levelV;
    16. 			while (levelSize--)
    17. 			{
    18. 				Node* front = q.front();
    19. 				q.pop();
    20. 				levelV.push_back(front->_kv.first);
    21. 				if (front->_left)
    22. 					q.push(front->_left);
    23.  
    24. 				if (front->_right)
    25. 					q.push(front->_right);
    26. 			}
    27. 			vv.push_back(levelV);
    28. 			for (auto e : levelV)
    29. 			{
    30. 				cout << e << " ";
    31. 			}
    32. 			cout << endl;
    33.  
    34. 			// 上一层出完，下一层就都进队列
    35. 			levelSize = q.size();
    36. 		}
    37.  
    38. 		return vv;
    39. 	}
    40.  
    41.     //中序遍历
    42. 	void InOrder()
    43. 	{
    44. 		_InOrder(_root);
    45. 		cout << endl;
    46. 	}
    47.  
    48.     //求高度差
    49. 	void Height()
    50. 	{
    51. 		cout << "最长路径:" << _maxHeight(_root) << endl;
    52. 		cout << "最短路径:" << _minHeight(_root) << endl;
    53. 	}
    54.  
    55.  
    56.     //判断是否平衡
    57. 	bool IsBalanceTree()
    58. 	{
    59. 		// 检查红黑树几条规则
    60.  
    61. 		Node* pRoot = _root;
    62. 		// 空树也是红黑树
    63. 		if (nullptr == pRoot)
    64. 			return true;
    65.  
    66. 		// 检测根节点是否满足情况
    67. 		if (BLACK != pRoot->_col)
    68. 		{
    69. 			cout << "违反红黑树性质二：根节点必须为黑色" << endl;
    70. 			return false;
    71. 		}
    72.  
    73. 		// 获取任意一条路径中黑色节点的个数 -- 比较基准值
    74. 		size_t blackCount = 0;
    75. 		Node* pCur = pRoot;
    76. 		while (pCur)
    77. 		{
    78. 			if (BLACK == pCur->_col)
    79. 				blackCount++;
    80.  
    81. 			pCur = pCur->_left;
    82. 		}
    83.  
    84. 		// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
    85. 		size_t k = 0;
    86. 		return _IsValidRBTree(pRoot, k, blackCount);
    87. 	}
    88. private:
    89.     //求最大高度
    90.     int _maxHeight(Node* root)
    91. 	{
    92. 		if (root == nullptr)
    93. 			return 0;
    94.  
    95. 		int lh = _maxHeight(root->_left);
    96. 		int rh = _maxHeight(root->_right);
    97.  
    98. 		return lh > rh ? lh + 1 : rh + 1;
    99. 	}
    100.  
    101.     //求最小高度
    102. 	int _minHeight(Node* root)
    103. 	{
    104. 		if (root == nullptr)
    105. 			return 0;
    106.  
    107. 		int lh = _minHeight(root->_left);
    108. 		int rh = _minHeight(root->_right);
    109.  
    110. 		return lh < rh ? lh + 1 : rh + 1;
    111. 	}
    112.  
    113.  
    114.     //中序遍历
    115. 	void _InOrder(Node* root)
    116. 	{
    117. 		if (root == nullptr)
    118. 			return;
    119.  
    120. 		_InOrder(root->_left);
    121. 		cout << root->_kv.first << " ";
    122. 		_InOrder(root->_right);
    123. 	}
    124.  
    125.     //是否是合法的红黑树
    126. 	bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
    127. 	{
    128. 		//走到null之后，判断k和black是否相等
    129. 		if (nullptr == pRoot)
    130. 		{
    131. 			if (k != blackCount)
    132. 			{
    133. 				cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
    134. 				return false;
    135. 			}
    136. 			return true;
    137. 		}
    138.  
    139. 		// 统计黑色节点的个数
    140. 		if (BLACK == pRoot->_col)
    141. 			k++;
    142.  
    143. 		// 检测当前节点与其双亲是否都为红色
    144. 		if (RED == pRoot->_col && pRoot->_parent && pRoot->_parent->_col == RED)
    145. 		{
    146. 			cout << "违反性质三：存在连在一起的红色节点" << endl;
    147. 			return false;
    148. 		}
    149.  
    150. 		return _IsValidRBTree(pRoot->_left, k, blackCount) &&
    151. 			_IsValidRBTree(pRoot->_right, k, blackCount);
    152. 	}

    根据红黑树的性质验证是否为红黑树：

    性质2：根节点可以直接进行判断

    性质3：遇到红色节点就去检查父节点的颜色

    性质4：先统计一条路径上黑色节点数量，再进行前序遍历，和每条路径上的黑色节点数量进行比较判断

    六. 红黑树与AVL树的比较

    红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(logN)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数， 所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

  • 相关阅读:
    Proteus中如何使用Arduino实现 ST7735显示屏十六宫格拼图游戏
    一篇文章熟练掌握Git
    vue2实例
    阿里云OSS简单应用
    AI大预言模型——ChatGPT在地学、GIS、气象、农业、生态、环境等应用
    如何优化前端性能？
    jvm的结构以及如何调优
    gpt4与gpt4o对比
    关于 provide、inject 在Vue3中的用法
    Web3时代：探索DAO的未来之路
  • 原文地址：https://blog.csdn.net/Britney_dark/article/details/127767542