红黑树(C++实现)_红黑树存kv

红黑树的概念

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

红黑树的性质

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

上面的4点性质用自己的话可以总结为：(性质5不用记)

1.结点不是红色就是黑色
2.没有连续的红色结点
3.每条路径上的黑色结点的数量是一样的

AVL树是通过高度来控制平衡的，是严格平衡的。那如果新插入结点很多那么旋转也是要付出代价的。红黑树通过颜色来控制平衡，但不是严格的平衡，它近似平衡。红黑树也可以达到AVL树的效率。它最长路径不超过最短路径的2倍。

那为什么红黑树的最长路径不超过最短路径的2倍呢？

通过上面的性质，假设我们把红黑树的黑色结点单独抽出来，从跟到叶子黑结点个数为N个

那它最短路径就是长度为N
那它最长的路径可能是一黑一红

那它的长度为2N，所以它的最长路径不超过最短路径的2倍，则其他路径的长度就在N-2N之间。那么红黑树增删查改的效率就在logN-2logN之间，和AVL树的logN差不多了。

红黑树的结点定义

红黑树的结点定义还是跟AVL树一样，定义成三叉链结构和KV模型，不同的则是红黑树用枚举加入了颜色。

enum Color
{
	RED,
	BLACK
};
template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V> _left;//结点的左孩子
	RBTreeNode<K, V> _right;//结点的右孩子
	RBTreeNode<K, V> _parent;//结点的双亲
	pair<K, V>_kv;
	Color _color;//该结点的颜色
	RBTreeNode(const pair<K,V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_color(RED)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

红黑树的插入

那么我们插入结点时选择插入黑结点还是红结点呢？

当然是选择插入红结点了。选择插入黑结点那麻烦就大了，那1条路径上就多了1个黑结点，破坏了性质4，代价很大。插入红结点，如果它的父亲结点是黑色则不用调整，拍拍屁股走人，它的父亲是红色那我们在进行后序的处理。

总结一下：
1.插入黑色结点一定破坏性质4，调整起来会很麻烦
2.插入红结点不一定破坏红黑树的性质，它的父亲结点是红色才进行调整，比插入黑结点调整起来方便。

✨✨✨✨✨✨✨✨✨✨***我是分割线***✨✨✨✨✨✨✨✨✨✨✨✨✨✨

插入的逻辑：

1.找到插入结点的位置
2.插入结点
3.检测新结点插入后是否破坏了红黑的性质，如果破坏则需要进行处理

因为新插入结点的颜色是红色，若它的父亲结点是黑色不用调整，是红色的话需要对红黑树分情况来讨论。

红黑树调整主要看叔叔结点

下面我们根据叔叔结点的情况来具体看一下。

情况一

以下用p来代表parent结点，c代表cur为新增结点,g代表grandparent结点，u代表uncle结点。
我们还是跟AVL树一样画具象图：

1.叔叔结点存在且为红

为什么把g变成红色呢？如果g不变成红色，那此时子树上就多了1个黑结点了。
只要我们画出具象图，那面试时手撕红黑树也完全不怂。

当然还有很多种情况，那就给出抽象图：

这种情况下cur在p的左边还是右边都不影响。

情况二

叔叔结点存在且为黑，新增结点是p的左边

这是由情况一变来的，如果u存在那cur一定是黑的，不是新郑结点，这样才满足红黑树的性质。

✨✨✨✨✨✨✨✨✨✨***我是分割线***✨✨✨✨✨✨✨✨✨✨✨✨✨✨

新增结点是p的右边

情况三

叔叔结点不存在

新增结点在parent的左边

新增结点在parent的右边

总结一下：

以上的情况都是父亲结点在祖先结点的左边，在祖先结点的右边也是相同的处理方法
1.叔叔结点存在且为红，把父亲结点和叔叔结点变黑，祖先变红继续向上处理直到祖先是根节点
2.叔叔存在为黑，祖孙三代在一条直线上进行单旋，不在则进行双旋
3.叔叔不存在，祖孙三代在一条直线上进行单旋，不在则进行双旋
所以2,3的逻辑可以合在一起，分为新增结点在父亲结点的左边还是右边处理。

下面再来简单的说说父亲结点在祖先结点的右边

叔叔存在且为红

此时，cur在p的左边还是右边没有影响。

叔叔存在且为黑

新增结点在父亲结点的右边

新增结点在父亲结点的左边

叔叔不存在

总结一下：

1.叔叔存在且为红,u,p变黑，g变红继续向上调，直到g为根结点，最后把g变黑
2.叔叔存在且为黑，祖孙3带在一条直线上单旋，折线要双旋
3.叔叔不存在，祖孙3带在一条直线上单旋，折线要双旋

✨✨✨✨✨✨✨✨✨✨***我是分割线***✨✨✨✨✨✨✨✨✨✨✨✨✨✨

代码如下：

	pair<Node*, bool> insert(const pair<K, V>& kv)
	{
		//1.树为空
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_color = BLACK;//根结点为黑色
			return make_pair(_root, true);
		}
		//树不为空
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			//新结点key大于当前结点往右边
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			//新结点key小于当前结点往左边
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return make_pair(cur, false);
			}
		}
		cur = new Node(kv);
		Node* newnode = cur;
		newnode->_color = RED;
		if (parent->_kv.first < kv.first)
		{
			parent->_right = newnode;
			newnode->_parent = parent;
		}
		else
		{
			parent->_left = newnode;
			newnode->_parent = parent;
		}

		//开始调整颜色
		//父亲存在且为红
		while (parent && parent->_color == RED)
		{
			Node* grandParent = parent->_parent;		
			//parent是grandParent左孩子
			if (grandParent->_left == parent)
			{
				Node* uncle = grandParent->_right;
				//叔叔存在且为红色,父亲和叔叔都调为黑色
				//祖先调为红色，如果不调那每条路径的黑结点变了
				if (uncle && uncle->_color == RED)
				{
					parent->_color = BLACK;
					uncle->_color = BLACK;
					grandParent->_color = RED;
					//继续往上调
					cur = grandParent;
					parent = cur->_parent;
				}
				else//叔叔不存在或叔叔存在且为黑
				{
					if (parent->_left == cur)
					{    //右单旋
						RotateR(grandParent);
						parent->_color = BLACK;
						grandParent->_color = RED;
					}
					else //parent->_right == cur
					{
						RotateL(parent);
						RotateR(grandParent);
						grandParent->_color = RED;
						cur->_color = BLACK;
					}
					break;
				}
			}
			else //parent是grandParent左孩子
			{
				Node* uncle = grandParent->_left;
				if (uncle && uncle->_color == RED)
				{
					uncle->_color = BLACK;
					parent->_color = BLACK;
					grandParent->_color = RED;
					cur = grandParent;
					parent = cur->_parent;
				}
				else
				{
					if (parent->_right == cur)
					{
						RotateL(grandParent);
						parent->_color = BLACK;
						grandParent->_color = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandParent);
						cur->_color = BLACK;
						grandParent->_color = RED;
					}
					break;
				}	
			}
		}
		_root->_color = BLACK;
		return make_pair(newnode, true);
	}
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* parentParent = parent->_parent;
		//先旋转
		parent->_right = subRL;
		subR->_left = parent;

		parent->_parent = subR;
		//在改父亲结点
		if (subRL)
			subRL->_parent = parent;
		if (_root == parent)
		{
			_root = subR;
			_root->_parent = nullptr;
		}

		else
		{
			//subR旋转后可能是左右子树2种情况
			if (parentParent->_left == parent)
				parentParent->_left = subR;
			else
				parentParent->_right = subR;
			subR->_parent = parentParent;
		}
	}
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* parentParent = parent->_parent;//记录parent的父亲结点
		//subLR做parent->_left
		parent->_left = subLR;
		subL->_right = parent;
		//同时更新动的2个节点的parent
		//注意subLR还可能是空结点
		if (subLR)
			subLR->_parent = parent;
		parent->_parent = subL;
		//parent可能是单独的树，或者子树,分情况
		if (_root == parent)
		{
			_root = subL;
			_root->_parent = nullptr;
		}

		else
		{
			//还有可能parent是子树，可能是左子树
			if (parentParent->_left == parent)
				parentParent->_left = subL;
			else
				//也可能是右子树
				parentParent->_right = subL;
			//调整subL的父亲结点
			subL->_parent = parentParent;
		}
	}
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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177

红黑树的查找

查找跟AVL树的逻辑是一样的，博主这里就不做多的讲解了。

	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}

		return nullptr;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

红黑树的验证

先检查有没有连续的红结点，还有红结点的父亲结点是不是黑色。这就保证了没有连续的红结点。还有路径也要算。我们找1条路径作为参考，例如最左路径，只要有1条路径和它的黑结点数量不同就不是红黑树。

bool _CheckBlance(Node* root,int blackNum, int count)
	{
		if (root == nullptr)
		{
			if (count != blackNum)
			{
				cout << "黑色节点的数量不相等" << endl;
				return false;
			}

			return true;
		}

		if (root->_color == RED && root->_parent->_color == RED)
		{
			cout << "存在连续的红色节点" << endl;
			return false;
		}

		if (root->_color == BLACK)
		{
			count++;
		}

		return _CheckBlance(root->_left, blackNum, count)
			&& _CheckBlance(root->_right, blackNum, count);
	}

	bool CheckBlance()
	{
		if (_root == nullptr)
		{
			return true;
		}

		if (_root->_color == RED)
		{
			cout << "根节点是红色的" << endl;
			return false;
		}

		// 找最左路径做黑色节点数量参考值
		int blackNum = 0;
		Node* left = _root;
		while (left)
		{
			if (left->_color == BLACK)
			{
				blackNum++;
			}

			left = left->_left;
		}

		int count = 0;
		return _CheckBlance(_root, blackNum, count);
	}
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

我们来测试一下：

没有问题，博主也是调试了好长时间。一定要用好调试。

红黑树的和AVL树的比较

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

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】