🌈欢迎来到数据结构专栏~~封装Map和Set

---

• (꒪ꇴ꒪(꒪ꇴ꒪ )🐣,我是Scort
• 目前状态：大三非科班啃C++中
• 🌍博客主页：张小姐的猫~江湖背景
• 快上车🚘，握好方向盘跟我有一起打天下嘞！
• 送给自己的一句鸡汤🤔：
• 🔥真正的大师永远怀着一颗学徒的心
• 作者水平很有限，如果发现错误，可在评论区指正，感谢🙏
• 🎉🎉欢迎持续关注！
  

一. 红黑树源码

虽然 set 参数只有 key，但是介于 map 除了 key 还有 value；我们任然将对一棵KV模型的红黑树进行封装，

//枚举颜色
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>
struct RBTree
{
typedef RBTreeNode<K, V> Node;
public:
//如果是空树，则插入节点作为root节点
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;//根节点必须是黑色
return true; //插入成功
}

//按二叉搜索树的插入方法，找到待插入位置
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (kv.first > cur->_kv.first)//待插入结点的key值大于当前结点的key值
{
//往节点的右子树走
parent = cur;
cur = cur->_right;
}
else if (kv.first < cur->_kv.first)//待插入结点的key值小于当前结点的key值
{
//往节点的左子树走
parent = cur;
cur = cur->_left;
}
else//插入的值等于当前的节点，返回失败
{
return false;
}
}

//将节点链接到树上
cur = new Node(kv);//构造节点 
cur->_col = RED;

if (kv.first < parent->_kv.first)//判断链接左还是右？
{
//插入到左边
parent->_left = cur;
cur->_parent = parent;
}
else if (kv.first > parent->_kv.first)
{
//插入到右边
parent->_right = cur;
cur->_parent = parent;
}

//如果插入节点的父节点是红色的，则需要对红黑树进行操作
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
assert(grandfather);
assert(grandfather->_col == BLACK);

//关键看叔叔  ~ 判断叔叔的位置
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//情况1：uncle存在且为红  + 继续往上处理
if (uncle && uncle->_col == RED)
{
//变色：p和u变黑，g变红
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;

//继续往上调整
cur = grandfather;
parent = cur->_parent;
}
else  //情况2 + 情况3：uncle不存在 + uncle存在且为黑
{
//情况二：单旋 + 变色
//    g
//  p   u
//c            
if (cur = parent->_left)
{
RotateR(grandfather);//右旋

//颜色调整
parent->_col = BLACK;
grandfather->_col = RED;
}
else//cur == parent->_right
{
//情况三：左右双旋 + 变色
//    g
//  p   u
//    c 
RotateL(parent);
RotateR(grandfather);

//调整颜色
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else  //parent == grandfather->_right
{
Node* uncle = grandfather->_left;
//情况1：uncle存在且为红 + 继续往上处理
if (uncle && uncle->_col == RED)
{
//变色：p和u变黑，g变红
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;

//继续往上调整
cur = grandfather;
parent = cur->_parent;
}
else  //情况2 + 情况3：uncle不存在 + uncle存在且为黑
{
//情况二：单旋 + 变色
//    g
//  u   p
//        c            
if (cur = parent->_right)
{
RotateL(grandfather);//左单 旋

//颜色调整
parent->_col = BLACK;
grandfather->_col = RED;
}
else//cur == parent->_left
{
//情况三：右左双旋 + 变色
//    g
//  u   p
//    c 
RotateR(parent);
RotateL(grandfather);

//调整颜色
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;//不管什么，最后根要变黑
return true;
}

void InOrder()
{
_InOrder(_root);
cout << endl;
}

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

if (_root->_col == RED)
{
cout << "根节点不是黑色" << endl;
return false;
}

// 黑色节点数量基准值
int benchmark = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
++benchmark;

cur = cur->_left;//以最左的路径进行
}

return PrevCheck(_root, 0, benchmark);
}


private:
bool PrevCheck(Node* root, int blackNum, int& benchmark)
{
if (root == nullptr)
{
//cout << blackNum << endl;
//return;
if (benchmark == 0)
{
benchmark = blackNum;
return true;
}

if (blackNum != benchmark)
{
cout << "某条黑色节点的数量不相等" << endl;
return false;
}
else
{
return true;
}
}

if (root->_col == BLACK)
{
++blackNum;
}
//检测它的父亲
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "存在连续的红色节点" << endl;
return false;
}

return PrevCheck(root->_left, blackNum, benchmark)
&& PrevCheck(root->_right, blackNum, benchmark);
}

void _InOrder(Node* root)
{
if (root == nullptr)//空树也是红黑树
return;
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentParent = parent->_parent;

//建立subRL与parent之间的联系
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;

//建立parent与subR之间的联系
subR->_left = parent;
parent->_parent = subR;

//建立subR与parentParent之间的联系
if (parentParent == nullptr)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
{
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;

//建立subLR与parent之间的联系
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;

//建立parent与subL之间的联系
subL->_right = parent;
parent->_parent = subL;

//建立subL与parentParent之间的联系
if (parentParent == nullptr)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}

//左右双旋
void RotateLR(Node* parent)
{
RotateL(parent->_left);
RotateR(parent);
}

//右左双旋
void RotateRL(Node* parent)
{
RotateR(parent->_right);
RotateL(parent);
}

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

二. 观察源码

🥑底层RBTree的结构

RBTree是根据传的Value的值来判断是什么类型，也就是一棵泛型的RBTree，通过不同的实例化，实现出了Map和Set（传Key就是Set，传pair就是Map）

🥑底层的Key和Map

可见set传的是Key，Map传的是pair

二. 参数的适配

为了实现泛型RBTree，对此我们将红黑树第二个模板参数的名字改为T，让自动识别是map还是set

template<class K, class T>
struct RBTree
1
2

T模板参数可能只是键值Key，也可能是由Key和Value共同构成的键值对。如果是set容器，那么它传入底层红黑树的模板参数就是Key和Key：

template<class K>
class set
{
public：
//...
private:
RBTree<K, K> _t;
};
1
2
3
4
5
6
7
8

但如果是map容器，那么它传入底层红黑树的模板参数就是Key以及Key和Value构成的键值对：

template<class K, class V>
class map
{
public:
//...
private:
RBTree<K, pair<K, V>> _t;
};
1
2
3
4
5
6
7
8

那么问题来了：如果只看T的判断的话，是不是可以只保留第二个模板参数呢？

1️⃣对于Insert来说确实是这样的，因为此时红黑树的第二个模板参数当中也是有键值Key的，但是Key实际上是不可以省略的！

2️⃣对于set容器来说，省略红黑树的第一个参数当然没问题，因为set传入红黑树的第二个参数与第一个参数是一样的。但是对于map容器来说就不行了，因为map容器所提供的接口当中有些是只要求给出键值Key的，比如find和erase

三. 数据的存储

红黑树的模板参数变成了K和T，那节点存的是什么呢？
看了源码得知

• set容器：K和T都代表键值Key
• map容器：K代表键值Key，T代表由Key和Value构成的键值对

对于set容器来说，底层红黑树结点当中存储K和T都是一样的，但是对于map容器来说，底层红黑树就只能存储T了。由于底层红黑树并不知道上层容器到底是map还是set，因此红黑树的结点当中直接存储T就行了

这样一来就可以实现泛型树了，当上层容器是set的时候，结点当中存储的是键值Key；当上层容器是map的时候，结点当中存储的就是<Key, Value>键值对

template<class T>
struct RBTreeNode
{
RBTreeNode<K, V>* _left;//三叉链
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;

T _data;//存储的数据
Colour _col;//节点颜色

RBTreeNode(const pair<K, V>& kv)
:_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

四. 仿函数的支持

那我们插入比较的时候用data去比较吗？

• 对于set而言是Key，可以比较
• 但是对于map是pair，那我们要取其中的first来比较，但是我们能取first吗？
• 这个地方的data有可能是map；也有可能是set

那就只能我们自己实现一个仿函数了，如果是map那就是用于获取T当中的键值Key，当红黑树比较的时候就是仿函数去获取

仿函数，就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了

template<class K, class V>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
}
private:
RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
1
2
3
4
5
6
7
8
9
10
11
12
13

底层的红黑树不知道上层传的是map还是set，因此当需要进行两个结点键值的比较时，底层红黑树都会通过传入的仿函数来获取键值Key，进而进行两个结点键值的比较

set的仿函数不可缺

template<class K>
class set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
}
private:
RBTree<K, K, SetKeyOfT> _t;
1
2
3
4
5
6
7
8
9
10
11
12

所以set容器传入底层红黑树的就是set的仿函数，map容器传入底层红黑树的就是map的仿函数

//查找函数
Node* Find(const K& key)
{
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (kot(data) > kot(cur->_data))//待插入结点的key值大于当前结点的key值
{
//往节点的右子树走
parent = cur;
cur = cur->_right;
}
else if (kot(data) < kot(cur->_data))//待插入结点的key值小于当前结点的key值
{
//往节点的左子树走
parent = cur;
cur = cur->_left;
}
else//插入的值等于当前的节点，返回失败
{
return false;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

注意：

• 1️⃣所有进行节点键值比较的地方，均需要通过仿函数获取对应节点的键值后再进行键值的比较
• 2️⃣map和set的底层是一棵泛型红黑树实例化而来，实际上不是同一棵红黑树

五. 迭代器实现

🎨正向迭代器

红黑树的正向迭代器实际上就是对结点指针进行了封装，因此在正向迭代器当中实际上就只有一个成员变量，那就是结点的指针！

//正向迭代器
template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{
typedef RBTreeNode<T> Node;//节点类型
typedef __RBTreeIterator<T, Ref, Ptr> Self;//正向迭代器类型

Node* _node;//封装节点的指针
}
1
2
3
4
5
6
7
8
9

通过一个节点的指针就可以封装出迭代器！

__RBTreeIterator(Node* node)
:_node(node)
{}
1
2
3

当我们对正向迭代器进行解引用操作时，我们直接返回对应结点数据的引用即可

Ref operator*()
{
return _node->_data;//返回节点数据的引用
}
1
2
3
4

以及成员访问操作符 ->：

Ptr operator->()
{
return &_node->_data;//返回节点数据的指针
}
1
2
3
4

当然，正向迭代器当中至少还需要重载==和!=运算符，实现时直接判断两个迭代器所封装的结点是否是同一个即可

bool operator!=(const Self& s) const
{
return _node != s._node//判断两个正向迭代器所封装的结点是否是同一个
}

bool operator==(const Self& s) const
{
return _node == s._node//同上
}
1
2
3
4
5
6
7
8
9

重头戏才刚刚开始！真正的难点实际上++和--运算符的重载

一个结点的正向迭代器进行++操作后，应该根据红黑树中序遍历的序列找到当前结点的下一个结点

具体思路如下：

1. 当前节点的右子树不为空，++就是找 右子树中序的第一个（最左节点）
2. 如果节点的右子树为空，++就是找到 孩子在祖先左边的祖先

Self& operator++()
{
if (_node->_right)
{
//寻找该节点右子树中的最左节点
Node* left = _node->_right;
while (left->_left)
{
left = left->_left;
}
_node = left;//给给变成该节点
}
else
{
//找孩子在祖先左边的祖先
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_right) //判断parent不为空，空就崩了
{
cur = 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

同理， -- 的逻辑是一样的：

1. 当前节点的左子树不为空，--就是找 左子树中序的第一个（最右节点）
2. 如果节点的左子树为空，--就是找到 孩子在祖先右边的祖先

Self& operator--()
{
if (_node->_left)//结点的左子树不为空
{
//寻找该节点左子树中的最右节点
Node* right = _node->_left;
while (right->_right)
{
right = right->_right;
}
_node = right;//给给变成该节点
}
else//结点的左子树为空
{
//找孩子在祖先右边的祖先
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_left) //判断parent不为空，空就崩了
{
cur = 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

我们实现迭代器的时候会将迭代器类型进行 typedef 方便调用，完事了不要忘了迭代器还有两个成员函数 begin（） 和 end（） ；

• begin（） 返回中序序列当中第一个结点的正向迭代器，即最左节点
• end （）返回中序序列当中最后一个结点下一个位置的正向迭代器，这里直接用空指针构造一个正向迭代器（不严谨的处理）

template<class K, class T, class KeyOfT>
struct RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef __RBTreeIterator<T, T&, T*> iterator;//正向迭代器

iterator begin()
{
//寻找最左节点
Node* left = _root;
while (left && left->_left)
{
left = left->_left;
}

//返回最左结点的正向迭代器
return iterator(left);
}

iterator end()
{
//返回空节点的迭代器
return 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

实际上，上述所实现的迭代器是有缺陷的，因为理论上我们对end()位置的正向迭代器进行–操作后，应该得到最后一个结点的正向迭代器，但我们实现end()时，是直接返回由nullptr构造得到的正向迭代器的，因此上述实现的代码无法完成此操作

所以我们不妨看看 C++ STL 库的实现逻辑

库里面是采用了类似双向链表的处理，给整个红黑树造了一个哨兵位节点，该节点左边指向最小的最左节点，右边指向最大的右节点，同时还有一个非常 bug 的设计就是这里哨兵位节点 header 的红黑树头结点之间的 parent 相互指向

在该结构下，实现 begin() 时，直接用头结点的左孩子构造一个正向迭代器即可，实现 rbegin() 时，直接用头结点的右孩子构造一个反向迭代器即可，严谨的过程是先构造正向迭代器，再用正向迭代器构造反向迭代器，end（） 和 rend（） 此时就不需要什么 nullptr 了，直接有头结点（哨兵位）进行迭代器构造即可，这样就能完成一个逻辑完整的迭代器了

🎨反向迭代器

上面得知：反向迭代器的严谨构造过程是用正向迭代器进行封装，我们可以将

template<class Iterator>//迭代器适配器
struct ReverseIterator
{
typedef ReverseIterator<Iterator> Self; //反向迭代器
typedef typename Iterator::reference Ref; //指针的引用
typedef typename Iterator::pointer Ptr; //结点指针

Iterator _it; //反向迭代器封装的正向迭代器

//构造函数
ReverseIterator(Iterator it)
:_it(it) //根据所给正向迭代器构造一个反向迭代器
{}

Ref operator*()
{
return *_it; //调用正向迭代器的operator*返回引用
}

Ptr operator->()
{
return _it.operator->(); //调用正向迭代器的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; 
}
};

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

Set的实现

都是接上红黑树的接口即可

namespace ljj
{
template<class K>
class set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:

//typename告诉编译器这一大坨是类型，不是静态变量
typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;

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

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

pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key);//调用红黑树的insert
}

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

Map的实现

map 也和 set 同理，复用红黑树的底层接口实现，此外还需要实现 [] 运算符的重载：

template<class K, class V>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
//typename告诉编译器这一大坨是类型，不是静态变量
typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;

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

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

pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);//调用红黑树的insert
}

//【】的底层调用就是Insert
V& operator[](const K& key)
{
pair<iterator, bool> ret = Insert(make_pair(K, V()));//插入成功就是当前的迭代器，失败就是之前的迭代器
return ret.first->second;
}
private:
RBTree<K, pair<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

红黑树的代码

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

template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;//三叉链
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;

//pair<K, V> _kv;//存储键值对
T _data;
Colour _col;//节点颜色

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

//正向迭代器
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)
{}

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;//同上
}

Self& operator++()
{
if (_node->_right)
{
//寻找该节点右子树中的最左节点
Node* left = _node->_right;
while (left->_left)
{
left = left->_left;
}
_node = left;//给给变成该节点
}
else
{
//找孩子在祖先左边的祖先
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_right) //判断parent不为空，空就崩了
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}

Self& operator--()
{
if (_node->_left)//结点的左子树不为空
{
//寻找该节点左子树中的最右节点
Node* right = _node->_left;
while (right->_right)
{
right = right->_right;
}
_node = right;//给给变成该节点
}
else//结点的左子树为空
{
//找孩子在祖先右边的祖先
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_left) //判断parent不为空，空就崩了
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
};


template<class K, class T, class KeyOfT>
struct RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef __RBTreeIterator<T, T&, T*> iterator;//正向迭代器

iterator begin()
{
//寻找最左节点
Node* left = _root;
while (left && left->_left)
{
left = left->_left;
}

//返回最左结点的正向迭代器
return iterator(left);
}

iterator end()
{
//返回空节点的迭代器
return iterator(nullptr);
}

//如果是空树，则插入节点作为root节点
pair<iterator, bool> Insert(const T& data)
{
KeyOfT kot;
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;//根节点必须是黑色
return make_pair(iterator(_root), true); //插入成功
}

//按二叉搜索树的插入方法，找到待插入位置
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (kot(data) > kot(cur->_data))//待插入结点的key值大于当前结点的key值
{
//往节点的右子树走
parent = cur;
cur = cur->_right;
}
else if (kot(data) < kot(cur->_data))//待插入结点的key值小于当前结点的key值
{
//往节点的左子树走
parent = cur;
cur = cur->_left;
}
else//插入的值等于当前的节点，返回失败
{
return make_pair(iterator(cur), false);
}
}

//将节点链接到树上
cur = new Node(data);//构造节点 
Node* newnode = cur;
cur->_col = RED;

if (kot(data) < kot(parent->_data))//判断链接左还是右？
{
//插入到左边
parent->_left = cur;
cur->_parent = parent;
}
else if (kot(data) > kot(parent->_data))
{
//插入到右边
parent->_right = cur;
cur->_parent = parent;
}

//如果插入节点的父节点是红色的，则需要对红黑树进行操作
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
assert(grandfather);
assert(grandfather->_col == BLACK);

//关键看叔叔  ~ 判断叔叔的位置
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//情况1：uncle存在且为红  + 继续往上处理
if (uncle && uncle->_col == RED)
{
//变色：p和u变黑，g变红
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;

//继续往上调整
cur = grandfather;
parent = cur->_parent;
}
else  //情况2 + 情况3：uncle不存在 + uncle存在且为黑
{
//情况二：单旋 + 变色
//    g
//  p   u
//c            
if (cur = parent->_left)
{
RotateR(grandfather);//右旋

//颜色调整
parent->_col = BLACK;
grandfather->_col = RED;
}
else//cur == parent->_right
{
//情况三：左右双旋 + 变色
//    g
//  p   u
//    c 
RotateL(parent);
RotateR(grandfather);

//调整颜色
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else  //parent == grandfather->_right
{
Node* uncle = grandfather->_left;
//情况1：uncle存在且为红 + 继续往上处理
if (uncle && uncle->_col == RED)
{
//变色：p和u变黑，g变红
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;

//继续往上调整
cur = grandfather;
parent = cur->_parent;
}
else  //情况2 + 情况3：uncle不存在 + uncle存在且为黑
{
//情况二：单旋 + 变色
//    g
//  u   p
//        c            
if (cur = parent->_right)
{
RotateL(grandfather);//左单 旋

//颜色调整
parent->_col = BLACK;
grandfather->_col = RED;
}
else//cur == parent->_left
{
//情况三：右左双旋 + 变色
//    g
//  u   p
//    c 
RotateR(parent);
RotateL(grandfather);

//调整颜色
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;//不管什么，最后根要变黑
return make_pair(iterator(newnode), true);
}

void InOrder()
{
_InOrder(_root);
cout << endl;
}

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

if (_root->_col == RED)
{
cout << "根节点不是黑色" << endl;
return false;
}

// 黑色节点数量基准值
int benchmark = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
++benchmark;

cur = cur->_left;//以最左的路径进行
}

return PrevCheck(_root, 0, benchmark);
}


private:
bool PrevCheck(Node* root, int blackNum, int& benchmark)
{
if (root == nullptr)
{
//cout << blackNum << endl;
//return;
if (benchmark == 0)
{
benchmark = blackNum;
return true;
}

if (blackNum != benchmark)
{
cout << "某条黑色节点的数量不相等" << endl;
return false;
}
else
{
return true;
}
}

if (root->_col == BLACK)
{
++blackNum;
}
//检测它的父亲
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "存在连续的红色节点" << endl;
return false;
}

return PrevCheck(root->_left, blackNum, benchmark)
&& PrevCheck(root->_right, blackNum, benchmark);
}

void _InOrder(Node* root)
{
if (root == nullptr)//空树也是红黑树
return;
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentParent = parent->_parent;

//建立subRL与parent之间的联系
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;

//建立parent与subR之间的联系
subR->_left = parent;
parent->_parent = subR;

//建立subR与parentParent之间的联系
if (parentParent == nullptr)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
{
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;

//建立subLR与parent之间的联系
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;

//建立parent与subL之间的联系
subL->_right = parent;
parent->_parent = subL;

//建立subL与parentParent之间的联系
if (parentParent == nullptr)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}

//左右双旋
void RotateLR(Node* parent)
{
RotateL(parent->_left);
RotateR(parent);
}

//右左双旋
void RotateRL(Node* parent)
{
RotateR(parent->_right);
RotateL(parent);
}

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
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
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465

📢写在最后