1. 首页
  2. 文章中心
  3. C语言

C++ STL容器详解之红黑树部分模拟实现

160 阅读 0 评论
我是靠谱客的博主 多情学姐，这篇文章主要介绍C++ STL容器详解之红黑树部分模拟实现，现在分享给大家，希望可以做个参考。

一、红黑树的概念

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

二、红黑树的性质

1. 每个结点不是红色就是黑色；

2. 根节点是黑色的；

3. 如果一个节点是红色的，则它的两个孩子结点是黑色的；

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

5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)；

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

三、红黑树节点的定义

复制代码
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
enum Colour		//红黑树颜色枚举
{
	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;
 
	Colour _col;
 
	RBTreeNode(const pair<K, V>& kv)	//构造函数
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)
	{}
};

插入时默认为红色节点，因为红色可能会破坏规则3，黑色一定会破坏规则4，所以默认红色。

四、红黑树结构 

为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为跟节点必须为黑色，为了与根节点进行区分，将头结点给成黑色，并且让头结点的 parent 域指向红黑树的根节点，left域指向红黑树中最小的节点，right域指向红黑树中最大的节点，如下:

五、 红黑树的插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

1. 按照二叉搜索的树规则插入新节点：

复制代码
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
pair<Node*, bool> Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return make_pair(_root, true);
		}
 
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return make_pair(cur, false);
			}
		}
 
		Node* newNode = new Node(kv);
		newNode->_col = RED;
		if (parent->_kv.first > kv.first)
		{
			parent->_left = newNode;
			newNode->_parent = parent;
		}
		else
		{
			parent->_right = newNode;
			newNode->_parent = parent;
		}
		cur = newNode;
 
		while (parent && parent->_col == RED)		//违反规则三
		{
 
		}
 
		_root->_col = BLACK;		//插入结束再次将根变为黑
 
		return make_pair(cur, true);
	}

2. 检测新节点插入后，红黑树的性质是否造到破坏

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：

cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

情况一：cur为红，p为红，g为黑，u存在且为红

如果g是根节点，调整完成后，需要将g改为黑色，如果g是子树，g一定有父节点，且如果为红色呃，继续向上调整。

将p,u改为黑，g改为红，然后把g当成cur，继续向上调整 。

情况二: cur为红，p为红，g为黑，u不存在/u为黑

u的情况有两种：

1.如果u节点不存在，则cur一定是新插入节点，因为如果cur不是新插入节点，则cur和p一定有一个节点的颜色是黑色，就不满足性质4：每条路径黑色节点个数相同。

2.如果u节点存在，则其一定是黑色的，那么cur节点原来的颜色一定是黑色的，现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色。

p为g的左孩子，cur为p的左孩子，则进行右单旋转；

p为g的右孩子，cur为p的右孩子，则进行左单旋转。

p变黑，g变红。

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

需要进行双旋。

代码实现：

复制代码
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
while (parent && parent->_col == RED)		//违反规则三
		{
			Node* grandfather = parent->_parent;
 
			if (parent == grandfather->_left)			//左半边
			{
				Node* uncle = parent->_right;
 
				if (uncle && uncle->_col == red)		//情况一
				{
					uncle->_col = BLACK;
					grandfather->_col = RED;
					parent->_col = BLACK;
 
					cur = grandfather;			//迭代
					parent = cur->_parent;
				}
				else							//情况2.3
				{
					if (cur == parent->_left)		//单侧
					{
						RotateR(grandfather);
 
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else					//折
					{
						RotateL(parent);
						RotateR(grandfather);
 
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
 
					break;		//黑色数量无变化，不需要向上
				}
			}
			else         // parent == grandfather->_right
			{
				Node* uncle = parent->_left;
				if (uncle && uncle->_col == red)		//情况一
				{
					uncle->_col = BLACK;
					grandfather->_col = RED;
					parent->_col = BLACK;
 
					cur = grandfather;			//迭代
					parent = cur->_parent;
				}
				else							//情况2.3
				{
					if (cur == parent->_right)		//单侧
					{
						RotateL(grandfather);
 
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else					//折
					{
						RotateR(parent);
						RotateL(grandfather);
 
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
 
					break;
				}
			}
		}

六、代码

复制代码
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
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
#pragma once
#include<iostream>
#include<assert.h>
 
using namespace std;
 
enum Colour		//红黑树颜色枚举
{
	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;
 
	Colour _col;
 
	RBTreeNode(const pair<K, V>& kv)	//构造函数
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)
	{}
};
 
template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
private:
	Node* _root;
 
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* parentP = parent->_parent;
 
		if (subLR)							//左子树的右子树连接到父的右
			subLR->_parent = parent;
 
		parent->_left = subLR;
		subL->_right = parent;
		parent->_parent = subL;
 
		// 如果parent是根节点，根新指向根节点的指针
		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			// 如果parent是子树，可能是其双亲的左子树，也可能是右子树
			if (parentP->_left == parent)
				parentP->_left = subL;
			else
				parentP->_right = subL;
 
			subL->_parent = parentP;
		}
	}
 
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* parentP = parent->_parent;
 
		if (subRL)
			subRL->_parent = parent;
 
		parent->_right = subRL;
		subR->_left = parent;
		parent->_parent = subR;
 
		// 如果parent是根节点，根新指向根节点的指针
		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			// 如果parent是子树，可能是其双亲的左子树，也可能是右子树
			if (parentP->_left == parent)
				parentP->_left = subR;
			else
				parentP->_right = subR;
 
			subR->_parent = parentP;
		}
	}
 
	void _Destory(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
 
		_Destory(root->_left);
		_Destory(root->_right);
 
		delete root;
	}
 
public:
	RBTree()
		:_root(nullptr)
	{}
 
	~RBTree()
	{
		_Destory(_root);
		_root = nullptr;
	}
 
	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else if (cur->_kv < key)
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}
 
		return nullptr;
	}
 
	pair<Node*, bool> Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return make_pair(_root, true);
		}
 
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return make_pair(cur, false);
			}
		}
 
		Node* newNode = new Node(kv);
		newNode->_col = RED;
		if (parent->_kv.first > kv.first)
		{
			parent->_left = newNode;
			newNode->_parent = parent;
		}
		else
		{
			parent->_right = newNode;
			newNode->_parent = parent;
		}
		cur = newNode;
 
		while (parent && parent->_col == RED)		//违反规则三
		{
			Node* grandfather = parent->_parent;
 
			if (parent == grandfather->_left)			//左半边
			{
				Node* uncle = parent->_right;
 
				if (uncle && uncle->_col == red)		//情况一
				{
					uncle->_col = BLACK;
					grandfather->_col = RED;
					parent->_col = BLACK;
 
					cur = grandfather;			//迭代
					parent = cur->_parent;
				}
				else							//情况2.3
				{
					if (cur == parent->_left)		//单侧
					{
						RotateR(grandfather);
 
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else					//折
					{
						RotateL(parent);
						RotateR(grandfather);
 
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
 
					break;		//黑色数量无变化，不需要向上
				}
			}
			else         // parent == grandfather->_right
			{
				Node* uncle = parent->_left;
				if (uncle && uncle->_col == red)		//情况一
				{
					uncle->_col = BLACK;
					grandfather->_col = RED;
					parent->_col = BLACK;
 
					cur = grandfather;			//迭代
					parent = cur->_parent;
				}
				else							//情况2.3
				{
					if (cur == parent->_right)		//单侧
					{
						RotateL(grandfather);
 
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else					//折
					{
						RotateR(parent);
						RotateL(grandfather);
 
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
 
					break;
				}
			}
		}
 
		_root->_col = BLACK;		//插入结束再次将根变为黑
 
		return make_pair(newNode, true);
	}
};

总结

本文对红黑树进行了介绍，并对构造，插入，查找进行了模拟实现。

以上就是C++ STL容器详解之红黑树部分模拟实现的详细内容，更多关于C++ STL红黑树实现的资料请关注靠谱客其它相关文章！

最后

以上就是多情学姐最近收集整理的关于C++ STL容器详解之红黑树部分模拟实现的全部内容，更多相关C++ STL容器详解之红黑树部分模拟实现内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(106)

相关文章

C语言system函数使用方法详解
C语言system函数使用方法详解
C++解决合并两个排序的链表问题
C++解决合并两个排序的链表问题
VS2017开发C语言出现“no_init_all“的解决办法
VS2017开发C语言出现“no_init_all“的解决办法
C语言SetConsoleTextAttribute函数使用方法
C语言SetConsoleTextAttribute函数使用方法
C++ STL容器详解之红黑树部分模拟实现
C++ STL容器详解之红黑树部分模拟实现
C/C++ Qt 数据库QSql增删改查组件应用教程
C/C++ Qt 数据库QSql增删改查组件应用教程
C语言使用rand函数生成随机数
C语言使用rand函数生成随机数
C++中的编译与链接
C++中的编译与链接

评论列表共有 0 条评论

立即
投稿
返回
顶部