• C++_红黑树

           

    目录

    1、红黑树的规则

    2、红黑树节点的定义 

    3、红黑树插入节点的调整操作

    3.1 情况一

    3.2 情况二

    3.3 情况三 

    4、红黑树的实现

    结语

    前言：

            在C++中，红黑树是二叉搜索树的另一种优化版本，他与AVL树的区别在于保持树的平衡方式不同，AVL树保持平衡的方式是在节点中多存储一个成员来记录平衡因子，红黑树保持平衡的方式也是增加了一个成员，但是该成员的作用是记录节点的两种状态（颜色）：红色--黑色。当然只记录颜色并不能保持平衡，红黑树还规定最长路径的节点个数不会超过最短路径的节点个数的两倍，因此红黑树不会因为插入有序数据而演变成“单支树”。

    1、红黑树的规则

            红黑树有如下规则：

            1、顾名思义，红黑树的节点只能有黑色和红色两种状态。

            2、根结点默认为黑色。

            3、红色节点的两个孩子只能是黑色节点。

            4、插入的节点默认为红色节点。

            5、每条路径的黑色节点都相同。

            红黑树正确示意图：

             红黑树错误示意图：

    2、红黑树节点的定义 

            通过上述对红黑树的简述，可以给出红黑树的节点代码：

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2.  
    3. enum Colour//定义一个枚举
    4. {
    5. 	RED,
    6. 	BLACK,
    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. 	Colour _col;//若是AVL树这里记载的是平衡因子，红黑树是颜色
    17.  
    18. 	RBTreeNode(const pair& kv)
    19. 		:_left(nullptr)
    20. 		, _right(nullptr)
    21. 		, _parent(nullptr)
    22. 		, _kv(kv)
    23. 		, _col(RED)//默认插入的节点是红色
    24. 	{}
    25. };

            可以发现，红黑树的节点代码几乎和AVL树一模一样，只是控制平衡的条件有区别，仅此而已。 

    3、红黑树插入节点的调整操作

            红黑树的插入函数可以分两个步骤：

            1、找到合适的位置插入，即二叉搜索树插入的逻辑（小于根节点的放在左边，大于根节点的放在右边）。

            2、因为插入的节点默认为红色，则插入节点后，查看当前树是否破坏了红黑树的规则，即观察其节点的父母节点是否为红色，如果是则需要进行调整操作（规则3）。

            在分析之前，先确定好节点之间的关系名称（cur表示新插入的节点，parant表示父母节点，uncle表示叔叔节点，gparent表示祖父节点）：

    3.1 情况一

            当叔叔节点存在且为红，父母节点为红，祖父节点为黑：

            最后可以发现，经过一系列的调整后符号红黑树的规则。

    3.2 情况二

            情况二又分两种情况：1、叔叔节点为黑色。2、不存在叔叔节点。

            1、其他条件和情况一相同，但是叔叔节点是黑色的：

            从上图可以发现，情况二多了旋转的步骤，并且在旋转之后将parent变黑，gparent变红，最终结果满足红黑树的规则。

            2、若不存在叔叔节点：

            综上所述，情况二可以总结为：旋转+变色（parent变黑，gparent变红）。 

    3.3 情况三 

            情况三即以上情况的插入点不一样，以上情况的插入节点都是插入在“边缘处”，通俗来讲就是左子树插入的节点都是作为左孩子插入的，而右子树插入的节点都是作为右孩子插入的，但是实际中总会出现在右子树中插入的节点是以左孩子的形式插入的（如下图），拿上述情况二的第二种情况举例，若插入的cur在parent的左边，那么以上的处理方法显然不能解决问题，具体操作图如下：

    4、红黑树的实现

            红黑树的实现代码如下：

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2.  
    3. #include
    4. using namespace std;
    5.  
    6. enum Colour//定义一个枚举
    7. {
    8. 	RED,
    9. 	BLACK,
    10. };
    11.  
    12. template<class K, class V>
    13. struct RBTreeNode
    14. {
    15. 	RBTreeNode* _left;//指向左孩子
    16. 	RBTreeNode* _right;//指向右孩子
    17. 	RBTreeNode* _parent;//指向父母节点
    18. 	pair _kv;//记录数据
    19. 	Colour _col;//若是AVL树这里记载的是平衡因子，红黑树是颜色
    20.  
    21. 	RBTreeNode(const pair& kv)
    22. 		:_left(nullptr)
    23. 		, _right(nullptr)
    24. 		, _parent(nullptr)
    25. 		, _kv(kv)
    26. 		, _col(RED)//默认插入的节点是红色
    27. 	{}
    28. };
    29.  
    30. template<class K, class V>
    31. class RBTree//红黑树类
    32. {
    33. 	typedef RBTreeNode Node;
    34. public:
    35. 	~RBTree()
    36. 	{
    37. 		_Destroy(_root);
    38. 		_root = nullptr;
    39. 	}
    40. public:
    41. 	bool Insert(const pair& kv)//插入函数
    42. 	{
    43. 		if (_root == nullptr)
    44. 		{
    45. 			_root = new Node(kv);
    46. 			_root->_col = BLACK;//第一次插入的根结点手动置黑
    47. 			return true;
    48. 		}
    49.  
    50. 		Node* parent = nullptr;
    51. 		Node* cur = _root;
    52. 		while (cur)
    53. 		{
    54. 			if (cur->_kv.first < kv.first)
    55. 			{
    56. 				parent = cur;
    57. 				cur = cur->_right;
    58. 			}
    59. 			else if (cur->_kv.first > kv.first)
    60. 			{
    61. 				parent = cur;
    62. 				cur = cur->_left;
    63. 			}
    64. 			else
    65. 			{
    66. 				return false;
    67. 			}
    68. 		}
    69.  
    70. 		cur = new Node(kv);
    71. 		if (parent->_kv.first > kv.first)
    72. 		{
    73. 			parent->_left = cur;
    74. 		}
    75. 		else
    76. 		{
    77. 			parent->_right = cur;
    78. 		}
    79. 		cur->_parent = parent;
    80.  
    81. 		//当parent为红色则违法规则，需要调整
    82. 		while (parent && parent->_col == RED)
    83. 		{
    84. 			Node* grandfather = parent->_parent;
    85. 			if (grandfather->_left == parent)//父母在祖父的左边
    86. 			{
    87. 				Node* uncle = grandfather->_right;
    88. 				// 情况1：叔叔节点存在且为红，叔叔和父母进行变色处理，并继续往上处理
    89. 				if (uncle && uncle->_col == RED)
    90. 				{
    91. 					parent->_col = BLACK;
    92. 					uncle->_col = BLACK;
    93. 					grandfather->_col = RED;
    94.  
    95. 					// 继续往上调整
    96. 					cur = grandfather;
    97. 					parent = cur->_parent;
    98. 				}
    99. 				else // 情况2：叔叔不存在/叔叔存在且为黑，旋转+变色
    100. 				{
    101. 					//父母在祖父的左边，而cur在父母的左边，说明是“边缘”情况
    102. 					if (cur == parent->_left)
    103. 					{
    104. 						RotateR(grandfather);
    105. 						parent->_col = BLACK;
    106. 						grandfather->_col = RED;
    107. 					}
    108. 					else//对应所述的情况三，需要旋转两次，并且cur变成了根结点
    109. 					{
    110. 						RotateL(parent);
    111. 						RotateR(grandfather);
    112. 						cur->_col = BLACK;
    113. 						grandfather->_col = RED;
    114. 					}
    115. 					break;
    116. 				}
    117. 			}
    118. 			else // 父母在祖父的右边
    119. 			{
    120. 				Node* uncle = grandfather->_left;
    121. 				// 情况1：u存在且为红，变色处理，并继续往上处理
    122. 				if (uncle && uncle->_col == RED)
    123. 				{
    124. 					parent->_col = BLACK;
    125. 					uncle->_col = BLACK;
    126. 					grandfather->_col = RED;
    127.  
    128. 					// 继续往上调整
    129. 					cur = grandfather;
    130. 					parent = cur->_parent;
    131. 				}
    132. 				else // 情况2：叔叔不存在/叔叔存在且为黑，旋转+变色
    133. 				{
    134. 					//以下逻辑同上思路，只不过逻辑相反
    135. 					if (cur == parent->_right)
    136. 					{
    137. 						RotateL(grandfather);
    138. 						grandfather->_col = RED;
    139. 						parent->_col = BLACK;
    140. 					}
    141. 					else
    142. 					{
    143. 						RotateR(parent);
    144. 						RotateL(grandfather);
    145. 						cur->_col = BLACK;
    146. 						grandfather->_col = RED;
    147. 					}
    148.  
    149. 					break;
    150. 				}
    151. 			}
    152. 		}
    153. 		_root->_col = BLACK;//根结点始终为黑
    154.  
    155. 		return true;
    156. 	}
    157.  
    158. 	void InOrder()
    159. 	{
    160. 		_InOrder(_root);
    161. 	}
    162.  
    163. 	bool IsRedB()//检查红黑树
    164. 	{
    165. 		if (_root && _root->_col == RED)
    166. 		{
    167. 			cout << "根节点颜色是红色" << endl;
    168. 			return false;
    169. 		}
    170.  
    171. 		int benchmark = 0;
    172. 		Node* cur = _root;
    173. 		while (cur)
    174. 		{
    175. 			if (cur->_col == BLACK)
    176. 				++benchmark;
    177. 			cur = cur->_left;
    178. 		}
    179.  
    180. 		// 连续红色节点
    181. 		return _Check(_root, 0, benchmark);
    182. 	}
    183.  
    184. 	int Height()
    185. 	{
    186. 		return _Height(_root);
    187. 	}
    188.  
    189. private:
    190. 	void _Destroy(Node* root)//释放空间
    191. 	{
    192. 		if (root == nullptr)
    193. 		{
    194. 			return;
    195. 		}
    196.  
    197. 		_Destroy(root->_left);
    198. 		_Destroy(root->_right);
    199. 		delete root;
    200. 	}
    201.  
    202. 	int _Height(Node* root)
    203. 	{
    204. 		if (root == NULL)
    205. 			return 0;
    206.  
    207. 		int leftH = _Height(root->_left);
    208. 		int rightH = _Height(root->_right);
    209.  
    210. 		return leftH > rightH ? leftH + 1 : rightH + 1;
    211. 	}
    212.  
    213. 	bool _Check(Node* root, int blackNum, int benchmark)//红黑树的验证
    214. 	{
    215. 		if (root == nullptr)//走到空，就判断黑色节点数量是否一样
    216. 		{
    217. 			if (benchmark != blackNum)
    218. 			{
    219. 				cout << "某条路径黑色节点的数量不相等" << endl;
    220. 				return false;
    221. 			}
    222.  
    223. 			return true;
    224. 		}
    225.  
    226. 		if (root->_col == BLACK)//重新记录每条路径下的黑色节点
    227. 		{
    228. 			++blackNum;
    229. 		}
    230.  
    231. 		if (root->_col == RED
    232. 			&& root->_parent
    233. 			&& root->_parent->_col == RED)//连续红色节点也会报错
    234. 		{
    235. 			cout << "存在连续的红色节点" << endl;
    236. 			return false;
    237. 		}
    238.  
    239. 		//每次递归都把黑色节点数量传给下一个栈帧
    240. 		return _Check(root->_left, blackNum, benchmark)
    241. 			&& _Check(root->_right, blackNum, benchmark);
    242. 	}
    243.  
    244. 	void _InOrder(Node* root)//中序遍历打印
    245. 	{
    246. 		if (root == nullptr)
    247. 		{
    248. 			return;
    249. 		}
    250.  
    251. 		_InOrder(root->_left);
    252. 		cout << root->_kv.first << " ";
    253. 		_InOrder(root->_right);
    254. 	}
    255.  
    256. 	void RotateL(Node* parent)//左旋
    257. 	{
    258. 		Node* subR = parent->_right;
    259. 		Node* subRL = subR->_left;
    260.  
    261. 		parent->_right = subRL;
    262. 		if (subRL)
    263. 			subRL->_parent = parent;
    264.  
    265. 		Node* ppnode = parent->_parent;
    266.  
    267. 		subR->_left = parent;
    268. 		parent->_parent = subR;
    269.  
    270. 		if (ppnode == nullptr)
    271. 		{
    272. 			_root = subR;
    273. 			_root->_parent = nullptr;
    274. 		}
    275. 		else
    276. 		{
    277. 			if (ppnode->_left == parent)
    278. 			{
    279. 				ppnode->_left = subR;
    280. 			}
    281. 			else
    282. 			{
    283. 				ppnode->_right = subR;
    284. 			}
    285.  
    286. 			subR->_parent = ppnode;
    287. 		}
    288. 	}
    289.  
    290. 	void RotateR(Node* parent)//右旋
    291. 	{
    292. 		Node* subL = parent->_left;
    293. 		Node* subLR = subL->_right;
    294.  
    295. 		parent->_left = subLR;
    296. 		if (subLR)
    297. 			subLR->_parent = parent;
    298.  
    299. 		Node* ppnode = parent->_parent;
    300.  
    301. 		subL->_right = parent;
    302. 		parent->_parent = subL;
    303.  
    304. 		if (parent == _root)
    305. 		{
    306. 			_root = subL;
    307. 			_root->_parent = nullptr;
    308. 		}
    309. 		else
    310. 		{
    311. 			if (ppnode->_left == parent)
    312. 			{
    313. 				ppnode->_left = subL;
    314. 			}
    315. 			else
    316. 			{
    317. 				ppnode->_right = subL;
    318. 			}
    319. 			subL->_parent = ppnode;
    320. 		}
    321. 	}
    322.  
    323. private:
    324. 	Node* _root = nullptr;
    325. };
    326.  
    327. int main()
    328. {
    329. 	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    330. 	RBTree<int, int> t1;
    331. 	for (auto e : a)
    332. 	{
    333. 		t1.Insert(make_pair(e, e));
    334. 	}
    335.  
    336. 	t1.InOrder();//j检查打印出来的数据是否有序
    337. 	cout << endl << t1.IsRedB() << endl;
    338. 	return 0;
    339. }

             运行结果：

            从上面代码可以看出，检验一棵树是否为红黑树，从以下几个方面进行判断：函数IsRedB的作用是判断根结点是否为黑色，然后随便遍历一条路径，记录该路径下黑色节点的数量（规则5）。 

            接着把记录下来的黑色节点数量传给函数_check，并且让_check函数把所有路径下的黑色节点记录下来，一一的去跟之前记录好的数据进行对比，若有不相等的情况说明该树不是红黑树，另外_check函数内还进行了红色节点是否连续的判断（规则3）。

    结语

            以上就是关于红黑树的讲解，红黑树的重点还是在于了解红黑树的调整逻辑，理清叔叔节点和父母节点他们的位置关系，最核心的还是叔叔节点，他的存在与否，是红色还是黑色都影响最终的调整规律。最后希望本文可以给你带来更多的收获，如果本文对你起到了帮助，希望可以动动小指头帮忙点赞👍+关注😎+收藏👌！如果有遗漏或者有误的地方欢迎大家在评论区补充，谢谢大家！！

  • 相关阅读:
    H桥级联型五电平三相逆变器Simulink仿真模型
    java学习记录抽象类和接口
    一、基础知识(2)-凸集、凸函数
    使用PAM保障开发运营安全
    2023 最新前端面试题 （HTML 篇）
    IT外包驻场人员怎么定位自己的痛点？
    Qt天气预报系统之JSON
    我，拿着80万加盟零食很忙，找不到门面……
    js原型链以及实现继承的手段
    虚拟机下载与Ubuntu安装
  • 原文地址：https://blog.csdn.net/efls111/article/details/136431993