• 红黑树C++实现

    目录

    一、红黑树的概念

    二、红黑树的性质

    三、红黑树节点的定义

    四、红黑树的插入

    4.1 插入节点

    4.2 插入节点的颜色

    4.3 调整情况1

    4.4 调整情况2

    4.5 调整情况3

    4.6 调整情况总结

    五、调整的实现

    5.1 调整的步骤分析

    5.2 代码实现

    六、树的平衡判断

    七、源代码+测试代码

    一、红黑树的概念

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

    二、红黑树的性质

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

    解读：

    性质三：保证树中没有连续的红色节点

    性质四：每条路径上黑色节点的数目相同

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

    其中，其极限最短：全黑。极限最长：一黑一红……

    三、红黑树节点的定义

     因为性质一，节点的颜色不是红就是黑，所以我们可以使用枚举来清晰的区分。

    四、红黑树的插入

    4.1 插入节点

    红黑树本质也是二叉搜索树，所以插入的方式是相同的。只是调整平衡的方式不同。插入的代码如下：

    1. bool Insert(const pair& kv)
    2. 	{
    3. 		if (!_root)
    4. 		{
    5. 			_root = new Node(kv);
    6. 			_root->_col = BLACK;
    7. 			return true;
    8. 		}
    9. 		Node* parent = nullptr;
    10. 		Node* cur = _root;
    11. 		//找插入的位置
    12. 		while (cur)
    13. 		{
    14. 			if (cur->_kv.first > kv.first)
    15. 			{
    16. 				parent = cur;
    17. 				cur = cur->_left;
    18. 			}
    19. 			else if (cur->_kv.first < kv.first)
    20. 			{
    21. 				parent = cur;
    22. 				cur = cur->_right;
    23. 			}
    24. 			else
    25. 			{
    26. 				return false;
    27. 			}
    28. 		}
    29. 		cur = new Node(kv);
    30. 		if (parent->_kv.first > kv.first)
    31. 		{
    32. 			parent->_left = cur;
    33. 		}
    34. 		else
    35. 		{
    36. 			parent->_right= cur;
    37. 		}
    38. 		cur->_parent = parent;
    39. 	}

    4.2 插入节点的颜色

    接下来我们就要分析，插入的节点默认应该是红色还是黑色。

    首先分析插入黑节点。如下：

     插入黑节点后，直接就破坏了红黑树的规则四，因为每条路径上的黑色节点数不再相同了，所以说插入黑节点是一定会出错的。

    接下来我们看看插入红节点。

     此中情况下，破坏了规则三，其红节点下必须是黑节点。

    在这种情况下，插入红节点，既没有破坏规则三，也没有破坏规则四。所以说，插入红节点有几率会破坏规则，而插入黑节点一定会破坏规则，且破坏了整棵树，所以我们默认插入红节点。

    那如果出现以上插入红节点破坏规则我们要怎么处理呢？

    我们采取 变色+旋转 的策略，以上这种情况我们只需要变色即可解决。如图所示：

    因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；

    但当新插入节点的双亲结点颜色为红色时，就违反了性质三不能有连续在一起的红色节点，此时就需要对红色数分情况来解决。

    即双亲黑色不调整，双亲红色则调整。

    4.3 调整情况1

    情况一：cur 为红，parent为红，grandfather为黑，uncle存在且为红.

    解决方式：将p，u 改为黑，g改为红，然后把 g 当作 cur，继续向上调整。

    4.4 调整情况2

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

    1. 如果 u 节点不存在，则 cur 一定是新插入节点，因为如果 cur 不是新插入节点，则 cur 和 p 一定有一个节点的颜色是黑色，就不满足性质4：每条路径黑色节点的个数相同。
    2. 如果 u 节点存在，则其一定是黑色的，那么 cur 节点原来的颜色一定是黑色的，现在看到其是红色的原因是因为 cur 的子树在调整的过程中将 cur 节点的颜色由黑色改成红色。

     此时这种情况，单纯的变色是无法解决的，我们就要采取旋转+变色的方式。

    此时我们的解决策略是将 p 变黑，g 变红，然后让其对 g 进行右单旋。

    4.5 调整情况3

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

     调整策略：

    p 为 g 的左孩子，cur 为 p 的右孩子，则针对 p 进行左单旋，则转变为情况 2，然后再进行情况 2 的右单旋+变色即可。

    4.6 调整情况总结

    在学习了AVL 树 之后，这三种情况其实也都能理解，接下来我们对其做一个总结。

    红黑树的关键在于叔叔。因为知道叔叔节点的情况，可以了解到另一棵子树的高度情况。

    三种情况：

    1. u 存在且为红，变色并继续向上处理
    2. u 不存在或为黑，进行 单旋+变色
    3. u 不存在或为黑，插入方式为折线，进行 双旋+变色。

    五、调整的实现

    5.1 调整的步骤分析

    1. 只有当cur 为红，p 为红，g 为黑，则进行调整。(p为黑不用调整，p 为红，则grandfather必然为黑，要不然此时不为红黑树)
    2. 查看 uncle 的位置，同时也是判断插入节点在 g 的左子树还是右子树。
    3. 情况1，uncle存在且为红，进行情况一的调整(变色+继续往上更新)。
    4. 如果uncle不存在或为黑，则为情况二或三
    5. 如果插入在边侧，则进行单旋+变色
    6. 如果插入在内侧，则进行双旋+变色。

    5.2 代码实现

    以下只有调整的代码，没有截取插入的代码。

    1. //1.因为插入的节点为红色， 如果parent也为红色，进行处理
    2. while (parent && parent->_col == RED)
    3. {
    4. 	Node* grandfater = parent->_parent;
    5. 	//2.判断爷节点的合法性
    6. 	assert(grandfater);
    7. 	assert(grandfater->_col == BLACK);
    8. 	//3.查看叔叔
    9. 	//4.首先判断叔叔位于grandfater的left 还是 right
    10. 	if (grandfater->_left == parent)
    11. 	{
    12. 		Node* uncle = grandfater->_right;
    13. 		//5.情况1，叔叔存在 && 叔叔为红色
    14. 		if (uncle && uncle->_col == RED)
    15. 		{
    16. 			//6.将父、树变黑，祖父变红
    17. 			parent->_col = uncle->_col = BLACK;
    18. 			grandfater->_col = RED;
    19. 			//7.并继续往上处理
    20. 			cur = grandfater;
    21. 			parent = cur->parent;
    22. 		}
    23. 		//8.情况2+情况3  uncle不存在或为黑
    24. 		else
    25. 		{
    26. 			//9.判断单旋还是双旋
    27. 			//      g          
    28. 			//    p   u
    29. 			//  c            右单旋+变色
    30. 			if (cur == parent->_left)
    31. 			{
    32. 				RotateR(grandfater);
    33. 				parent->_col = BLACK;
    34. 				grandfater->_col = RED;
    35. 			}
    36. 			//    g          左右双旋+变色
    37. 			//   p  u        
    38. 			//    c
    39. 			else
    40. 			{
    41. 				RotateL(parent);
    42. 				RotateR(grandfater);
    43. 				cur->_col = BLACK;
    44. 				grandfater->_col = RED;
    45. 			}
    46. 			break;
    47. 		}
    48. 	}
    49. 	else
    50. 	{
    51. 		Node* uncle = grandfater->_left;
    52. 		if (uncle && uncle->_col == RED)
    53. 		{
    54. 			parent->_col = uncle->_col = BLACK;
    55. 			grandfater->_col = RED;
    56. 			//继续往上处理
    57. 			cur = grandfater;
    58. 			parent = cur->parent;
    59. 		}
    60. 		else
    61. 		{
    62. 			//9.判断单旋还是双旋
    63. 			//      g          
    64. 			//    u   p
    65. 			//          c    左单旋+变色
    66. 			if (cur == parent->_right)
    67. 			{
    68. 				RotateL(grandfater);
    69. 				parent->_col = BLACK;
    70. 				grandfater->_col = RED;
    71. 			}
    72. 			//    g          右左双旋+变色
    73. 			//   u  p        
    74. 			//     c
    75. 			else
    76. 			{
    77. 				RotateR(parent);
    78. 				RotateL(grandfater);
    79. 				cur->_col = BLACK;
    80. 				grandfater->_col = RED;
    81. 			}
    82. 			break;
    83. 		}
    84. 	}
    85. }
    86.  
    87. //因为以上会将祖父变红，直接将_root变黑
    88. _root->_color = BLACK;
    89. return true;

    好的，实现了插入之后，我们来使用一段测试代码测试一下 Insert

    六、树的平衡判断

    实现 Insert 之后，只能证明当前的结构是一棵搜索树，而不能证明其是否为红黑树，接下来我们还要编写一个Balanceu验证平衡。

    所以这个判定平衡的函数应该按照红黑树的规则，来进行判定该树是否符合红黑树的性质。即，算每条路径上的黑节点数量，如果路径上的黑节点数量相同，则说明是红黑树。

    实现步骤：

    1. 计算最左/右边路径上的黑节点个数，将该值设为基准值。
    2. 走前序遍历，遇到黑节点则将将计数器++
    3. 如果当前节点的为红，并且父节点也为红则直接返回false。
    4. 如果该路径上的黑节点总数等于基准值，则返回true，反之返回false。

    代码如下：

    1.  
    2. bool IsBalance()
    3. {
    4. 	if (_root == nullptr)
    5. 	{
    6. 		return true;
    7. 	}
    8. 	if (_root->_col == RED)
    9. 	{
    10. 		cout << "根节点不是黑色" << endl;
    11. 		return false;
    12. 	}
    13.  
    14. 	//设置基准值,以来校验路径上的黑节点
    15. 	int benchmark = 0;
    16. 	Node* cur = _root;
    17.     //计算左侧路径上的黑色节点数量
    18. 	while (cur)
    19. 	{
    20. 		if (cur->_col == BLACK)
    21. 		{
    22. 			++benchmark;
    23. 		}
    24. 		cur = cur->_left;
    25. 	}
    26. 	return PrevCheck(_root, 0, benchmark);
    27. }
    28. bool PrevCheck(Node* root, int blackNum, int Benchmark)
    29. {
    30. 	if (root == nullptr)
    31. 	{
    32. 		if (blackNum != Benchmark)
    33. 			return false;
    34. 		else
    35. 			return true;
    36. 	}
    37. 	if (root->_col == BLACK)
    38. 		++blackNum;
    39. 	if (root->_col == RED && root->_parent->_col == RED)
    40. 	{
    41. 		cout << "存在连续的红色节点" << endl;
    42. 		return false;
    43. 	}
    44.  
    45. 	return PrevCheck(root->_left, blackNum, Benchmark)
    46. 		&& PrevCheck(root->_right, blackNum, Benchmark);
    47. }

    以上检查方式就按照红黑树的三条重要性质进行了检查，

    1.根节点为黑色；2.不存在连续的红节点；3.每条路径上的黑节点个数相同。

    满足以上三点才能证明该结构为红黑树。

    接下来我们进入测试。

     测试一：

    测试二：

    注意一件事情，我们使用的是键值对的形式进行插入的，如果 k 存在了，则不会进行插入，并且红黑树中的排序是按照 k 的大小进行排序的，所以使用 find 函数时，要按 pair.first 查找，因为 pair.second并按搜索树的规则存储的。 

    七、源代码+测试代码

    红黑树代码(实现了插入、查找、中序遍历、高度、平衡检测)

    1. #include 
    2. using namespace std;
    3.  
    4. enum Color { RED, BLACK };
    5. //节点的定义
    6. template <class K,class V>
    7. struct RBTreeNode
    8. {
    9. 	RBTreeNode* _left;	
    10. 	RBTreeNode* _right;	
    11. 	RBTreeNode* _parent;	
    12.  
    13. 	pair _kv;			    
    14. 	Color _col;					
    15.  
    16. 	RBTreeNode(const pair& kv)
    17. 		:_left(nullptr)
    18. 		, _right(nullptr)
    19. 		, _parent(nullptr)
    20. 		, _kv(kv)
    21. 		, _col(RED)               
    22. 	{}
    23. };
    24. //红黑树
    25. template <class K, class V>
    26. class RBTree
    27. {
    28. 	typedef RBTreeNode Node;
    29. public:
    30. 	bool Insert(const pair& kv)
    31. 	{
    32. 		if (!_root)
    33. 		{
    34. 			_root = new Node(kv);
    35. 			_root->_col = BLACK;
    36. 			return true;
    37. 		}
    38. 		Node* parent = nullptr;
    39. 		Node* cur = _root;
    40. 		while (cur)
    41. 		{
    42. 			if (cur->_kv.first > kv.first)
    43. 			{
    44. 				parent = cur;
    45. 				cur = cur->_left;
    46. 			}
    47. 			else if (cur->_kv.first < kv.first)
    48. 			{
    49. 				parent = cur;
    50. 				cur = cur->_right;
    51. 			}
    52. 			else
    53. 			{
    54. 				return false;
    55. 			}
    56. 		}
    57. 		cur = new Node(kv);
    58. 		if (parent->_kv.first > kv.first)
    59. 		{
    60. 			parent->_left = cur;
    61. 		}
    62. 		else
    63. 		{
    64. 			parent->_right = cur;
    65. 		}
    66. 		cur->_parent = parent;
    67. 		while (parent && parent->_col == RED)
    68. 		{
    69. 			Node* grandfater = parent->_parent;
    70. 			assert(grandfater);
    71. 			assert(grandfater->_col == BLACK);
    72. 			if (grandfater->_left == parent)
    73. 			{
    74. 				Node* uncle = grandfater->_right;
    75. 				if (uncle && uncle->_col == RED)
    76. 				{
    77. 					parent->_col = uncle->_col = BLACK;
    78. 					grandfater->_col = RED;
    79. 					cur = grandfater;
    80. 					parent = cur->_parent;
    81. 				}
    82. 				else
    83. 				{
    84. 					if (cur == parent->_left)
    85. 					{
    86. 						RotateR(grandfater);
    87. 						parent->_col = BLACK;
    88. 						grandfater->_col = RED;
    89. 					}					else
    90. 					{
    91. 						RotateL(parent);
    92. 						RotateR(grandfater);
    93. 						cur->_col = BLACK;
    94. 						grandfater->_col = RED;
    95. 					}
    96. 					break;
    97. 				}
    98. 			}
    99. 			else
    100. 			{
    101. 				Node* uncle = grandfater->_left;
    102. 				if (uncle && uncle->_col == RED)
    103. 				{
    104. 					parent->_col = uncle->_col = BLACK;
    105. 					grandfater->_col = RED;
    106. 					cur = grandfater;
    107. 					parent = cur->_parent;
    108. 				}
    109. 				else
    110. 				{
    111. 					if (cur == parent->_right)
    112. 					{
    113. 						RotateL(grandfater);
    114. 						parent->_col = BLACK;
    115. 						grandfater->_col = RED;
    116. 					}
    117. 					else
    118. 					{
    119. 						RotateR(parent);
    120. 						RotateL(grandfater);
    121. 						cur->_col = BLACK;
    122. 						grandfater->_col = RED;
    123. 					}
    124. 					break;
    125. 				}
    126. 			}
    127. 		}
    128. 		_root->_col = BLACK;
    129. 		return true;
    130.  
    131. 	}
    132. 	void Inorder()
    133. 	{
    134. 		_Inorder(_root);
    135. 	}
    136. 	int Height()
    137. 	{
    138. 		return _Height(_root);
    139. 	}
    140. 	pair Find(const K& key)
    141. 	{
    142. 		Node* cur = _root;
    143. 		while (cur)
    144. 		{
    145. 			if (cur->_kv.first > key)
    146. 			{
    147. 				cur = cur->_left;
    148. 			}
    149. 			else if (cur->_kv.first < key)
    150. 			{
    151. 				cur = cur->_right;
    152. 			}
    153. 			else
    154. 			{
    155. 				return cur->_kv;
    156. 			}
    157. 		}
    158. 		return pair<int, int>(0, 0);
    159. 	}
    160. 	bool IsBalance()
    161. 	{
    162. 		if (_root == nullptr)
    163. 		{
    164. 			return true;
    165. 		}
    166. 		if (_root->_col == RED)
    167. 		{
    168. 			cout << "根节点不是黑色" << endl;
    169. 			return false;
    170. 		}
    171.  
    172. 		//设置基准值,以来校验路径上的黑节点
    173. 		int benchmark = 0;
    174. 		Node* cur = _root;
    175. 		while (cur)
    176. 		{
    177. 			if (cur->_col == BLACK)
    178. 			{
    179. 				++benchmark;
    180. 			}
    181. 			cur = cur->_left;
    182. 		}
    183. 		return PrevCheck(_root,0, benchmark);
    184. 	}
    185. 	
    186. private:
    187.  
    188. 	bool PrevCheck(Node* root, int blackNum,int Benchmark)
    189. 	{
    190. 		if (root==nullptr)
    191. 		{
    192. 			//cout << blackNum << endl;
    193. 			if (blackNum == 2)                 //     3 
    194. 			{                                  //   7   16
    195. 				int n = 0;                     //      11
    196. 			}                                  //
    197. 			if (blackNum != Benchmark)
    198. 				return false;
    199. 			else 
    200. 			return true;
    201. 		}
    202. 		if (root->_col == BLACK)
    203. 			++blackNum;
    204. 		if (root->_col == RED && root->_parent->_col == RED)
    205. 		{
    206. 			cout << "存在连续的红色节点" << endl;
    207. 			return false;
    208. 		}
    209.  
    210. 		return PrevCheck(root->_left, blackNum, Benchmark)
    211. 		&& PrevCheck(root->_right, blackNum, Benchmark);
    212. 	}
    213.  
    214. 	void _Inorder(Node* root)
    215. 	{
    216. 		if (root)
    217. 		{
    218. 			_Inorder(root->_left);
    219. 			cout << root->_kv.first << ":" << root->_kv.second << endl;
    220. 			_Inorder(root->_right);
    221. 		}
    222. 	}
    223.  
    224. 	int _Height(Node* root)
    225. 	{
    226. 		if (root == nullptr)
    227. 			return 0;
    228. 		return max(_Height(root->_left), _Height(root->_right)) + 1;
    229. 	}
    230.  
    231. 	void RotateL(Node* parent)
    232. 	{
    233. 		Node* subR = parent->_right;
    234. 		Node* subRL = subR->_left;
    235.  
    236. 		parent->_right = subRL;
    237. 		subR->_left = parent;
    238. 		if (subRL)  
    239. 			subRL->_parent = parent;
    240.  
    241. 		Node* ppNode = parent->_parent;
    242. 		parent->_parent = subR;
    243. 		if (_root == parent)
    244. 		{
    245. 			_root = subR;
    246. 			subR->_parent = nullptr;
    247. 		}
    248. 		else  
    249. 		{
    250. 			if (ppNode->_left == parent)
    251. 			{
    252. 				ppNode->_left = subR;
    253. 			}
    254. 			else
    255. 			{
    256. 				ppNode->_right = subR;
    257. 			}
    258. 			subR->_parent = ppNode;
    259. 		}
    260. 	}
    261.  
    262. 	void RotateR(Node* parent)
    263. 	{
    264. 		Node* subL = parent->_left;
    265. 		Node* subLR = subL->_right;
    266.  
    267. 		parent->_left = subLR;
    268. 		if (subLR)
    269. 			subLR->_parent = parent;
    270.  
    271. 		Node* ppNode = parent->_parent;
    272. 		subL->_right = parent;
    273. 		parent->_parent = subL;
    274. 		if (ppNode)
    275. 		{
    276. 			if (ppNode->_left == parent)
    277. 			{
    278. 				ppNode->_left = subL;
    279. 			}
    280. 			else
    281. 			{
    282. 				ppNode->_right = subL;
    283. 			}
    284. 			subL->_parent = ppNode;
    285. 		}
    286. 		else
    287. 		{
    288. 			_root = subL;
    289. 			subL->_parent = nullptr;
    290. 		}
    291. 	}
    292.     //成员变量 _root 
    293. 	Node* _root=nullptr; 
    294. };

    测试代码

    1. void TestRBTree1()
    2. {
    3. 	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    4. 	RBTree<int, int> t1;
    5. 	for (auto e : a)
    6. 	{
    7. 		t1.Insert(e);
    8. 	}
    9. 	t1.Inorder();
    10.  
    11. 	//检测是否为红黑树
    12. 	if (t1.IsBalance())
    13. 		cout << "Is RedBlackTree" << endl;
    14. 	else
    15. 		cout << "Not RedBlackTree" << endl;
    16.  
    17. 	//查找 18 
    18. 	cout << "Find（18）：";
    19. 	int result = t1.Find(18);
    20. 	cout << result<< endl;
    21.  
    22. }
    23.  
    24. void TestRBTree2()
    25. {
    26. 	size_t N = 10000000;
    27. 	RBTree<int, int> t1;
    28. 	for (size_t i = 0; i < N; ++i)
    29. 	{
    30. 		t1.Insert(i);
    31. 	}
    32. 	cout <<"Height:" << t1.Height() << endl;
    33.  
    34. 	//检测是否为红黑树
    35. 	if (t1.IsBalance())
    36. 		cout << "Is RedBlackTree" << endl;
    37. 	else
    38. 		cout << "Not RedBlackTree" << endl;
    39.  
    40. 	int  result = t1.Find(23451);
    41. 	cout << result<< endl;
    42.  
    43. }
    44.  
    45. int main()
    46. {
    47. 	TestRBTree1();
    48. 	TestRBTree2();
    49. 	return 0;
    50. }

  • 相关阅读:
    MyBatis学习：MyBatis框架下执行SQL语句传递基本类型参数
    119.(前端)商品管理增加基本信息布局——model与ref与prop概念介绍、使用级联选择器与tab中使用form表单
    黑盒子问题
    《nlp入门+实战：第八章：使用Pytorch实现手写数字识别》
    includes问题
    MyBatis级联查询和缓存
    leetcode - 学习计划之剑指offer
    ERR_PNPM_NO_GLOBAL_BIN_DIR Unable to find the global bin directory
    理论+实践，带你了解分布式训练
    【Android Gradle 插件】Gradle 构建机制 ④ ( Gradle 构建生命周期 | 初始阶段 | 配置阶段 | 执行阶段 )
  • 原文地址：https://blog.csdn.net/Brant_zero/article/details/127866054