【C++/STL】：红黑树的应用 --- 封装map和set_c++ 红黑树 stl

点击跳转至文章：【C++】：红黑树深度剖析 — 手撕红黑树！

前言

map 和 set 的底层本质上还是复用，通过对红黑树的改造，再分别套上一层 map 和 set 的 “壳子”，以达到 “一树二用” 的目的。

在改造红黑树的过程中，我大概归纳了以下几个需要重点解决的问题：

(1) 对红黑树节点的改造。关联式容器中存储的是<key, value>的键值对，K为key的类型，如果是 set 则是 K，如果是map，则为pair<K, V>。如何用一个节点结构控制两种类型，使用类模板参数T。

(2) 在插入操作时，如何完成数据的比较。由于我们的节点类型的泛型，如果是 set 则是 K，如果是map，则为pair<K, V>，而pair的比较是由 first 和 second 共同决定的，这显然不符合要求。因此插入数据时不能直接比较，要在 set 和 map 类中实现一个 KeyOfT 的仿函数，以便单独获取两个类型中的 key 数据。

(3) 在红黑树中实现普通迭代器和const迭代器，再套上 “壳子”。

(4) 关于 key 的修改问题。在STL库中，set 和 map 的 key 都是不能修改的，因为要符合二叉搜索树的特性，但是 map 中的 value 又是可以修改的。这个问题需要单独处理。

(5) 红黑树相关接口的改造。其中包括对 Find 和 Insert 函数的改造，特别是 Insert，因为在 map 里实现 operator[] 时需要依赖 Insert 函数。

说明：如果大家要自己动手实现封装，可以按照上面五个问题的流程进行实现。但是在本篇文章中由于展示等的原因，无法按照上面的步骤。

一，红黑树的改造

1. 红黑树的主体框架

(1) K 是给find，erase用的，T 是给节点，insert用的；

(2) KeyOfT 是由于下面需要比较，但是比较时不知道T的类型， set是key类型的比较，map是pair类型的比较，要统一变成key的比较。

template <class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node; //节点
public:
	typedef RBTreeIterator<T, T&, T*> Iterator; //普通迭代器
	typedef RBTreeIterator<T, const T&, const T*> ConstIterator; //const 迭代器

	//其他功能的实现……
	
private:
	Node* _root = nullptr;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

2. 对红黑树节点结构的改造

//枚举颜色
enum Colour
{
	RED,
	BLACK
};

//节点类
template <class T>
struct RBTreeNode
{
	T _data;

	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	//pair<K, V> _kv;
	Colour _col;

	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(BLACK)
	{}
};

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

3. 红黑树的迭代器

3.1 迭代器类

//迭代器类
template <class T, class Ref, class Ptr>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self;

	Node* _node;

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

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

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

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

	//从局部的某一个过程考虑
	Self& operator++()
	{
		if (_node->_right)
		{
			//右不为空，右子树的最左节点就是下一个访问的节点
			Node* leftMost = _node->_right;
			while (leftMost->_left)
				leftMost = leftMost->_left;

			_node = leftMost;
		}
		else
		{
			//右为空，代表当前节点所在的子树已经访问完了，下一个访问的节点是祖先
			//沿着到根节点的那个路径查找，孩子是父亲左的那个祖先节点就是下一个访问的节点

			Node* cur = _node;
			Node* parent = cur->_parent;
			//循环找祖先
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}

			_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
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

迭代器中最复杂的就是 operator++()的实现，它与原先的 vector/list 不同，红黑树的迭代器是要完成二叉树的中序遍历。

为了完成二叉树的中序遍历，我们需要从局部的某一过程考虑，就是假设 it 已经走到了某一节点，要找到下一个访问的节点，分为两种情况：

(1) 当前节点的右子树不为空：

如下图，假设 it 已经到达了13节点，说明此时13的左子树已经访问完了，右子树不为空，下一个要访问的节点就是右子树的最左节点15

(2) 当前节点的右子树为空：

如下图，假设 it 此时到达了15节点，它的右子树为空，下一个访问哪个节点呢？有些人单纯的认为是15的父亲17，其实是错误的。

那假设 it 到达6节点上呢，6的右为空，但是根据中序遍历的顺序，6的父亲1已经访问过了。

其实此时是要找当前节点的祖先，父亲也是祖先之一。

右为空，代表当前节点所在的子树已经访问完了，下一个访问的节点是祖先，是哪个祖先呢？沿着到根节点的那个路径查找，孩子是父亲左的那个祖先节点就是下一个访问的节点。

(a) 假设此时走到了15节点，下一个访问的节点是17，cur 是 parent 的左，parent 就是下一个要访问的那个祖先节点；

(b) 假设此时走到了6节点，下一个访问的节点是8，但是此时 cur 是 parent 的右，不满足条件，继续向上查找，cur = parent，parent = parent->_parent，这时 cur 在1，parent 在8，cur 是 parent 的左，parent 就是下一个要访问的那个祖先节点

3.2 Begin() 和 End()

//中序遍历，找树的最左节点
Iterator Begin()
{
	//Node* cur = _root;
	Node* leftMost = _root;

	while (leftMost->_left)
		leftMost = leftMost->_left;

	return Iterator(leftMost);
}

Iterator End()
{
	return Iterator(nullptr);
}

ConstIterator Begin()const
{
	//Node* cur = _root;
	Node* leftMost = _root;

	while (leftMost->_left)
		leftMost = leftMost->_left;

	return ConstIterator(leftMost);
}

ConstIterator End()const
{
	return ConstIterator(nullptr);
}

Iterator Find(const K& key)
{
	Node* cur = _root;
	while (cur)
	{
		if (cur->_data > key)
			cur = cur->_left;
		else if (cur->_data < key)
			cur = cur->_right;
		else
			return Iterator(cur);
	}
	return End();
}
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

四，红黑树相关接口的改造

4.1 Find 函数的改造

查找成功，返回查找到的那个节点的迭代器，查找失败，就返回 nullptr。

Iterator Find(const K& key)
{
	Node* cur = _root;
	while (cur)
	{
		if (cur->_data > key)
			cur = cur->_left;
		else if (cur->_data < key)
			cur = cur->_right;
		else
			return Iterator(cur);
	}
	return End();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4.2 Insert 函数的改造

map 里的 operator[] 需要依赖 Insert 的返回值

pair<Iterator, bool> Insert(const T& data)
{
	if (_root == nullptr)
	{
		_root = new Node(data);
		return make_pair(Iterator(_root), true);
	}

	KeyOfT kot;
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (kot(cur->_data) > kot(data))
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (kot(cur->_data) < kot(data))
		{
			parent = cur;
			cur = cur->_right;
		}
		else
			return make_pair(Iterator(cur), false);
	}
	cur = new Node(data);
	Node* newnode = cur;

 	//此处省略变色+旋转部分的代码……
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

五，红黑树改造的完整代码

说明：由于代码太长，影响展示效果，所以插入部分的 变色+旋转 的代码此处省略，和红黑树的基本一模一样，请前往【C++】：红黑树深度剖析 — 手撕红黑树！

RBTree.h

#include <iostream>
#include <assert.h>
using namespace std;

//枚举颜色
enum Colour
{
	RED,
	BLACK
};

//节点类
template <class T>
struct RBTreeNode
{
	T _data;

	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	//pair<K, V> _kv;
	Colour _col;

	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(BLACK)
	{}
};

//迭代器类
template <class T, class Ref, class Ptr>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self;

	Node* _node;

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

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

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

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

	//从局部的某一个过程考虑
	Self& operator++()
	{
		if (_node->_right)
		{
			//右不为空，右子树的最左节点就是下一个访问的节点
			Node* leftMost = _node->_right;
			while (leftMost->_left)
				leftMost = leftMost->_left;

			_node = leftMost;
		}
		else
		{
			//右为空，代表当前节点所在的子树已经访问完了，下一个访问的节点是祖先
			//沿着到根节点的那个路径查找，孩子是父亲左的那个祖先节点就是下一个访问的节点

			Node* cur = _node;
			Node* parent = cur->_parent;
			//循环找祖先
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}
};


//K 是给find，erase用的，T 是给节点，插入用的
// KeyOfT 是由于下面需要比较，但是比较时不知道T的类型，
// set是key类型的比较，map是pair类型的比较，要统一变成key的比较

template <class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef RBTreeIterator<T, T&, T*> Iterator;
	typedef RBTreeIterator<T, const T&, const T*> ConstIterator;


	//中序遍历，找树的最左节点
	Iterator Begin()
	{
		//Node* cur = _root;
		Node* leftMost = _root;

		while (leftMost->_left)
			leftMost = leftMost->_left;

		return Iterator(leftMost);
	}

	Iterator End()
	{
		return Iterator(nullptr);
	}

	ConstIterator Begin()const
	{
		//Node* cur = _root;
		Node* leftMost = _root;

		while (leftMost->_left)
			leftMost = leftMost->_left;

		return ConstIterator(leftMost);
	}

	ConstIterator End()const
	{
		return ConstIterator(nullptr);
	}

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

	pair<Iterator, bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			return make_pair(Iterator(_root), true);
		}

		KeyOfT kot;
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kot(cur->_data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else
				return make_pair(Iterator(cur), false);
		}
		cur = new Node(data);
		Node* newnode = cur;

		//新增节点，颜色为红色
		cur->_col = RED;
		
		//此处省略变色+旋转部分的代码……
		
private:
		Node* _root = 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

六，set 的封装实现

set的底层为红黑树，因此只需在set内部封装一棵红黑树，即可将该容器实现出来。

为了解决 set 中 key 值不能修改的问题，在传给 RBTree 的第二个模板参数前加 const 即可。

MySet.h

#include "RBTree.h"

namespace cc
{
	template<class K>
	class set
	{
		// 获取 set 里面的 key
		struct SetOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};

	public:
		typedef typename RBTree<K, const K, SetOfT>::Iterator iterator;
		typedef typename RBTree<K, const K, SetOfT>::ConstIterator const_iterator;

		iterator begin()
		{
			return _t.Begin();
		}

		iterator end()
		{
			return _t.End();
		}

		const_iterator begin()const
		{
			return _t.Begin();
		}

		const_iterator end()const
		{
			return _t.End();
		}

		pair<iterator, bool> insert(const K& key)
		{
			return _t.Insert(key);
		}

		iterator find(const K& key)
		{
			return _t.Find(key);
		}
	private:
		RBTree<K, const K, SetOfT> _t;
	};
}

//使用 const 迭代器 
void Print(const cc::set<int>& s)
{
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

//测试代码
void Test_set()
{
	//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	int a[] = { 16,3,7,11,9,26,18,14,15 };
	cc::set<int> s;

		for (auto e : a)
			s.insert(e);

		for (auto e : s)
			cout << e << " ";

		cout << endl;

		Print(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
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

七，map 的封装实现

map的底层结构就是红黑树，因此在map中直接封装一棵红黑树，然后将其接口包装下即可。

map 中 pair 的 first 不能修改，second 可以修改，在 pair 的第一个参数前加 const 即可。

MyMap.h

#include "RBTree.h"

namespace cc
{
	template<class K, class V>
	class map
	{
		//获取 pair 中的 key
		struct MapOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename RBTree<K, pair<const K, V>, MapOfT>::Iterator iterator;
		typedef typename RBTree<K, pair<const K, V>, MapOfT>::ConstIterator const_iterator;


		iterator begin()
		{
			return _t.Begin();
		}

		iterator end()
		{
			return _t.End();
		}

		const_iterator begin()const
		{
			return _t.Begin();
		}

		const_iterator end()const
		{
			return _t.End();
		}

		pair<iterator, bool> insert(const pair<K, V>& kv)
		{
			return _t.Insert(kv);
		}

		iterator find(const K& key)
		{
			return _t.Find(key);
		}

		//给一个key，返回value的引用
		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = insert(make_pair(key, V()));
			return ret.first->second;
		}
	private:
		RBTree<K, pair<const K,V>, MapOfT> _t;
	};
}


//测试代码
void Test_map()
{
	cc::map<string, string> dict;

	dict.insert({ "left","左边" });
	dict.insert({ "right","右边" });
	dict.insert({ "insert","插入" });

	dict["left"] = "剩余，左边";

	cc::map<string, string>::iterator it = dict.begin();
	while (it != dict.end())
	{
		//it->first += 'x'; //err
		it->second += 'y'; //ok

		cout << it->first << ":" << it->second << endl;
		++it;
	}

	cout << endl;
}

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