【C++】红黑树插入操作实现以及验证红黑树是否正确

🌏博客主页： 主页
🔖系列专栏： C++
❤️感谢大家点赞👍收藏⭐评论✍️
😍期待与大家一起进步！

---

---

前言

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

红黑树的性质：

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

一、红黑树的插入操作

1.红黑树结点的定义

enum Color {
	RED,
	BLACK
};
template<class K,class V>
struct RBTreeNode {
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	pair<K, V>_kv;
	Color _col;//颜色

	RBTreeNode(const pair<K,V>&kv)
		:_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_kv(kv),
		_col(RED)
		//结点默认给成红色是为了方便后续的插入
		//因为默认为黑色的话还需要考虑所有路径上黑色结点数量是否相同
		//太麻烦了
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.红黑树的插入

插入分为一下三种情况，因为我们插入的结点默认为红色，而红黑树定义中指出不能出现连续的两个红色结点，为了维持红黑树，我们需要对一些结点的颜色进行改变有时还需要旋转改变树的形状，至于有关旋转的函数Rotate，我已经在之前AVL树的模拟实现中详细说明了，这里就不多在赘述了【C++】AVL树的插入操作实现以及验证是否正确（带平衡因子），有需要的可以去看一下。

1.uncle存在且为红

这种情况就不需要考虑旋转了

2.uncle不存在

3.uncle存在且为黑

总结：
红黑树插入关键看uncle
1.uncle存在且为红，变色（uncle与parent变黑色，grandfather变红色），之后继续向上处理
2.uncle不存在或者uncle存在且为黑，旋转加变色，之后break
3.小规律：grandfather在这个过程中要不本来就为红色，要不就变成红色

3.完整代码

template<class K,class V>
class RBTree {
	typedef RBTreeNode<K,V> Node;
public:
	bool Insert(const pair<K, V>& kv) {
		if (_root == nullptr) {
			//根节点必须为黑色
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur) {//寻找插入位置
			if (cur->_kv.first < kv.first) {
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first) {
				parent = cur;
				cur = cur->_left;
			}
			else {
				return false;
			}
		}
		cur = new Node(kv);
		cur->_col = RED;
		//插入对应位置，默认为红色
		if (parent->_kv.first < kv.first) {
			parent->_right = cur;
		}
		else {
			parent->_left = cur;
		}
		cur->_parent = parent;
		//让新插入结点指向父亲

		while (parent && parent->_col == RED) {
			Node* grandfather = parent->_parent;
			if (parent = grandfather->_left) {
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED) {//uncle存在且为红
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					//继续向上更新
					cur = grandfather;
					parent = cur->_parent;
				}
				else {//uncle不存在或者uncle为黑
					if (cur == parent->_left) {
						//     g
						//   p
						// c
						RotateR(grandfather);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else {
						//     g
						//   p
						//		c
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;

					}
					break;
				}
			}
			else {// parent == grandfather->_right
				Node* uncle = grandfather->_right;
					if (uncle && uncle->_col == RED) {//uncle存在且为红
						parent->_col = uncle->_col = BLACK;
						grandfather->_col = RED;
						//继续向上更新
						cur = grandfather;
						parent = cur->_parent;

					}
					else {//uncle不存在或者uncle为黑
						if (cur == parent->_right) {
							// g
						   //	  p
						   //       c
							RotateL(grandfather);
							parent->_col = BLACK;
							grandfather->_col = RED;
						}
						else {
							// g
							//	  p
							// c
							RotateR(parent);
							RotateL(grandfather);
							cur->_col = BLACK;
							grandfather->_col = RED;
						}
						break;
					}
			}
		}
		_root->_col = BLACK;
			//根节点必须为黑色
		return true;
	}

	void RotateL(Node* parent) {//左旋
		Node* cur = parent->_right;
		Node* curleft = cur->_left;
		parent->_right = curleft;
		if (curleft) {
			curleft->_parent = parent;
		}
		cur->_left = parent;
		Node* ppnode = parent->_parent;
		if (ppnode == nullptr) {
			_root = cur;
			cur->_parent = nullptr;
		}
		else {
			if (ppnode->_left = parent) {
				ppnode->_left = cur;
			}
			else {
				ppnode->_right = cur;
			}
			cur->_parent = ppnode;
		}

	}

	void RotateR(Node* parent) {//右旋
		Node* cur = parent->_left;
		Node* curright = cur->_right;
		parent->_left = curright;
		if (curright) {
			curright->_parent = parent;
		}
		cur->_right = parent;
		Node* ppnode = parent->_parent;
		parent->_parent = cur;
		if (ppnode == nullptr) {
			_root = cur;
			cur->_parent = nullptr;
		}
		else {
			if (ppnode->_left == parent) {
				ppnode->_left = cur;
			}
			else {
				ppnode->_right = cur;
			}
			cur->_parent = ppnode;
		}
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

二、是否为红黑树的验证

1.IsBlance函数

bool IsBalance() {
		return IsBalance(_root);
	}
	bool IsBalance(Node* root) {
		if (root == nullptr) {
			return true;
		}
		if (root->_col != BLACK) {
			return false;
		}//根节点一定为黑色
		int benchmark = 0;
		Node* cur = _root;
		while (cur) {//算出最左边黑色结点的数目，为了与
			//其他路径黑色结点的数目作比较
			if (cur->_col == BLACK) {
				benchmark++;
			}
			cur = cur->_left;
		}
		return CheckColor(root, 0, benchmark);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.CheckColor函数

bool CheckColor(Node* root, int blacknum, int benchmark) {
		if (root == nullptr) {
			//root为空说明已经数完了一条路径的黑色结点
			//与原先数的最左的黑色节点数进行比较
			if (blacknum != benchmark) {
				return false;
			}
			return true;
		}
		if (root->_col == BLACK) {
			blacknum++;//当前路径黑色结点树++
		}
		if (root->_col == RED && root->_parent && root->_parent->_col == RED) {
			cout << root->_kv.first << "出现连续红色节点" << endl;
			//判断是否出现连续的红色结点
			return false;
		}
		//递归式对左右子树分别检验
		return CheckColor(root->_left, blacknum, benchmark) && CheckColor(root->_right, blacknum, benchmark);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

三、红黑树与AVL树的比较

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