数据结构——红黑树_红黑树数据结构

数据结构——红黑树

前言

红黑树是map，set，mutilmap，mutilset容器的底层数据结构，也是一种非常重要的数据结构，它在效率上对AVL又做了进一步的优化，因为AVL结构在插入，或删除时，无法避免大量的旋转操作，导致效率有所损耗，但是红黑树，就在这一点有了更好的优化，但是牺牲了平衡性，所以是不是一个完全平衡的二叉搜索树。

一、红黑树的概念和性质

概念：

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

性质：
1、根节点是黑色的

2、每个节点不是红色的就是黑色的

3、红色节点的子节点一定是黑色的

4、红色节点不能相连

5、从任意节点出发，它每一条路径上的黑色节点数目是相同的

这里有一条总结红黑树的顺口溜：

一头一脚黑，
黑连红不连。
插入看叔伯，
删除看兄弟。

这四句话就概括了红黑树的所有性质，以及插入和删除时应该怎样处理的情况。

二、红黑树节点的定义

#include<iostream>
#include<stack>
#include<vector>
using namespace std;
enum Color{BLACK = 0,RED = 1};  //设置颜色

template<typename Type>    //类的前向声明，不然因为编译器版本原因可能在声明友元类的时候出错
class RBTree;

template<typename Type>
class RBTreeNode
{
	friend class RBTree<Type>;   //成为友元类，可以访问节点私有成员
public:
	RBTreeNode(Type val = Type())
		:_rightChild(nullptr),_leftChild(nullptr),_parent(nullptr),_Val(val),_color(RED)
	{}
	~RBTreeNode()
	{}
private:
	Type _Val;
	RBTreeNode<Type>* _rightChild;
	RBTreeNode<Type>* _leftChild;
	RBTreeNode<Type>* _parent;
	Color _color;
};

template<typename Type>
class RBTree
{
public:
	RBTree():Nul(_BuyNode()),_root(Nul)
	{
		Nul->_leftChild = Nul->_rightChild = Nul->_parent = nullptr;
		Nul->_color = BLACK;
	}
protected:
	RBTreeNode<Type>* _BuyNode(const Type val = Type())  
	{
		RBTreeNode<Type>* s = new RBTreeNode<Type>(val);
		s->_leftChild = s->_rightChild = Nul;
		return s;
	}
private:
	RBTreeNode<Type>* Nul;
	RBTreeNode<Type>* _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

我们有两个类，一个类是我们的红黑树类，另一个类是叶子节点类
红黑树类：
有两个成员，这里就有红黑树的另一个人为的看法，就是所有空节点，都为黑色节点，根一定是黑色节点，所以在初始化的时候我们不能没有根，初始化时一定要有一个黑色节点作为根节点，那么就有了为什么除了 _root以外还有一个节点作为空节点，所有空节点都指向这个节点。

然后呢，我们为了调整时方便，多使用了一个父指针，指向自己的父节点，因为不用这个的话，未来插入，删除都将变的超级麻烦！后面会有说到。

三、红黑树的旋转

这里我们就不需要再像AVL树一样写四个旋转方法了，因为初学，所以我们需要详细一点，现在我们直接选择同时调用左单旋和右单旋实现双旋转，这样就不需要重复实现了。提高了代码的复用性。

1.右单旋

因为我们在旋转之前就已经完成了颜色的修改，所以我们只需要进行单纯的旋转即可

template<typename Type>
void RBTree<Type>::RotateR(RBTreeNode<Type>*& t, RBTreeNode<Type>* p)
{
	RBTreeNode<Type>* s = p->_leftChild;
	/*判断即将要旋转的位置是否有左子树，有的话就将其挂在未来旋转过来的节点的右子树上
	  其次。如果没有，因为开头说过，所有节点的空节点，都指向了我们自己设置的空节点Nul，
	  所以只需要让p的右子树指向它就好了。*/
	if (s->_rightChild != Nul)
		s->_rightChild->_parent = p;
	p->_leftChild = s->_rightChild;
	s->_parent = p->_parent;
	
	if (p->_parent == Nul)   //被旋转的节点是根节点
		t = s;
	else if (p == p->_parent->_leftChild)  //不是根节点，判断是左子树还是右子树进行连接
		p->_parent->_leftChild = s; 
	else
		p->_parent->_rightChild = s;
		
	s->_rightChild = p;   //将节点的其他指针调整指向
	p->_parent = s;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

为什么这次不同于AVL树使用引用传需要被旋转的值呢，从代码可以知道，这次直接在旋转的同时完成了连接，具体步骤的意义会标识在代码中，这样看着比较方便。

2.左单旋

void RBTree<Type>::RotateL(RBTreeNode<Type>*& t, RBTreeNode<Type>* p)
{
	RBTreeNode<Type>* s = p->_rightChild;
	/*判断即将要旋转的位置是否有左子树，有的话就将其挂在未来旋转过来的节点的右子树上
	  其次。如果没有，因为开头说过，所有节点的空节点，都指向了我们自己设置的空节点Nul，
	  所以只需要让p的右子树指向它就好了。*/
	if (s->_leftChild != Nul)
		s->_leftChild->_parent = p;
	p->_rightChild = s->_leftChild;
	s->_parent = p->_parent;
	
	if (p->_parent == Nul)  //被旋转的节点是根节点
		t = s;
	else if (p == p->_parent->_leftChild) //不是根节点，判断是左子树还是右子树进行连接
		p->_parent->_leftChild = s;
	else
		p->_parent->_rightChild = s;
		
	s->_leftChild = p;  //将节点的其他指针调整指向
	p->_parent = s;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

四、红黑树的插入

template<typename Type>
void RBTree<Type>::_Insert(RBTreeNode<Type>* &t, const Type val)
{
	RBTreeNode<Type>* p = t;
	RBTreeNode<Type>* pr = Nul;
	while (p != Nul)    //寻找插入位置
	{
		if (val == p->_Val)  //不接受相同数据
			return;

		pr = p;

		if (val > p->_Val)
			p = p->_rightChild;
		else
			p = p->_leftChild;
	}

	p = _BuyNode(val);
	if (pr == Nul)  // 插入的是第一个根节点
	{
		t = p;
		t->_parent = pr;
	}

	if (val > pr->_Val)
		pr->_rightChild = p;
	else
		pr->_leftChild = p;
	p->_parent = pr;

	/*调整平衡*/
	In_balance(t, p);
}
template<typename Type>
void RBTree<Type>::In_balance(RBTreeNode<Type>*& t, RBTreeNode<Type>*& m)
{
	while (m->_parent->_color == RED)
	{
		RBTreeNode<Type>* u;   //uncle节点
		if (m->_parent == m->_parent->_parent->_leftChild)   //左分支
		{
			u = m->_parent->_parent->_rightChild;
			if (u->_color == RED)     //状况三   uncle为红色节点
			{
				m->_parent->_color = BLACK;
				m->_parent->_parent->_color = RED;
				u->_color = BLACK;
				m = m->_parent->_parent;
			}
			else    //uncle为黑色节点
			{
				if (m == m->_parent->_rightChild)  //状况二  
				{
					m = m->_parent;
					RotateL(t, m);
				}
				m->_parent->_color = BLACK;                  //状况一
				m->_parent->_parent->_color = RED;
				RotateR(t, m->_parent->_parent);
			}
		}
		else   //右分支
		{
			u = m->_parent->_parent->_leftChild;
			if (u->_color == RED)     //uncle为红色节点
			{
				//状况三  
				m->_parent->_color = BLACK;
				m->_parent->_parent->_color = RED;
				u->_color = BLACK;
				m = m->_parent->_parent;
			}
			else      //uncle为黑色节点
			{
				if (m == m->_parent->_leftChild)  //状况二  
				{
					m = m->_parent;
					RotateR(t, m);
				}
				m->_parent->_color = BLACK;                  //状况一
				m->_parent->_parent->_color = RED;
				RotateL(t, m->_parent->_parent);
			}
		}
	}
	t->_color = 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
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

寻找插入位置就不多说了，仔细看一下就会了，主要说一下调整平衡这里：

调整平衡的两种情况

一、uncle节点为黑色

uncle可能存在也可能不存在，无所谓，不存在的话在我们设置的时候也是指向我们自己设置的黑色空节点Nul

情况一 插入节点在外侧插入（单旋转）

我们只需要先将其父节点改为黑色，祖父节点改为红色，在进行单旋转即可达到平衡

情况二 插入节点在内侧插入（双旋转）

先将其进行一次单旋转，使其变成情况一，再通过情况一着色，旋转，达到平衡，这里有一个小细节，就是我们需要提前将m节点追到m的父节点，因为我们的目标就是要让其成为情况一，仔细看过旋转函数的同学一定都发现了，旋转完之后父节点会转下去，所以我们需要根据旋转函数体现追到父节点，使其旋转过后成为情况一

二、uncle节点为红色

这时我们的处理比较简单，我们只需要将其father节点和uncle节点的颜色改为黑色，grandfather节点的颜色改为红色，然后继续向上调整即可，这时又会转换成上面的情况一或者情况二，再根据相应的调整方式进行调整即可

五、红黑树的删除

template<class Type>
void RBTree<Type>::_Remove(RBTreeNode<Type>*& t, const Type val)
{
	RBTreeNode<Type>* p = t;
	while (p != Nul)            //寻找要被删除的节点
	{
		if (p->_Val == val)
			break;

		if (val > p->_Val)
			p = p->_rightChild;
		else
			p = p->_leftChild;
	}
	
	RBTreeNode<Type>* q;    

	if (p == Nul)   //被删除节点不存在
		return;
	 
	if (p->_leftChild != Nul && p->_rightChild != Nul)   //被删除节点有左右子树
	{
		q = p->_leftChild;

		while (q->_rightChild != Nul)
			q = q->_rightChild;

		p->_Val = q->_Val;
		p = q;
	}

	if (p->_leftChild != Nul)   //被删除节点只有一个子树
		q = p->_leftChild;
	else
		q = p->_rightChild;
	q->_parent = p->_parent;   //将q节点挂到被删除的节点的父节点的子树上

	if (q->_parent == Nul) // 被删除的是根节点
	{
		t = q;
		t->_color = BLACK;
		delete p;
		return;
	}
	
	if (p == p->_parent->_leftChild)    //父节点在对应的左树或者右树连接p的子树
		p->_parent->_leftChild = q;
	else
		p->_parent->_rightChild = q;
	
	/*调整平衡*/
	if (p->_color == BLACK)
	{
		if (q != Nul)   //组合四: 直接互换颜色，删除p节点即可
			q->_color = BLACK;
		else            //组合二
			Re_balance(t, q);
	}
	delete p;
}
template<class Type>
void RBTree<Type>::Re_balance(RBTreeNode<Type>*& t, RBTreeNode<Type>*& m)
{
	while (m != t)
	{
		RBTreeNode<Type>* b;
		if (m == m->_parent->_leftChild)     //左分支
		{
			b = m->_parent->_rightChild;

			/*———  情形四  ———*/
			if (b->_color == RED)    
			{
				b->_color = BLACK;
				m->_parent->_color = RED;
				RotateL(t, m->_parent);
				b = m->_parent->_rightChild;
			}

			/*———  情形三  ———*/
			if (b->_leftChild->_color != RED && b->_rightChild->_color != RED)  
			{
				b->_color = RED;
				if (m->_parent->_color == RED)
				{
					m->_parent->_color = BLACK;
					m = t;
				}
				else
					m = m->_parent;    //向上回溯，继续判断
			}
			else
			{
				/*———  情形二  ———*/
				if (b->_leftChild->_color == RED)  
				{
					b->_color = RED;
					b->_leftChild->_color = BLACK;
					RotateR(t, b);
					b = b->_parent;
				}
				/*———  情形一  ———*/
				b->_color = m->_parent->_color;
				m->_parent->_color = BLACK;
				b->_rightChild->_color = BLACK;
				RotateL(t, m->_parent);

				m = t;
			}
		}
		else   //右分支
		{
			b = m->_parent->_leftChild;

			/*———  情形四  ———*/
			if (b->_color == RED)
			{
				b->_color = BLACK;
				m->_parent->_color = RED;
				RotateR(t, m->_parent);
				m = m->_parent;
			}

			/*———  情形三  ———*/
			if (b->_leftChild->_color != RED && b->_rightChild->_color != RED)
			{
				b->_color = RED;
				if (m->_parent->_color = RED)
				{
					m->_parent->_color = BLACK;
					m = t;
				}
				else
					m = m->_parent;
			}
			else
			{
				/*———  情形二  ———*/
				if (b->_rightChild->_color == RED)
				{
					b->_color = RED;
					b->_rightChild->_color = BLACK;
					RotateL(t, b);
					b = b->_parent;
				}

				/*———  情形一  ———*/
				b->_color = m->_parent->_color;
				m->_parent->_color = BLACK;
				b->_leftChild->_color = BLACK;
				RotateR(t, m->_parent);

				m = t;
			}
		}
		t->_color = 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
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

如何寻找删除位置以及，被删除节点的子节点的处理，跟AVL树相同，都将其化成至多只有一个子树 或者 没有子树的情况，所以这里就不在多说，主要说一下，删除时，不同颜色，不同位置的节点，如何进行删除。

删除时会遇到的六种情况

情况一：
删除节点为RED节点，并且为叶子节点，那么直接删除即可

情况二：
删除节点为RED节点，只有一个叶子节点

解释：
这种情况是不存在的，不然会导致其违背红黑树的性质——每条路径上的黑色节点数目相同；又或者违背红黑树的性质——红色节点不能相连

情况三：
删除节点为BLACK节点，只有一个叶子节点

解释：
该节点的叶子节点颜色只能为RED，如果是BLACK节点，还是会违背红黑树的性质——每条路径上的黑色节点数目相同，所以，只能是RED叶子节点，那么直接将叶子节点颜色改为BLACK,用叶子节点代替被删除节点的位置，即可达到平衡

情况四、五
被删除节点有两个节点，这里被删除节点可能为RED或者BLACK
解释：
这里的替换寻找都与AVL树相同，这里节点颜色不一定就是这个样子，只是举例而已，所以不在多说，替换之后，情况四、五将转化成情况三 或者 情况六

情况六
删除节点为BLACK节点，且没有子节点。

这种情况下又有四种情形：

情形一：
被删除节点的brother节点有一个于其方向相同的子节点

解释：
先将father节点和brother节点的颜色互换，然后对father节点进行一次左旋转，然后将mine节点删除，就可以达到平衡。

情形二：
被删除节点的brother节点有一个于其方向相反的子节点

解释：
首先，先将brother节点与son节点颜色互换，然后对brother节点进行一次右旋转，这时，就变成了情形一，再进行情形一的操作，就可以达到平衡

情形三
brother节点没有红色子节点

解释：
当father节点为红色时，先将brother颜色改为红色然后将father节点颜色改为黑色，最后将mine节点删除即可达到平衡

解释：
这里细心的小伙伴可以看到，father节点从圆形变成了黑色，这里叫做“双重黑色”，它是我们假定的黑色，它并不是真实存在的，而是我们自己主观的想象，这种情况的出现是mine节点将自己的黑色给了father节点，这样我们就当作它平衡了，它黑色减少了，但是father本来就是黑色，然后现在有多了一重，所以是双重黑色，那么理所当然，我们需要删掉这个多余的黑色，所以需要将brother节点颜色改为红色然后继续向上回溯，继续调整平衡。

情况四
brother节点为红色

解释：
先将father和brother节点的颜色进行调整，然后对father节点进行左旋，这时，新的brother节点就是son节点，这就转化成brother节点为BLACK的情况，这样就可以转化成上面其他几种情况来进行响应的调整。

六、源代码

#include<iostream>
#include<stack>
#include<vector>
using namespace std;
enum Color { BLACK = 0, RED = 1 };  //设置颜色

template<typename Type>    //类的前向声明，不然因为编译器版本原因可能在声明友元类的时候出错
class RBTree;

template<typename Type>
class RBTreeNode
{
	friend class RBTree<Type>;   //成为友元类，可以访问节点私有成员
public:
	RBTreeNode(Type val = Type())
		:_rightChild(nullptr), _leftChild(nullptr), _parent(nullptr), _Val(val), _color(RED)
	{}
	~RBTreeNode()
	{}
private:
	Type _Val;
	Color _color;
	RBTreeNode<Type>* _rightChild;
	RBTreeNode<Type>* _leftChild;
	RBTreeNode<Type>* _parent;
};

template<typename Type>
class RBTree
{
public:
	RBTree() :Nul(_BuyNode()), _root(Nul)
	{
		Nul->_leftChild = Nul->_rightChild = Nul->_parent = nullptr;
		Nul->_color = BLACK;
	}
public:
	void Insert(Type val = Type())
	{
		_Insert(_root, val);
	}
	void Remove(Type val = Type())
	{
		_Remove(_root, val);
	}
protected:
	void _Insert(RBTreeNode<Type>*& t,const Type val);
	void In_balance(RBTreeNode<Type>*& t, RBTreeNode<Type>*& m);
	void _Remove(RBTreeNode<Type>*& t, const Type val);
	void Re_balance(RBTreeNode<Type>*& t, RBTreeNode<Type>*& m);
	void RotateL(RBTreeNode<Type>*& t, RBTreeNode<Type>* p);
	void RotateR(RBTreeNode<Type>*& t, RBTreeNode<Type>* p);
protected:
	RBTreeNode<Type>* _BuyNode(const Type val = Type())
	{
		RBTreeNode<Type>* s = new RBTreeNode<Type>(val);
		s->_leftChild = s->_rightChild = Nul;
		return s;
	}
private:
	RBTreeNode<Type>* Nul;
	RBTreeNode<Type>* _root;
};

template<typename Type>
void RBTree<Type>::RotateL(RBTreeNode<Type>*& t, RBTreeNode<Type>* p)
{
	RBTreeNode<Type>* s = p->_rightChild;
	if (s->_leftChild != Nul)
		s->_leftChild->_parent = p;
	p->_rightChild = s->_leftChild;
	s->_parent = p->_parent;
	if (p->_parent == Nul)
		t = s;
	else if (p == p->_parent->_leftChild)
		p->_parent->_leftChild = s;
	else
		p->_parent->_rightChild = s;
	s->_leftChild = p;
	p->_parent = s;
}
template<typename Type>
void RBTree<Type>::RotateR(RBTreeNode<Type>*& t, RBTreeNode<Type>* p)
{
	RBTreeNode<Type>* s = p->_leftChild;
	if (s->_rightChild != Nul)
		s->_rightChild->_parent = p;
	p->_leftChild = s->_rightChild;
	s->_parent = p->_parent;
	if (p->_parent == Nul)
		t = s;
	else if (p == p->_parent->_leftChild)
		p->_parent->_leftChild = s;
	else
		p->_parent->_rightChild = s;
	s->_rightChild = p;
	p->_parent = s;
}
template<typename Type>
void RBTree<Type>::_Insert(RBTreeNode<Type>* &t, const Type val)
{
	RBTreeNode<Type>* p = t;
	RBTreeNode<Type>* pr = Nul;
	while (p != Nul)    //寻找插入位置
	{
		if (val == p->_Val)  //不接受相同数据
			return;

		pr = p;

		if (val > p->_Val)
			p = p->_rightChild;
		else
			p = p->_leftChild;
	}

	p = _BuyNode(val);
	if (pr == Nul)  // 插入的是第一个根节点
	{
		t = p;
		t->_parent = pr;
	}

	if (val > pr->_Val)
		pr->_rightChild = p;
	else
		pr->_leftChild = p;
	p->_parent = pr;

	/*调整平衡*/
	In_balance(t, p);
}
template<typename Type>
void RBTree<Type>::In_balance(RBTreeNode<Type>*& t, RBTreeNode<Type>*& m)
{
	while (m->_parent->_color == RED)
	{
		RBTreeNode<Type>* u;   //uncle节点
		if (m->_parent == m->_parent->_parent->_leftChild)   //左分支
		{
			u = m->_parent->_parent->_rightChild;
			if (u->_color == RED)     //状况三   uncle为红色节点
			{
				m->_parent->_color = BLACK;
				m->_parent->_parent->_color = RED;
				u->_color = BLACK;
				m = m->_parent->_parent;
			}
			else    //uncle为黑色节点
			{
				if (m == m->_parent->_rightChild)  //状况二  
				{
					m = m->_parent;
					RotateL(t, m);
				}
				m->_parent->_color = BLACK;                  //状况一
				m->_parent->_parent->_color = RED;
				RotateR(t, m->_parent->_parent);
			}
		}
		else   //右分支
		{
			u = m->_parent->_parent->_leftChild;
			if (u->_color == RED)     //uncle为红色节点
			{
				//状况三  
				m->_parent->_color = BLACK;
				m->_parent->_parent->_color = RED;
				u->_color = BLACK;
				m = m->_parent->_parent;
			}
			else      //uncle为黑色节点
			{
				if (m == m->_parent->_leftChild)  //状况二  
				{
					m = m->_parent;
					RotateR(t, m);
				}
				m->_parent->_color = BLACK;                  //状况一
				m->_parent->_parent->_color = RED;
				RotateL(t, m->_parent->_parent);
			}
		}
	}
	t->_color = BLACK;
}
template<class Type>
void RBTree<Type>::_Remove(RBTreeNode<Type>*& t, const Type val)
{
	RBTreeNode<Type>* p = t;
	while (p != Nul)
	{
		if (p->_Val == val)
			break;

		if (val > p->_Val)
			p = p->_rightChild;
		else
			p = p->_leftChild;
	}
	
	RBTreeNode<Type>* q;    

	if (p == Nul)   //被删除节点不存在
		return;
	 
	if (p->_leftChild != Nul && p->_rightChild != Nul)   //被删除节点有左右子树
	{
		q = p->_leftChild;

		while (q->_rightChild != Nul)
			q = q->_rightChild;

		p->_Val = q->_Val;
		p = q;
	}

	if (p->_leftChild != Nul)   //被删除节点只有一个子树
		q = p->_leftChild;
	else
		q = p->_rightChild;
	q->_parent = p->_parent;   //将q节点挂到被删除的节点的父节点的子树上

	if (q->_parent == Nul) // 被删除的是根节点
	{
		t = q;
		t->_color = BLACK;
		delete p;
		return;
	}
	
	if (p == p->_parent->_leftChild)    //父节点在对应的左树或者右树连接p的子树
		p->_parent->_leftChild = q;
	else
		p->_parent->_rightChild = q;
	
	/*调整平衡*/
	if (p->_color == BLACK)
	{
		if (q != Nul)   //组合四: 直接互换颜色，删除p节点即可
			q->_color = BLACK;
		else            //组合二
			Re_balance(t, q);
	}
	delete p;
}
template<class Type>
void RBTree<Type>::Re_balance(RBTreeNode<Type>*& t, RBTreeNode<Type>*& m)
{
	while (m != t)
	{
		RBTreeNode<Type>* b;
		if (m == m->_parent->_leftChild)     //左分支
		{
			b = m->_parent->_rightChild;

			/*———  情形四  ———*/
			if (b->_color == RED)    
			{
				b->_color = BLACK;
				m->_parent->_color = RED;
				RotateL(t, m->_parent);
				b = m->_parent->_rightChild;
			}

			/*———  情形三  ———*/
			if (b->_leftChild->_color != RED && b->_rightChild->_color != RED)  
			{
				b->_color = RED;
				if (m->_parent->_color == RED)
				{
					m->_parent->_color = BLACK;
					m = t;
				}
				else
					m = m->_parent;    //向上回溯，继续判断
			}
			else
			{
				/*———  情形二  ———*/
				if (b->_leftChild->_color == RED)  
				{
					b->_color = RED;
					b->_leftChild->_color = BLACK;
					RotateR(t, b);
					b = b->_parent;
				}
				/*———  情形一  ———*/
				b->_color = m->_parent->_color;
				m->_parent->_color = BLACK;
				b->_rightChild->_color = BLACK;
				RotateL(t, m->_parent);

				m = t;
			}
		}
		else   //右分支
		{
			b = m->_parent->_leftChild;   //兄弟节点

			/*———  情形四  ———*/
			if (b->_color == RED)
			{
				b->_color = BLACK;
				m->_parent->_color = RED;
				RotateR(t, m->_parent);
				m = m->_parent;
			}

			/*———  情形三  ———*/
			if (b->_leftChild->_color != RED && b->_rightChild->_color != RED)
			{
				b->_color = RED;
				if (m->_parent->_color = RED)
				{
					m->_parent->_color = BLACK;
					m = t;
				}
				else
					m = m->_parent;
			}
			else
			{
				/*———  情形二  ———*/
				if (b->_rightChild->_color == RED)
				{
					b->_color = RED;
					b->_rightChild->_color = BLACK;
					RotateL(t, b);
					b = b->_parent;
				}

				/*———  情形一  ———*/
				b->_color = m->_parent->_color;
				m->_parent->_color = BLACK;
				b->_leftChild->_color = BLACK;
				RotateR(t, m->_parent);

				m = t;
			}
		}
		t->_color = BLACK;
	}
}
int main()
{
	RBTree<int> Rb;
	vector<int> iv = { 10, 7,  8, 15, 5, 6, 11, 13, 12 };
	for (int i = 0; i < iv.size(); ++i)
	{
		Rb.Insert(iv[i]);
	}

	Rb.Remove(11);
	Rb.Remove(13);
	Rb.Remove(8);
	Rb.Remove(12);
	Rb.Remove(6);

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