C++ 改造红黑树,封装map和set

一.前言:已经实现好了的红黑树

set是Key模型的红黑树
map是Key-Value模型的红黑树
我们之前已经把红黑树实现并测试过了
这是Key-Value模型的红黑树
RBTree.h

#pragma once
enum Color
{
	RED,
	BLACK
};

template<class K,class V>
struct RBTreeNode
{
	RBTreeNode<K,V>* _pLeft;
	RBTreeNode<K,V>* _pRight;
	RBTreeNode<K,V>* _pParent;
	Color _color;
	pair<K,V> _data;
	//新插入的节点默认是红色
	RBTreeNode(const pair<K,V>& data)
		:_pLeft(nullptr)
		,_pRight(nullptr)
		,_pParent(nullptr)
		,_color(RED)
		,_data(data)
	{}
};

template<class K,class V>
class RBTree
{
	typedef RBTreeNode<K,V> Node;
public:

	// 在红黑树中插入值为data的节点，插入成功返回true，否则返回false
	// 注意：为了简单起见，本次实现红黑树不存储重复性元素
	bool Insert(const pair<K,V>& data)
	{
		if (_pRoot == nullptr)
		{
			_pRoot = new Node(data);
			//根节点是黑色
			_pRoot->_color = BLACK;
			return true;
		}
		Node* cur = _pRoot, * parent = nullptr;
		while (cur)
		{
			//比我小,往左找
			if (data.first < cur->_data.first)
			{
				parent = cur;
				cur = cur->_pLeft;
			}
			//比我大,往右找
			else if (data.first > cur->_data.first)
			{
				parent = cur;
				cur = cur->_pRight;
			}
			//有重复元素,插入失败
			else
			{
				return false;
			}
		}
		//找到空位置,开始插入
		cur = new Node(data);
		//连接父亲和孩子
		if (cur->_data.first < parent->_data.first)
		{
			parent->_pLeft = cur;
		}
		else
		{
			parent->_pRight = cur;
		}
		cur->_pParent = parent;
		//父亲是黑色,插入成功
		if (parent->_color == BLACK)
		{
			return true;
		}
		//父亲是红色,需要调整
		//且此时爷爷一定是黑色
		//根据叔叔的颜色来调整
		while (parent && parent->_color == RED)
		{
			Node* grandParent = parent->_pParent;
			//爸爸是爷爷的左孩子
			if (parent == grandParent->_pLeft)
			{
				Node* uncle = grandParent->_pRight;
				//根据叔叔的颜色来调整
				//1.叔叔存在且为红
				if (uncle && uncle->_color == RED)
				{
					//修改爸爸,叔叔,爷爷的颜色
					uncle->_color = parent->_color = BLACK;
					grandParent->_color = RED;
					//此时视爷爷为新插入的红色节点继续向上影响
					cur = grandParent;
					parent = cur->_pParent;
				}
				//2.叔叔不存在或者叔叔是黑
				else
				{
					//1.我是爸爸的左孩子
					if (parent->_pLeft == cur)
					{
						//对爷爷进行一次右旋
						RotateR(grandParent);
						//把爷爷改成红色,爸爸改成黑色
						grandParent->_color = RED;
						parent->_color = BLACK;
						//此时爸爸是黑色,无需break,当然break也可以,因此爸爸是黑色,下次循环就不会进入了
					}
					//2.我是爸爸的右孩子
					else
					{
						//1.对爸爸进行左旋
						RotateL(parent);
						//2.对爷爷右旋
						RotateR(grandParent);
						//3.孩子改成黑色,爷爷改成红色
						cur->_color = BLACK;
						grandParent->_color = RED;
						//4.一定要break,如果不break的话,因为爸爸是红色,所以循环会继续,此时就乱套了
						break;
					}
				}
			}
			//爸爸是爷爷的右孩子
			else
			{
				Node* uncle = grandParent->_pLeft;
				//1.叔叔存在且为红
				if (uncle && uncle->_color == RED)
				{
					uncle->_color = parent->_color = BLACK;
					grandParent->_color = RED;
					cur = grandParent;
					parent = cur->_pParent;
				}
				//2.叔叔不存在或者叔叔为黑
				else
				{
					//1.我是爸爸的右孩子
					if (parent->_pRight == cur)
					{
						//对爷爷左旋
						RotateL(grandParent);
						//爷爷改成红色,爸爸改成黑色
						grandParent->_color = RED;
						parent->_color = BLACK;
						//此时爸爸是黑色,无需break,当然break也可以,因此爸爸是黑色,下次循环就不会进入了
					}
					//2.我是爸爸的左孩子
					else
					{
						//1.对爸爸右旋
						RotateR(parent);
						//2.对爷爷左旋
						RotateL(grandParent);
						//3.把孩子改成黑色,爷爷改成红色
						cur->_color = BLACK;
						grandParent->_color = RED;
						//4.一定要break,如果不break的话,因为爸爸是红色,所以循环会继续,此时就乱套了
						break;
					}
				}
			}
		}
		_pRoot->_color = BLACK;
		return true;
	}

	// 检测红黑树中是否存在关键字为key的节点，存在返回该节点的地址，否则返回nullptr
	Node* Find(const K& key)
	{
		Node* cur = _pRoot;
		while (cur)
		{
			if (cur->_data.first > key)
			{
				cur = cur->_pLeft;
			}
			else if (cur->_data.second < key)
			{
				cur = cur->_pRight;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

	// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测
	bool IsValidRBTRee()
	{
		//1.空树是红黑树
		if (_pRoot == nullptr)
		{
			return true;
		}
		//2.根节点不能为红色
		if (_pRoot->_color == RED)
		{
			return false;
		}
		//3.为了验证性质: 红黑树的任意一条路径上的黑色节点个数相同   找参考值
		size_t ReferenceCount = 0;
		Node* cur = _pRoot;
		while (cur)
		{
			if (cur->_color == BLACK)
			{
				ReferenceCount++;
			}
			cur = cur->_pLeft;
		}
		return _IsValidRBTRee(_pRoot, 0, ReferenceCount);
	}

	void InOrder()
	{
		_InOrder(_pRoot);
	}
private:
	bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t& ReferenceCount)
	{
		if (pRoot == nullptr)
		{
			if (blackCount != ReferenceCount)
			{
				cout << "存在黑色节点数量不相等的路径" << endl;
				return false;
			}
			return true;
		}
		//验证性质: 红黑树中不能存在连续的红色节点
		//如果一个节点是红色,该节点一定不是根节点,因此该节点一定有父亲
		//只需要保证红色节点的父亲不是红色节点即可
		if (pRoot->_color == RED)
		{
			if (pRoot->_pParent->_color == RED)
			{
				cout << "存在连续的红色节点" << endl;
				return false;
			}
		}
		else
		{
			blackCount++;
		}
		return _IsValidRBTRee(pRoot->_pLeft, blackCount, ReferenceCount) && _IsValidRBTRee(pRoot->_pRight, blackCount, ReferenceCount);
	}

	// 右单旋
	void RotateR(Node* pParent)
	{
		Node* subL = pParent->_pLeft;
		Node* subLR = subL->_pRight;
		Node* grandParent = pParent->_pParent;
		subL->_pRight = pParent;
		pParent->_pParent = subL;
		pParent->_pLeft = subLR;
		if (subLR)
			subLR->_pParent = pParent;
		if (grandParent == nullptr)
		{
			_pRoot = subL;
			_pRoot->_pParent = nullptr;
		}
		else
		{
			if (pParent == grandParent->_pLeft)
			{
				grandParent->_pLeft = subL;
			}
			else
			{
				grandParent->_pRight = subL;
			}
			subL->_pParent = grandParent;
		}
	}

	// 左单旋
	void RotateL(Node* pParent)
	{
		Node* subR = pParent->_pRight;
		Node* subRL = subR->_pLeft;
		Node* grandParent = pParent->_pParent;
		pParent->_pParent = subR;
		subR->_pLeft = pParent;
		pParent->_pRight = subRL;
		if (subRL)
			subRL->_pParent = pParent;
		//说明此时pParent是_pRoot
		if (grandParent == nullptr)
		{
			_pRoot = subR;
			_pRoot->_pParent = nullptr;
		}
		//说明此时pParent所在的树是一颗子树,需要跟父亲链接
		else
		{
			if (pParent == grandParent->_pLeft)
			{
				grandParent->_pLeft = subR;
			}
			else
			{
				grandParent->_pRight = subR;
			}
			subR->_pParent = grandParent;
		}
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr) return;
		_InOrder(root->_pLeft);
		cout << root->_data.first << " " << root->_data.second << " ";
		_InOrder(root->_pRight);
	}
private:
	Node* _pRoot = nullptr;
};
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
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329

要想用红黑树来封装set和map,我们首先想到的是在搞一份Key模型的红黑树,
然后用Key模型红黑树来封装set,Key-Value模型红黑树封装map
但是STL库中set和map的设计却不是这样的
它们都是只用了一份红黑树,怎么做到的呢?
下面就让我们来探索一下

二.简化STL库里面对于map和set的封装

红黑树的源码:是一个KV模型的红黑树
它是通过传入的Value的值来判断类型,利用模板的技术实现的一棵泛型的红黑树
通过模板的实例化,实现了map和set

1.STL库中红黑树的简化代码

我们挑选出一部分很重要的成员来看看STL库中的红黑树是怎么个泛型法呢?

2.STL库中set的简化代码

下面我们看一下set

3.STL库中map的简化代码

下面我们看一下map

4.封装map和set的第一步

RBTree.h

template<class K, class V>
class RBTree
1
2

对于V这个模板参数:
可能是键值Key,也可能是由Key和Value共同组成的键值对pair

MySet.h
对于set而言,传入底层红黑树的模板参数就是Key和Key

template<class K>
class set
{
private:
	RBTree<K, K> _root;
};
1
2
3
4
5
6

MyMap.h
对于map而言,传入底层红黑树的模板参数就是Key和pair<const Key,Value>

template<class K, class V>
class map
{
private:
	//我们知道:map的Key不允许被修改,Value允许被修改
	//因此pair里面的K加上const修饰
	RBTree<K, pair<const K, V>> _root;
};
1
2
3
4
5
6
7
8

5.红黑树第一个模板参数的价值

通过上面的传参,我们可以知道:
只需要对于红黑树的第二个模板参数传入不同的值就可以对set和map进行很好地区分
那么红黑树的第一个模板参数是不是就没有用了呢?

对于insert(const Value& v)来说,是这样的,因为插入的值就是value
set的value是key,map的value是pair

但是对于find(const Key& k)来说,查找的依据是key,对于set是可以的
但是对于map来说,它的value是一个键值对,而我们是需要key来查找的,因此第一个模板参数不能不要

6.红黑树节点的定义

enum Color
{
	RED,
	BLACK
};
template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _pLeft;
	RBTreeNode<T>* _pRight;
	RBTreeNode<T>* _pParent;
	Color _color;
	T _data;
	//新插入的节点默认是红色
	RBTreeNode(const T& data)
		:_pLeft(nullptr)
		, _pRight(nullptr)
		, _pParent(nullptr)
		, _color(RED)
		, _data(data)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

三.仿函数

1.解除仿函数的误解

在学习优先级队列的时候我们遇到了仿函数
当时我们写了一个greater的仿函数,传入greater就能建小堆
传入less就能建大堆

当时我们知道:仿函数是一个类,主要重载operator()
不过仿函数不仅仅可以用于比较大小,这是我们常有的一大误解

2.仿函数在这里的价值

由于红黑树不知道传的是set还是map
因此在insert时进行节点键值的比较时,底层红黑树需要使用仿函数来获取键值key,从而才能进行比较

3.set的仿函数

对set而言,仿函数就是返回Key

template<class K>
class set
{
public:
	struct SetKeyofT
	{
		const K& operator()(const K& k)
		{
			return k;
		}
	};
private:
	RBTree<K, K,SetKeyofT> _root;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4.map的仿函数

对map而言,仿函数就是返回pair的first,也就是Key

template<class K, class V>
class map
{
public:
	struct MapKeyofT
	{
		const K& operator()(const pair<const K, V>& kv)
		{
			return kv.first;
		}
	};
private:
	//我们知道:map的Key不允许被修改,Value允许被修改
	//因此pair里面的K加上const修饰
	RBTree<K, pair<const K, V>,MapKeyofT> _root;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5.红黑树的修改

修改之后,因为红黑树的代码太长了,所以这里只列出修改的地方
1.类模板

template<class K, class V,class KeyofT>
1

2.成员变量

private:
		Node* _pRoot = nullptr;
		KeyofT _kot;
1
2
3

3.insert插入时的比较逻辑

//1 参数只需要传V即可(也就是红黑树的第二个模板参数)
//对于set而言V就是Key
//对于map而言,V就是pair<K,V>
bool Insert(const V& data)
{
	if (_pRoot == nullptr)
	{
		_pRoot = new Node(data);
		//根节点是黑色
		_pRoot->_color = BLACK;
		return true;
	}
	Node* cur = _pRoot, * parent = nullptr;
	while (cur)
	{
		//比我小,往左找
		if (_kot(data) < _kot(cur->_data))
		{
			parent = cur;
			cur = cur->_pLeft;
		}
		//比我大,往右找
		else if (_kot(data) > _kot(cur->_data))
		{
			parent = cur;
			cur = cur->_pRight;
		}
		//有重复元素,插入失败
		else
		{
			return false;
		}
	}
	//找到空位置,开始插入
	cur = new Node(data);
	//连接父亲和孩子
	if (_kot(cur->_data) < _kot(parent->_data))
	{
		parent->_pLeft = cur;
	}
	//..旋转变色等其他操作,这些操作都无需进行节点的Key有关比较
}
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

6.仿函数小总结

四.迭代器

1.迭代器类的定义

跟list类似,红黑树的正向迭代器也是对节点指针进行了一层封装
同样的,为了实现const_iterator,这里传入Ref和Ptr这两个模板参数

不过这里增加了const迭代器和非const迭代器的转化

template<class T, class Ref, class Ptr>
struct __TreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef __TreeIterator<T, T&, T*> iterator;
	typedef __TreeIterator<T, Ref, Ptr> Self;
	Node* _node;

	__TreeIterator(Node* node)
		:_node(node)
	{}

	//普通迭代器和const_iterator的转化
	__TreeIterator(const iterator& it)
		:_node(it._node)
	{}
	
	Ref operator*();

	Ptr operator->();

	//找中序遍历的下一个节点
	Self& operator++();

	bool operator!=(const Self& s);

	bool operator==(const Self& s);
};
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

2.解引用,!=,==的实现

Ref operator*()
{
	return _node->_data;
}

Ptr operator->()
{
	return &_node->_data;
}

bool operator!=(const Self& s)
{
	return _node != s._node;
}

bool operator==(const Self& s)
{
	return _node == s._node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3.operator++

这里的迭代器走的是二叉树的中序遍历,因此++要找到中序遍历的下一个节点
如何找呢?
1.如果节点的右子树不为空,中序的下一个节点就是右子树的最左节点
2.如果节点的右子树为空,那么就需要一直往上找
直到父亲为空或者孩子是父亲的左孩子时,此时的父亲就是中序的下一个节点

//找中序遍历的下一个节点
Self& operator++()
{
	//1.左子树 根节点 右子树
	//如果有右孩子,那就是右子树的最左节点
	//如果没有右孩子,那往上找直到我是父亲的左孩子或者我的父亲是空节点为止,此时我的父亲就是下一个节点
	Node* cur = _node;
	if (cur->_pRight)
	{
		Node* right = cur->_pRight;
		while (right->_pLeft)
		{
			right = right->_pLeft;
		}
		_node = right;
	}
	else
	{
		Node* parent = cur->_pParent;
		while (parent && parent->_pRight == cur)
		{
			cur = parent;
			parent = cur->_pParent;
		}
		_node = parent;
	}
	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

4.给红黑树加上begin和end

begin是中序的第一个节点,也就是最左节点
end是中序的最后一个节点的下一个节点,也就是空节点

跟list一样,普通迭代器就是V V& V*
const_iterator就是V const V& const V*

template<class K, class V,class KeyofT>
class RBTree
{
	typedef RBTreeNode<V> Node;
public:

	typedef __TreeIterator<V, V&, V*> iterator;

	typedef __TreeIterator<V,const V&,const V*> const_iterator;

	iterator begin()
	{
		Node* cur = _pRoot;
		while (cur && cur->_pLeft)
		{
			cur = cur->_pLeft;
		}
		return iterator(cur);
	}

	iterator end()
	{
		return iterator(nullptr);
	}

	const_iterator begin() const
	{
		Node* cur = _pRoot;
		while (cur && cur->_pLeft)
		{
			cur = cur->_pLeft;
		}
		return const_iterator(cur);
	}

	const_iterator end() const
	{
		return const_iterator(nullptr);
	}
	//其他成员....
};
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

五.set的实现

1.注意

1.typename

直接复用红黑树的接口即可实现set
注意:

typedef typename RBTree<K, K, SetKeyofT>::const_iterator iterator;
1

typename的作用:因为没有实例化的模板是区分不了静态变量和类型的,因此需要我们使用typename告诉编译器这是类型

2.set的特性

库里面的set是不允许修改里面的值的
也就是说set的普通迭代器和const迭代器其实都是const迭代器
因此都复用红黑树的const_iterator即可

2.set的代码

namespace wzs
{
	template<class K>
	class set
	{
	public:
		struct SetKeyofT
		{
			const K& operator()(const K& k)
			{
				return k;
			}
		};
		typedef typename RBTree<K, K, SetKeyofT>::const_iterator iterator;

		typedef typename RBTree<K, K, SetKeyofT>::const_iterator const_iterator;

		iterator begin() const
		{
			return _root.begin();
		}
		iterator end() const
		{
			return _root.end();
		}
		pair<iterator, bool> insert(const K& k)
		{
			return _root.Insert(k);
		}
	private:
		RBTree<K, K, SetKeyofT> _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

六.map的实现

1.operator[]的说明

STL库里面的map容器的方括号[]的作用:

返回值:
插入成功:pair<新插入的key所在的节点的iterator,true>
插入失败:pair<已经存在的key所在的节点的iterator,false>

作用:
如果插入成功,那么operator[]相当于insert
如果插入失败,那么operator[]相当于find

也就是说operator[]有多重技能
operator[]是map的一个非常重要的函数,可以实现3个功能:插入,查找,修改
1
2
3
4
5
6
7
8
9
10

这是对源码的一个简化:

operator[]:给一个key,返回这个key所对应的value的引用
简化前:
mapped_type& operator[](const Key_type& k)
{
   return (*(this->insert(make_pair(k,mapped_type())))).first).second;
}

简化后
V& operator(const K& key)
{
   pair<iterator,bool> ret=insert(key,V());//V():value的默认构造的匿名对象
   return ret.first->second;
1
2
3
4
5
6
7
8
9
10
11
12

2.map的代码

namespace wzs
{
	template<class K, class V>
	class map
	{
	public:
		struct MapKeyofT
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};
		typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::iterator iterator;
		typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::const_iterator const_iterator;
		iterator begin()
		{
			return _root.begin();
		}
		iterator end()
		{
			return _root.end();
		}

		const_iterator begin() const
		{
			return _root.begin();
		}
		
		const_iterator end() const
		{
			return _root.end();
		}

		pair<iterator, bool> insert(const pair<const K, V>& kv)
		{
			return _root.Insert(kv);
		}
		/*
			operator[]:给一个key,返回这个key所对应的value的引用
			简化前:
			mapped_type& operator[](const Key_type& k)
			{
			   return (*(this->insert(make_pair(k,mapped_type())))).first).second;
			}

			简化后
			V& operator(const K& key)
			{
			   pair<iterator,bool> ret=insert(key,V());//V():value的默认构造的匿名对象
			   return ret.first->second;
			}
		*/
		V& operator[](const K& k)
		{
			pair<iterator, bool> ret = insert(make_pair(k, V()));
			return ret.first->second;
		}

	private:
		//我们知道:map的Key不允许被修改,Value允许被修改
		//因此pair里面的K加上const修饰
		RBTree<K, pair<const K, V>, MapKeyofT> _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

七.改造后的红黑树代码

#pragma once
namespace wzs
{
	enum Color
	{
		RED,
		BLACK
	};
	template<class T>
	struct RBTreeNode
	{
		RBTreeNode<T>* _pLeft;
		RBTreeNode<T>* _pRight;
		RBTreeNode<T>* _pParent;
		Color _color;
		T _data;
		//新插入的节点默认是红色
		RBTreeNode(const T& data)
			:_pLeft(nullptr)
			, _pRight(nullptr)
			, _pParent(nullptr)
			, _color(RED)
			, _data(data)
		{}
	};

	//给红黑树增加迭代器
	template<class T, class Ref, class Ptr>
	struct __TreeIterator
	{
		typedef RBTreeNode<T> Node;
		typedef __TreeIterator<T, T&, T*> iterator;
		typedef __TreeIterator<T, Ref, Ptr> Self;
		Node* _node;

		__TreeIterator(Node* node)
			:_node(node)
		{}

		//const迭代器和普通迭代器的转化
		__TreeIterator(const iterator& it)
			:_node(it._node)
		{}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &_node->_data;
		}

		//找中序遍历的下一个节点
		Self& operator++()
		{
			//1.左子树 根节点 右子树
			//如果有右孩子,那就是右子树的最左节点
			//如果没有右孩子,那往上找直到我是父亲的左孩子或者我的父亲是空节点为止,此时我的父亲就是下一个节点
			Node* cur = _node;
			if (cur->_pRight)
			{
				Node* right = cur->_pRight;
				while (right->_pLeft)
				{
					right = right->_pLeft;
				}
				_node = right;
			}
			else
			{
				Node* parent = cur->_pParent;
				while (parent && parent->_pRight == cur)
				{
					cur = parent;
					parent = cur->_pParent;
				}
				_node = parent;
			}
			return *this;
		}

		bool operator!=(const Self& s)
		{
			return _node != s._node;
		}

		bool operator==(const Self& s)
		{
			return _node == s._node;
		}
	};

	template<class K, class V,class KeyofT>
	class RBTree
	{
		typedef RBTreeNode<V> Node;
	public:
		typedef __TreeIterator<V, V&, V*> iterator;
		typedef __TreeIterator<V, const V&, const V*> const_iterator;

		iterator begin()
		{
			Node* cur = _pRoot;
			while (cur && cur->_pLeft)
			{
				cur = cur->_pLeft;
			}
			return iterator(cur);
		}

		iterator end()
		{
			return iterator(nullptr);
		}

		const_iterator begin() const
		{
			Node* cur = _pRoot;
			while (cur && cur->_pLeft)
			{
				cur = cur->_pLeft;
			}
			return const_iterator(cur);
		}

		const_iterator end() const
		{
			return const_iterator(nullptr);
		}

		//1,参数只需要传V即可(也就是红黑树的第二个模板参数)
		//对于set而言V就是Key
		//对于map而言,V就是pair<K,V>
		pair<iterator, bool> Insert(const V& data)
		{
			if (_pRoot == nullptr)
			{
				_pRoot = new Node(data);
				//根节点是黑色
				_pRoot->_color = BLACK;
				return make_pair(iterator(_pRoot), true);
			}
			Node* cur = _pRoot, * parent = nullptr;
			while (cur)
			{
				//比我小,往左找
				if (_kot(data) < _kot(cur->_data))
				{
					parent = cur;
					cur = cur->_pLeft;
				}
				//比我大,往右找
				else if (_kot(data) > _kot(cur->_data))
				{
					parent = cur;
					cur = cur->_pRight;
				}
				//有重复元素,插入失败
				else
				{
					return make_pair(iterator(cur), false);
				}
			}
			//找到空位置,开始插入
			cur = new Node(data);
			Node* newnode = cur;
			//连接父亲和孩子
			if (_kot(cur->_data) < _kot(parent->_data))
			{
				parent->_pLeft = cur;
			}
			else
			{
				parent->_pRight = cur;
			}
			cur->_pParent = parent;
			//父亲是黑色,插入成功
			if (parent->_color == BLACK)
			{
				return make_pair(iterator(newnode), true);
			}
			//父亲是红色,需要调整
			//且此时爷爷一定是黑色
			//根据叔叔的颜色来调整
			while (parent && parent->_color == RED)
			{
				Node* grandParent = parent->_pParent;
				//爸爸是爷爷的左孩子
				if (parent == grandParent->_pLeft)
				{
					Node* uncle = grandParent->_pRight;
					//根据叔叔的颜色来调整
					//1.叔叔存在且为红
					if (uncle && uncle->_color == RED)
					{
						//修改爸爸,叔叔,爷爷的颜色
						uncle->_color = parent->_color = BLACK;
						grandParent->_color = RED;
						//此时视爷爷为新插入的红色节点继续向上影响
						cur = grandParent;
						parent = cur->_pParent;
					}
					//2.叔叔不存在或者叔叔是黑
					else
					{
						//1.我是爸爸的左孩子
						if (parent->_pLeft == cur)
						{
							//对爷爷进行一次右旋
							RotateR(grandParent);
							//把爷爷改成红色,爸爸改成黑色
							grandParent->_color = RED;
							parent->_color = BLACK;
							//此时爸爸是黑色,无需break,当然break也可以,因此爸爸是黑色,下次循环就不会进入了
						}
						//2.我是爸爸的右孩子
						else
						{
							//1.对爸爸进行左旋
							RotateL(parent);
							//2.对爷爷右旋
							RotateR(grandParent);
							//3.孩子改成黑色,爷爷改成红色
							cur->_color = BLACK;
							grandParent->_color = RED;
							//4.一定要break,如果不break的话,因为爸爸是红色,所以循环会继续,此时就乱套了
							break;
						}
					}
				}
				//爸爸是爷爷的右孩子
				else
				{
					Node* uncle = grandParent->_pLeft;
					//1.叔叔存在且为红
					if (uncle && uncle->_color == RED)
					{
						uncle->_color = parent->_color = BLACK;
						grandParent->_color = RED;
						cur = grandParent;
						parent = cur->_pParent;
					}
					//2.叔叔不存在或者叔叔为黑
					else
					{
						//1.我是爸爸的右孩子
						if (parent->_pRight == cur)
						{
							//对爷爷左旋
							RotateL(grandParent);
							//爷爷改成红色,爸爸改成黑色
							grandParent->_color = RED;
							parent->_color = BLACK;
							//此时爸爸是黑色,无需break,当然break也可以,因此爸爸是黑色,下次循环就不会进入了
						}
						//2.我是爸爸的左孩子
						else
						{
							//1.对爸爸右旋
							RotateR(parent);
							//2.对爷爷左旋
							RotateL(grandParent);
							//3.把孩子改成黑色,爷爷改成红色
							cur->_color = BLACK;
							grandParent->_color = RED;
							//4.一定要break,如果不break的话,因为爸爸是红色,所以循环会继续,此时就乱套了
							break;
						}
					}
				}
			}
			_pRoot->_color = BLACK;
			return  make_pair(iterator(newnode), true);
		}

		// 检测红黑树中是否存在关键字为key的节点，存在返回该节点的地址，否则返回nullptr
		Node* Find(const K& key)
		{
			Node* cur = _pRoot;
			while (cur)
			{
				if (cur->_data.first > key)
				{
					cur = cur->_pLeft;
				}
				else if (cur->_data.second < key)
				{
					cur = cur->_pRight;
				}
				else
				{
					return cur;
				}
			}
			return nullptr;
		}

		// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测
		bool IsValidRBTRee()
		{
			//1.空树是红黑树
			if (_pRoot == nullptr)
			{
				return true;
			}
			//2.根节点不能为红色
			if (_pRoot->_color == RED)
			{
				return false;
			}
			//3.为了验证性质: 红黑树的任意一条路径上的黑色节点个数相同   找参考值
			size_t ReferenceCount = 0;
			Node* cur = _pRoot;
			while (cur)
			{
				if (cur->_color == BLACK)
				{
					ReferenceCount++;
				}
				cur = cur->_pLeft;
			}
			return _IsValidRBTRee(_pRoot, 0, ReferenceCount);
		}

		void InOrder()
		{
			_InOrder(_pRoot);
		}
	private:
		bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t& ReferenceCount)
		{
			if (pRoot == nullptr)
			{
				if (blackCount != ReferenceCount)
				{
					cout << "存在黑色节点数量不相等的路径" << endl;
					return false;
				}
				return true;
			}
			//验证性质: 红黑树中不能存在连续的红色节点
			//如果一个节点是红色,该节点一定不是根节点,因此该节点一定有父亲
			//只需要保证红色节点的父亲不是红色节点即可
			if (pRoot->_color == RED)
			{
				if (pRoot->_pParent->_color == RED)
				{
					cout << "存在连续的红色节点" << endl;
					return false;
				}
			}
			else
			{
				blackCount++;
			}
			return _IsValidRBTRee(pRoot->_pLeft, blackCount, ReferenceCount) && _IsValidRBTRee(pRoot->_pRight, blackCount, ReferenceCount);
		}

		// 右单旋
		void RotateR(Node* pParent)
		{
			Node* subL = pParent->_pLeft;
			Node* subLR = subL->_pRight;
			Node* grandParent = pParent->_pParent;
			subL->_pRight = pParent;
			pParent->_pParent = subL;
			pParent->_pLeft = subLR;
			if (subLR)
				subLR->_pParent = pParent;
			if (grandParent == nullptr)
			{
				_pRoot = subL;
				_pRoot->_pParent = nullptr;
			}
			else
			{
				if (pParent == grandParent->_pLeft)
				{
					grandParent->_pLeft = subL;
				}
				else
				{
					grandParent->_pRight = subL;
				}
				subL->_pParent = grandParent;
			}
		}

		// 左单旋
		void RotateL(Node* pParent)
		{
			Node* subR = pParent->_pRight;
			Node* subRL = subR->_pLeft;
			Node* grandParent = pParent->_pParent;
			pParent->_pParent = subR;
			subR->_pLeft = pParent;
			pParent->_pRight = subRL;
			if (subRL)
				subRL->_pParent = pParent;
			//说明此时pParent是_pRoot
			if (grandParent == nullptr)
			{
				_pRoot = subR;
				_pRoot->_pParent = nullptr;
			}
			//说明此时pParent所在的树是一颗子树,需要跟父亲链接
			else
			{
				if (pParent == grandParent->_pLeft)
				{
					grandParent->_pLeft = subR;
				}
				else
				{
					grandParent->_pRight = subR;
				}
				subR->_pParent = grandParent;
			}
		}

		void _InOrder(Node* root)
		{
			if (root == nullptr) return;
			_InOrder(root->_pLeft);
			cout << root->_data.first << " " << root->_data.second << " ";
			_InOrder(root->_pRight);
		}
	private:
		Node* _pRoot = nullptr;
		KeyofT _kot;
	};
}
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
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434

测试代码:

#include <iostream>
using namespace std;
#include <vector>
#include "MySet.h"
#include "MyMap.h"
namespace wzs
{
	void test1()
	{
		map<int, int> m;
		m.insert(make_pair(1, 1));
		m.insert(make_pair(2, 1));
		m.insert(make_pair(3, 1323));
		m.insert(make_pair(4, 111));
		m.insert(make_pair(3, 12));
		m.insert(make_pair(1, 1));
		map<int, int>::iterator it = m.begin();
		while(it != m.end())
		{
			it->second = 10;
			cout << it->first << " : " << it->second << endl;
			++it;
		}
		cout << endl;
		map<int, int>::const_iterator cit = m.begin();
		while (cit != m.end())
		{
			//it->first = 10;
			//cit->second = 10;
			cout << cit->first << " : " << cit->second << endl;
			++cit;
		}
	}

	void test2()
	{
		set<int> s;
		s.insert(1);
		s.insert(2);
		s.insert(3);
		s.insert(4);
		set<int>::iterator it = s.begin();
		while (it != s.end())
		{
			//*it += 1;
			cout << *it << " ";
			++it;
		}
		cout << endl;

		set<int>::const_iterator cit = s.begin();
		while (cit != s.end())
		{
			//*cit += 1;
			cout << *cit << " ";
			++cit;
		}
		cout << endl;
	}

	void test3()
	{
		//统计次数
		map<string, int> countMap;
		vector<string> dict = { "hello","hi","who","hi","hi","who","which" };
		for (auto& e : dict)
		{
			countMap[e]++;
		}
		for (auto& e : countMap)
		{
			cout << e.first << ":" << e.second << endl;
		}
	}
}
int main()
{
	wzs::test1();
	cout << endl;
	wzs::test2();
	cout << endl;
	wzs::test3();
	return 0;
}
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

以上就是C++ 改造红黑树,封装map和set的全部内容,希望能对大家有所帮助!