Cpp五条

这个屌丝很懒，什么也没留下！

热门标签

map，set底层数据结构红黑树

作者：Cpp五条 | 2024-04-09 15:12:14

踩

set底层数据结构

红黑树

- 红黑树的概念
- - 红黑树的性质
  - 红黑树的极端情况
用红黑树来封装map,set

红黑树的概念

①红黑树与AVL树一样都是平衡二叉搜索树
②通过从任一节点到其叶子节点的所有路径上都包含相同数目的黑节点的限制，确保没有一条路径会比其他路径长出俩倍，因而是接近平衡

红黑树的性质

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

红黑树的极端情况

针对第三点我们很容易想到两种极端情况

在这里插入图片描述

虽然是AVL时间复杂度的两倍但是在log函数面前2倍并不会很大，二者相差并不大
但AVL树为了保持严格的平衡，条件更加苛刻，代价大
综合来看红黑树更优一些

用红黑树来封装map,set

定义红黑树结点

enum Colour
{
	RED,
	BLACK,
};

//red-black node
template <class T>
struct RBTreeNode
{
	//三叉链
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	T _data;//结点储存的数据 map存储pair set存储Key
	Colour _col;//结点的颜色
	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _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
24

红黑树的迭代器

//反向迭代器
//迭代器的适配器
template<class Iterator>
struct ReverseIterator
{
	typedef typename Iterator::reference Ref;
	typedef typename Iterator::pointer Ptr;

	typedef ReverseIterator<Iterator> Self;

	Iterator _it;//储存的是正向迭代器

	ReverseIterator(Iterator it)
		:_it(it)
	{
	}

	Ref operator*()
	{
		return *_it;
	}

	Ptr operator->()
	{
		return _it.operator->();
	}

	Self& operator++()
	{
		--_it;
		return *this;
	}

	Self& operator--()
	{
		++_it;
		return *this;
	}
	bool operator!=(const Self& s)const
	{
		return _it != s._it;
	}
	bool operator==(const Self& s)const
	{
		return _it == s._it;
	}
};
//正向迭代器
	//结点储存的数据T  
template<class T, class Ref, class Ptr>
struct  _TreeIterator
{
	typedef Ref reference;
	typedef Ptr pointer;
	typedef RBTreeNode<T> Node;
	typedef _TreeIterator<T, Ref, Ptr> Self;

	Node* _node;//指向红黑树结点的指针

	_TreeIterator(Node* node)
		:_node(node)
	{

	}
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
	bool operator!=(const Self& s)const
	{
		return _node != s._node;
	}
	bool operator==(const Self& s)const
	{
		return _node == s._node;
	}
	//重点重载operator++ 根据中序遍历走
	Self& operator++()
	{
		//右节点存在 访问右树最左的结点
		if (_node->_right)
		{
			Node* left = _node->_right;
			while (left->_left)
			{
				left = left->_left;
			}
			_node = left;
		}
		//右节点不存在的情况,向上找
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;

			while (parent && cur == parent->_right)
			{
				//说明访问过了
				cur = cur->_parent;
				parent = parent->_parent;
			}
			//此时cur结点是parent的左
			_node = parent;
		}
		//如果是最后一个结点++，则返回nullpitr
		return *this;
	}
	//operator--()
	Self& operator--()
	{
		//左节点存在 访问左树最右结点
		if (_node->_left)
		{
			Node* right = _node->_left;
			while (right->_right)
			{
				right = right->_right;
			}
			_node = right;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{

				cur = cur->_parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		//end--返回空节点
		return *this;

	}
};
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

红黑树的插入操作

新插入红色结点更好：
插入红色结点，只可能破坏规则3,影响不大
插入黑色结点就会破坏非常关键的规则4，导致左最长路径可能不仅仅是2*log（N）破坏了平衡

预备知识：旋转

1.单旋（以右单旋为例）
大致思路：
①先保存parent的父结点
②让subLR作parent的左
③parent作subL的右
④parent的父节点作subL的parent
在这里插入图片描述

//右单旋
void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		//判断subLR是否存在
		if (subLR)
			subLR->_parent = parent;

		subL->_right = parent;
		Node* parentParent = parent->_parent;
		parent->_parent = subL;
		
		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
				parentParent->_left = subL;
			else
				parentParent->_right = 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

2.双旋（以左右双旋为例）
大致思路：
①先对subL左旋
②再对parent右旋
在这里插入图片描述

插入

①插入的结点的parent为黑色：不需要调整，直接插入
②插入的结点的parent是红色：违反规则3，需要调整（关键看Uncle）

1.cur为红，p为红，g为黑，u存在且为红（不分方向）
调整方法：将parent跟uncle变黑，grandfather变红，并且向上检查grandfather的父亲，继续向上调整
在这里插入图片描述
此时，cur为红色，为了保持规则3，parent必须变黑，这样左子树增加了一个黑结点，右子树uncle就需要变黑，grandfather就必须变红来保持该子树黑结点数目不变

2.cur为红，p为红，g为黑，u为黑或不存在

调整方法：有两种情况，如果两个红结点不是一条直线就需要双旋，如果是就需要单旋，与AVL树类似

讨论在左边的情况：

在这里插入图片描述

在这里插入图片描述
代码：

pair<iterator, bool> Insert(const T& data)
	{
		//如果是空树
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(iterator(_root), true);
		}
		//仿函数 转化结点储存的T map转化成pair的first set转化成key
		KeyofT kot;
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (kot(cur->_data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return make_pair(iterator(cur), false);
			}
		}
		Node* newnode = new Node(data);
		if (kot(parent->_data) > kot(data))
		{
			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 = grandfather->_right;
				//uncle跟parent为红
				if (uncle&& uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;
					//继续向上处理
					cur = grandfather;
					parent = cur->_parent;

				}
				else//uncle存在且为黑或者不存在
				{
					//右单旋情况
					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//右边情况
			{
				Node* uncle = grandfather->_left;

				if (uncle&& uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;
					//继续向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				//uncle存在且为黑，或者不存在
				else
				{	//左单旋
					if (parent->_right == cur)
					{
						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(iterator(newnode), true);
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}
		subR->_left = parent;
		Node* grandparent = parent->_parent;
		parent->_parent = subR;
		if (parent == _root)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (grandparent->_left == parent)
			{
				grandparent->_left = subR;
			}
			else
			{
				grandparent->_right = subR;
			}
			subR->_parent = grandparent;
		}

	}
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		subL->_right = parent;
		Node* parentParent = parent->_parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
				parentParent->_left = subL;
			else
				parentParent->_right = 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
178
179
180

模拟实现红黑树的代码

		//比较的key //结点储存的  //仿函数用于转化T为key
template<class K, class T, class KeyofT>
class RBTree
{
	typedef RBTreeNode<T> Node;
	typedef _TreeIterator<T, T&, T*> iterator;
	typedef _TreeIterator<T, const T&, const T*> const_iterator;
	typedef ReverseIterator<iterator> reverse_iterator;
public:
	//反向迭代器
	reverse_iterator rbegin()
	{
		//最右结点
		Node* right = _root;
		while (right && right->_right)
		{
			right = right->_right;
		}
		return reverse_iterator(iterator(right));//反向迭代器中储存正向迭代器
		//实现正向迭代器代码的复用
	}
	reverse_iterator rend()
	{
		return reverse_iterator(iterator(nullptr));
	}
	//最左结点
	iterator begin()
	{
		Node* left = _root;
		while (left && left->_left)
		{
			left = left->_left;
		}
		return iterator(left);//匿名对象
	}
	iterator end()
	{
		return iterator(nullptr);
	}

	RBTree()
		:_root(nullptr)
	{}

	//拷贝构造，operator=

	Node* Find(const K& key)
	{
		KeyofT kot;
		Node* cur = _root;
		while (cur)
		{
			if (kot(cur->_data) > key)
			{
				cur = cur->_left;
			}
			else if (kot(cur->_data) < key)
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

	pair<iterator, bool> Insert(const T& data)
	{
		//如果是空树
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(iterator(_root), true);
		}
		//仿函数 转化结点储存的T map转化成pair的first set转化成key
		KeyofT kot;
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (kot(cur->_data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return make_pair(iterator(cur), false);
			}
		}
		Node* newnode = new Node(data);
		if (kot(parent->_data) > kot(data))
		{
			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 = grandfather->_right;
				//uncle跟parent为红
				if (uncle&& uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;
					//继续向上处理
					cur = grandfather;
					parent = cur->_parent;

				}
				else//uncle存在且为黑或者不存在
				{
					//右单旋情况
					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//右边情况
			{
				Node* uncle = grandfather->_left;

				if (uncle&& uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;
					//继续向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				//uncle存在且为黑，或者不存在
				else
				{	//左单旋
					if (parent->_right == cur)
					{
						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(iterator(newnode), true);
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}
		subR->_left = parent;
		Node* grandparent = parent->_parent;
		parent->_parent = subR;
		if (parent == _root)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (grandparent->_left == parent)
			{
				grandparent->_left = subR;
			}
			else
			{
				grandparent->_right = subR;
			}
			subR->_parent = grandparent;
		}

	}
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		subL->_right = parent;
		Node* parentParent = parent->_parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
				parentParent->_left = subL;
			else
				parentParent->_right = subL;

			subL->_parent = parentParent;
		}

	}
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}
		subR->_left = parent;
		Node* grandparent = parent->_parent;
		parent->_parent = subR;
		if (parent == _root)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (grandparent->_left == parent)
			{
				grandparent->_left = subR;
			}
			else
			{
				grandparent->_right = subR;
			}
			subR->_parent = grandparent;
		}

	}

	void Destory(Node* root)
	{
		if (root == nullptr)
			return;
		Destory(root->_left);
		Destory(root->_right);
		delete root;
	}
	~RBTree()
	{
		Destory(_root);
		_root = nullptr;
	}
private:
	Node* _root;
};
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
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296

封装set

set的底层就是红黑树，所以我们直接用上面的红黑树封装set

//set是K搜索模型
namespace tzc
{
	            //key   //结点储存的值T
	template<class K>
	class set
	{
		//set仿函数
		struct SetKeyofT
		{
						//结点储存的是key直接返回
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		//加typename是因为此时RBTree还没有实例化,所以告诉编译器这是一个类型，等实例化后再去找
		typedef typename RBTree<K, K, SetKeyofT>::iterator iterator;
		typedef typename RBTree<K, K, SetKeyofT>::reverse_iterator reverse_iterator;
		//反向的迭代器
		reverse_iterator rbegin()
		{
			return _t.rbegin();
		}
		reverse_iterator rend()
		{
			return _t.rend;
		}
		//正向迭代器
		iterator begin()
		{
			return _t.begin();
		}
		iterator end()
		{
			return _t.end();
		}
		
		pair<iterator, bool> insert(const K& k)
		{
			return _t.Insert(k);
		}
		
	private:
		RBTree<K, K, SetKeyofT> _t;//红黑树
	};

}
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

封装map

map是KV结构
比set多了一个重载[]

namespace tzc
{
	template<class K, class V>
	class map
	{
		//仿函数
		struct MapKeyofT
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;//结点储存的是pair，返回其first
			}
		};
	public:
		typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::iterator iterator;
		typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::reverse_iterator reverse_iterator;
		//反向迭代器
		reverse_iterator rbegin()
		{
			return _t.rbegin();
		}

		reverse_iterator rend()
		{
			return _t.rend();
		}
		
		iterator begin()
		{
			return _t.begin();
		}
		iterator end()
		{
			return _t.end();
		}
		
		pair<iterator, bool> insert(const pair<const K, V>& kv)
		{
			return _t.Insert(kv);
		}
		//最为关键的重载了[]
		//multimap并没有重载
		V& operator[](const K& key)
		{
			//无论插入成功或失败都会返回该结点的pair<iterator,bool>
			pair<iterator, bool> ret = insert(make_pair(key, V()));
			return ret.first->second;//返回该结点V的引用
		}

	private:
		RBTree<K, pair<const K, V>, MapKeyofT> _t;
	};
}
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

map、set设计的巧妙之处

设计地巧妙在于让map和set都复用了红黑树的代码
通过控制结点储存的值不同，传给红黑树的仿函数等不同来实现

在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/393570