• 深入理解 红黑树【满足红黑树5条规则】

    目录

    一.红黑树

    1.概念

    2.性质

    二.分部实现红黑树

    1.树节点

    2.红黑树成员

    3.插入（重点）

    情况一：叔叔节点存在且为红。

     情况二：叔叔不存在 or 叔叔存在且为黑

    ① 单旋情况

    ② 双旋情况

    注意：

    4.判断该树是否为红黑树

    三.红黑树实现代码

    AVLTree-》深入理解AVLTree【旋转控制平衡（单旋、双旋）】_糖果雨滴a的博客-CSDN博客

     使用红黑树封装实现的map和set：C++ 关联式容器map+set_糖果雨滴a的博客-CSDN博客

     

    前言：在学习红黑树之前，我们最好先学习一下AVLTree，并且这两个平衡二叉搜索树的难度差不多，学过了AVLTree之后，红黑树就会更加轻松一些。红黑树只是比较抽象一些，在调整方面较AVLTree要简单一些。

    一.红黑树

    1.概念

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

    2.性质

    ① 每个结点不是红色就是黑色

    ② 根节点是黑色的

    ③ 如果一个结点是红色的，则它的两个孩子结点是黑色的

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

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

    二.分部实现红黑树

    1.树节点

            实现一个含义3叉链的二叉树，并且包括pair类型的kv，以及枚举RED, BLACK颜色控制。

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

    2.红黑树成员

    1. template<class K, class V>
    2. class RBTree
    3. {
    4. 	typedef RBTreeNode Node;
    5. private:
    6. 	Node* _root = nullptr;
    7. }

    3.插入（重点）

            先简单看一下插入的代码： 

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

            前面就是正常的找到插入的位置，然后插入节点。

            这里我们默认插入的节点的颜色是红色，如果默认是黑色就一定违反规则四，而是红色就只是可能会违反规则三，相比较而言，插入节点颜色为红色的影响较小。

            接下来就是红黑树的重点部分：①符合红黑树规则 ②保证该搜索二叉树相对平衡。

            因为我们插入的节点是红色，那么只有出现连续的红色节点（即插入节点为红色，其父节点也为红色时）才需要进行调整。而具体情况主要与叔叔节点有关。

            这里我们先定义一个祖父节点grandfather，因为出现这种情况时父节点为红色，而如果没有grandfather，就一定违反规则二（根节点为黑色），因此grandfather一定存在，为了防止出现问题，这里我们assert一下。

            接下来就需要分情况了，首先是parent在祖父节点的左还是右需要分情况，因为左和右的不同，我们在后面进行旋转控制平衡时的旋转方向是不同的，因此要区分开来。

            这里我们以parent在grandfather的左为例，首先定义一个叔叔节点（grandfather的另一个孩子节点），这个叔叔节点是红黑树的关键。我们要以叔叔进行分情况。

    情况一：叔叔节点存在且为红。

            这种情况我们只需要变色处理，但是在变色处理后，可能导致上面的节点也出现此情况，因此要继续向上处理。

            处理方式：变色处理。

            操作：将parent和uncle的颜色改为BLACK，让grandfather的颜色改为RED。（这里我们不讨论grandfather是根节点的情况，我们在最后强制让root节点变为黑色）

            我们处理的原则是尽量保证原来的黑色节点的数量不变进行插入，因此按上述改颜色后黑色节点的数量是不会发生变化的。

            下面我们看图实现：

    g为grandfather，p为parent，u为uncle。

            代码实现：

    1. // 情况一：叔叔存在且为红
    2. if (uncle && uncle->_col == RED)
    3. {
    4. 	// 变色
    5. 	parent->_col = uncle->_col = BLACK;
    6. 	grandfather->_col = RED;
    7.  
    8. 	// 继续往上处理
    9. 	cur = grandfather;
    10. 	parent = cur->_parent;
    11. }

     情况二：叔叔不存在 or 叔叔存在且为黑

            情况二要再次进行划分，可以再分为两种情况，一种是进行单旋，另一种是进行双旋。

    ① 单旋情况

            grandfather，parent，cur在一条线上时发生单旋，这里我们是以parent在grandfather的左为例，因此这里cur是parent的左节点。

            处理方式：右单旋+变色处理

            操作：首先是右单旋，这里在AVLTree中进行了详细解释，然后再把parent的颜色变为BLACK，grandfather的颜色变为RED。

            

            代码实现：

    1. // 情况二：单旋(右单旋)
    2. if (cur == parent->_left)
    3. {
    4. 	//     g
    5. 	//   p
    6. 	// c
    7. 	RotateR(grandfather);
    8. 	parent->_col = BLACK;
    9. 	grandfather->_col = RED;
    10. }

    ② 双旋情况

            grandfather，parent，cur不在一条线上是发生双旋，这种情况说明cur是parent的右节点。

            处理方式：左右双旋+变色处理

            操作：先左单旋后右双旋，然后把cur的颜色变为BLACK，grangfather的颜色变为RED

            代码实现：

    1. // 情况三：双旋(左右双旋)
    2. else
    3. {
    4. 	//     g
    5. 	//   p
    6. 	//     c
    7. 	RotateL(parent);
    8. 	RotateR(grandfather);
    9. 	cur->_col = BLACK;
    10. 	grandfather->_col = RED;
    11. }

    注意：

            上面我们是以parent在grandfather的左为例，如果parent在grandfather的右，那么情况一是相同的，而情况二中的单旋和双旋分别从右单旋变为左单旋，从左右双旋变为右左双旋。而变色处理是相同的。

    4.判断该树是否为红黑树

            要想判断该树是否为红黑树，就要依次去判断该树是否满足这5个规则，同时也要满足没有一条路径会比其它路径长两倍以上。 

    1. bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
    2. {
    3. 	// 走到null之后，判断k和black是否相等
    4. 	if (nullptr == pRoot)
    5. 	{
    6. 		if (k != blackCount)
    7. 		{
    8. 			cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
    9. 			return false;
    10. 		}
    11. 			
    12. 		return true;
    13. 	}
    14.  
    15. 	// 统计黑色节点的个数
    16. 	if (BLACK == pRoot->_col)
    17. 	{
    18. 		k++; 
    19. 	}
    20.  
    21. 	// 检测当前节点与其双亲是否都为红色
    22. 	if (RED == pRoot->_col && pRoot->_parent && pRoot->_parent->_col == RED)
    23. 	{
    24. 		cout << "违反性质三：存在连在一起的红色节点" << endl;
    25. 		return false;
    26. 	}
    27.  
    28. 	return _IsValidRBTree(pRoot->_left, k, blackCount) &&
    29. 		_IsValidRBTree(pRoot->_right, k, blackCount);
    30. }
    31.  
    32. bool IsBalanceTree()
    33. {
    34. 	// 检查红黑树几条规则
    35. 	Node* pRoot = _root;
    36. 	// 空树也是红黑树
    37. 	if (nullptr == pRoot)
    38. 		return true;
    39.  
    40. 	// 检测根节点是否满足情况
    41. 	if (BLACK != pRoot->_col)
    42. 	{
    43. 		cout << "违反红黑树性质二：根节点必须为黑色" << endl;
    44. 		return false;
    45. 	}
    46.  
    47. 	// 获取任意一条路径中黑色节点的个数 -- 比较基准值
    48. 	size_t blackCount = 0;
    49. 	Node* pCur = pRoot;
    50. 	while (pCur)
    51. 	{
    52. 		if (BLACK == pCur->_col)
    53. 			blackCount++;
    54.  
    55. 		pCur = pCur->_left;
    56. 	}
    57.  
    58. 	// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
    59. 	size_t k = 0;
    60. 	return _IsValidRBTree(pRoot, k, blackCount);
    61. }

    三.红黑树实现代码

    1. #pragma once
    2.  
    3. #include 
    4.  
    5. enum Color
    6. {
    7. 	RED,
    8. 	BLACK,
    9. };
    10.  
    11. template<class K, class V>
    12. struct RBTreeNode
    13. {
    14. 	RBTreeNode* _left;
    15. 	RBTreeNode* _right;
    16. 	RBTreeNode* _parent;
    17. 	pair _kv;
    18.  
    19. 	Color _col;
    20.  
    21. 	RBTreeNode(const pair& kv)
    22. 		: _kv(kv)
    23. 		, _left(nullptr)
    24. 		, _right(nullptr)
    25. 		, _parent(nullptr)
    26. 		, _col(RED)
    27. 	{}
    28. };
    29.  
    30. template<class K, class V>
    31. class RBTree
    32. {
    33. 	typedef RBTreeNode Node;
    34. public:
    35. 	bool Insert(const pair& kv)
    36. 	{
    37. 		// 1.搜索树的规则插入
    38. 		// 2.看是否违反平衡规则，如果违反就需要处理：旋转
    39. 		if (_root == nullptr)
    40. 		{
    41. 			_root = new Node(kv);
    42. 			_root->_col = BLACK;
    43. 			return true;
    44. 		}
    45.  
    46. 		Node* parent = nullptr;
    47. 		Node* cur = _root;
    48. 		while (cur)
    49. 		{
    50. 			if (cur->_kv.first < kv.first)
    51. 			{
    52. 				parent = cur;
    53. 				cur = cur->_right;
    54. 			}
    55. 			else if (cur->_kv.first > kv.first)
    56. 			{
    57. 				parent = cur;
    58. 				cur = cur->_left;
    59. 			}
    60. 			else
    61. 			{
    62. 				return false;
    63. 			}
    64. 		}
    65.  
    66. 		cur = new Node(kv);
    67. 		cur->_col = RED;
    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 = parent;
    78.  
    79. 		// 存在连续红色节点
    80. 		while (parent && parent->_col == RED)
    81. 		{
    82. 			Node* grandfather = parent->_parent;
    83. 			assert(grandfather);
    84.  
    85. 			if (grandfather->_left == parent)
    86. 			{
    87. 				Node* uncle = grandfather->_right;
    88. 				// 情况一：叔叔存在且为红
    89. 				if (uncle && uncle->_col == RED)
    90. 				{
    91. 					// 变色
    92. 					parent->_col = uncle->_col = BLACK;
    93. 					grandfather->_col = RED;
    94.  
    95. 					// 继续往上处理
    96. 					cur = grandfather;
    97. 					parent = cur->_parent;
    98. 				}
    99. 				// 叔叔不存在 or 叔叔存在且为黑
    100. 				else
    101. 				{
    102. 					// 情况二：单旋(右单旋)
    103. 					if (cur == parent->_left)
    104. 					{
    105. 						//     g
    106. 						//   p
    107. 						// c
    108. 						RotateR(grandfather);
    109. 						parent->_col = BLACK;
    110. 						grandfather->_col = RED;
    111. 					}
    112. 					// 情况三：双旋(左右双旋)
    113. 					else
    114. 					{
    115. 						//     g
    116. 						//   p
    117. 						//     c
    118. 						RotateL(parent);
    119. 						RotateR(grandfather);
    120. 						cur->_col = BLACK;
    121. 						grandfather->_col = RED;
    122. 					}
    123.  
    124. 					break;
    125.  
    126. 				}
    127. 			}
    128. 			// grandfather->_right == parent
    129. 			else
    130. 			{
    131. 				Node* uncle = grandfather->_left;
    132. 				// 情况一：叔叔存在且为红
    133. 				if (uncle && uncle->_col == RED)
    134. 				{
    135. 					// 变色
    136. 					parent->_col = uncle->_col = BLACK;
    137. 					grandfather->_col = RED;
    138.  
    139. 					// 继续往上处理
    140. 					cur = grandfather;
    141. 					parent = cur->_parent;
    142. 				}
    143. 				// 叔叔不存在 or 叔叔存在且为黑
    144. 				else
    145. 				{
    146. 					// 情况二：单旋(左单旋)
    147. 					if (cur == parent->_right)
    148. 					{
    149. 						// g
    150. 						//   p
    151. 						//     c 
    152. 						RotateL(grandfather);
    153. 						parent->_col = BLACK;
    154. 						grandfather->_col = RED;
    155. 					}
    156. 					// 情况三：双旋(右左双旋)
    157. 					else
    158. 					{
    159. 						// g
    160. 						//   p
    161. 						// c
    162. 						RotateR(parent);
    163. 						RotateL(grandfather);
    164. 						cur->_col = BLACK;
    165. 						grandfather->_col = RED;
    166. 					}
    167.  
    168. 					break;
    169. 				}
    170. 			}
    171. 		}
    172.  
    173. 		_root->_col = BLACK;
    174.  
    175. 		return true;
    176. 	}
    177.  
    178. private:
    179. 	void RotateL(Node* parent)
    180. 	{
    181. 		Node* subR = parent->_right;
    182. 		Node* subRL = subR->_left;
    183.  
    184. 		parent->_right = subRL;
    185. 		if (subRL)
    186. 			subRL->_parent = parent;
    187.  
    188. 		Node* ppNode = parent->_parent;
    189.  
    190. 		subR->_left = parent;
    191. 		parent->_parent = subR;
    192.  
    193. 		if (parent == _root)
    194. 		{
    195. 			_root = subR;
    196. 			_root->_parent = nullptr;
    197. 		}
    198. 		else
    199. 		{
    200. 			if (parent == ppNode->_left)
    201. 			{
    202. 				ppNode->_left = subR;
    203. 			}
    204. 			else
    205. 			{
    206. 				ppNode->_right = subR;
    207. 			}
    208.  
    209. 			subR->_parent = ppNode;
    210. 		}
    211. 	}
    212.  
    213. 	void RotateR(Node* parent)
    214. 	{
    215. 		Node* subL = parent->_left;
    216. 		Node* subLR = subL->_right;
    217.  
    218. 		parent->_left = subLR;
    219. 		if (subLR)
    220. 			subLR->_parent = parent;
    221.  
    222. 		Node* ppNode = parent->_parent;
    223.  
    224. 		subL->_right = parent;
    225. 		parent->_parent = subL;
    226.  
    227. 		if (parent == _root)
    228. 		{
    229. 			_root = subL;
    230. 			_root->_parent = nullptr;
    231. 		}
    232. 		else
    233. 		{
    234. 			if (ppNode->_left == parent)
    235. 			{
    236. 				ppNode->_left = subL;
    237. 			}
    238. 			else
    239. 			{
    240. 				ppNode->_right = subL;
    241. 			}
    242. 			subL->_parent = ppNode;
    243. 		}
    244.  
    245. 	}
    246.  
    247. 	bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
    248. 	{
    249. 		// 走到null之后，判断k和black是否相等
    250. 		if (nullptr == pRoot)
    251. 		{
    252. 			if (k != blackCount)
    253. 			{
    254. 				cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
    255. 				return false;
    256. 			}
    257. 			
    258. 			return true;
    259. 		}
    260.  
    261. 		// 统计黑色节点的个数
    262. 		if (BLACK == pRoot->_col)
    263. 		{
    264. 			k++; 
    265. 		}
    266.  
    267. 		// 检测当前节点与其双亲是否都为红色
    268. 		if (RED == pRoot->_col && pRoot->_parent && pRoot->_parent->_col == RED)
    269. 		{
    270. 			cout << "违反性质三：存在连在一起的红色节点" << endl;
    271. 			return false;
    272. 		}
    273.  
    274. 		return _IsValidRBTree(pRoot->_left, k, blackCount) &&
    275. 			_IsValidRBTree(pRoot->_right, k, blackCount);
    276. 	}
    277.  
    278. public:
    279. 	bool IsBalanceTree()
    280. 	{
    281. 		// 检查红黑树几条规则
    282. 		Node* pRoot = _root;
    283. 		// 空树也是红黑树
    284. 		if (nullptr == pRoot)
    285. 			return true;
    286.  
    287. 		// 检测根节点是否满足情况
    288. 		if (BLACK != pRoot->_col)
    289. 		{
    290. 			cout << "违反红黑树性质二：根节点必须为黑色" << endl;
    291. 			return false;
    292. 		}
    293.  
    294. 		// 获取任意一条路径中黑色节点的个数 -- 比较基准值
    295. 		size_t blackCount = 0;
    296. 		Node* pCur = pRoot;
    297. 		while (pCur)
    298. 		{
    299. 			if (BLACK == pCur->_col)
    300. 				blackCount++;
    301.  
    302. 			pCur = pCur->_left;
    303. 		}
    304.  
    305. 		// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
    306. 		size_t k = 0;
    307. 		return _IsValidRBTree(pRoot, k, blackCount);
    308. 	}
    309. private:
    310. 	Node* _root = nullptr;
    311. };
  • 相关阅读:
    I2C总线实现逻辑
    Linux 日志系统
    30万以上的qps高并发服务如何优化
    Flutter高仿微信-第22篇-支付-二维码收款(二维码)
    【AI大模型】赋能儿童安全：楼层与室内定位实践与未来发展
    基于Springboot+vue的甜品蛋糕销售商城网站 elementui
    Python的math.sqrt()和math.pow()的使用
    web网页制作与实现 html+css+javascript+jquery+bootstarp响应式美食网站设计与实现
    zookeeper集群部署安装
    C++之类型转换
  • 原文地址：https://blog.csdn.net/qq_60750110/article/details/126199868