深入剖析红黑树：优雅地平衡二叉搜索树

一.红黑树的概念

在之前的学习中，我们了解了二叉搜索平衡树，AVL树通过控制每个结点中的平衡因子的绝对值不超过1，实现了一个高性能的树。而相较于AVL的高度平衡，红黑树觉得AVL为了平衡也付出了代价（插入和删除时进行了多次旋转），所以红黑树在控制平衡上面没有这么严格，只是要求，最长路径不超过最短路径的二倍。那红黑树又是如何控制实现的呢？接下来了解一下红黑树的性质：

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

二.插入操作

在我们了解红黑树的性质后，就需要分析相关代码看他如何实现的。首先我们看红黑树结点的定义:
因为map和set的底层使用红黑树实现了，为了之后方便，这里红黑树用了两个模板参数。

#include 

using namespace std;

enum Colour
{
	RED, BLACK
};

template<class K,class V>
class RBTreeNode
{
public:
	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)
	{}
};
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

结点定义中与AVL树差距不大，只是多了个用枚举定义的参数，用来指定是红结点还是黑结点。接下来讲解重点的插入操作：
首先因为红黑树也是二叉搜索树，所以要满足二叉搜索树的基本性质，再者是我们插入的结点的颜色先置为什么能让后面的调整更方便呢。如果黑色需要在后面依据性质4调整，插入红色的话依据性质3调整。明显是4更为复杂，所以我们插入颜色为红色。

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)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (kv.first < cur->_kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}
	cur = new Node(kv);
	cur->_col = RED;

	if (parent->_kv.first > cur->_kv.first)
	{
		parent->_left = cur;
	}
	else
	{
		parent->_right = cur;
	}
	cur->_parent = parent;
	///开始调整颜色
	///开始调整颜色
	_root->_col = BLACK;
	return true;
}
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

上段代码是不涉及调整颜色，只保证二叉搜索树性质。下面开始分类讨论研究如何调整颜色。

如上图所示，插入的cur结点是红色，这时出现了连续的两个红结点，所以就要进行调整。如果parent结点是黑色则不需要调整。我们把10结点和20结点称为parent和grandfather结点，22为uncle结点。
1.当uncle结点为红色时，变色然后继续向上调整

2.当uncle结点不存在时或者为黑时的处理方式相同：

完整代码如下:

	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)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);
		cur->_col = RED;

		if (parent->_kv.first > cur->_kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;//叔叔存在且为红
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else // 叔叔不存在或者为黑都是旋转＋变色
				{
					if (cur == parent->_left)
					{
						RevoR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RevoL(parent);
						RevoR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
				}
			}
			else
			{
				Node* uncle = grandfather->_left;//叔叔存在且为红
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else // 叔叔不存在或者为黑都是旋转＋变色
				{
					if (cur == parent->_left)
					{
						RevoR(parent);
						RevoL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RevoL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
				}
			}
		}

		_root->_col = BLACK;
		return true;
	}
	void RevoL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;
		parent->_right = curleft;//无论curleft是否为空都要执行这一步

		if (curleft)
		{
			curleft->_parent = parent;
		}
		cur->_left = parent;
		Node* ppnode = parent->_parent;
		parent->_parent = cur;

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

			}
			cur->_parent = ppnode;
		}

	}

	void RevoR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;
		parent->_left = curright;

		if (curright)
		{
			curright->_parent = parent;
		}
		cur->_right = parent;
		Node* ppnode = parent->_parent;
		parent->_parent = cur;
		if (_root == parent)//等价于 ppnode == nullptr
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			cur->_parent = ppnode;
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
			}
			else
			{
				ppnode->_right = 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
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

三.与AVL树的比较

红黑树和AVL树的插入效率O(logN)，只是红黑树不像AVL追求如此平衡，所以旋转次数会少，并且实现也较简单。所以在实践中大都使用红黑树。之后我们还是使用红黑树模拟实现map和set。