数据结构与算法--红黑树

Posted on

1 引言

  红黑树是树的数据结构中最为重要的一种。Java的容器TreeSet、TreeMap均使用红黑树实现。JDK1.8中HashMap中也加入了红黑树。C++ STL中的map和set同样使用红黑树实现。之前的文章已经详细介绍了2-3-4树的性质与操作。本篇文章将从2-3-4树与红黑树关系出发，详细阐明红黑树。
  2-3-4树和红黑树是完全等价的，但是2-3-4树的编程实现相对复杂，所以一般是通过实现红黑树来实现替代2-3-4树，而红黑树也同样保证在O(logN)的时间内完成查找、插入和删除操作。

2 定义

  红黑树是每个节点都带有颜色属性的平衡二叉查找树 ，颜色为红色或黑色。除了二叉查找树一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:

（1）节点是要么红色或要么是黑色。
（2）根一定是黑色节点。
（3）每个叶子节点都带有两个空的黑色节点（称之为NIL节点，它又被称为黑哨兵）。
（4）每个红色节点的两个子节点都是黑色（或者说从每个叶子到根的所有路径上不能有两个连续的红色节点）。
（5）从任一节点到它所能到达得叶子节点的所有简单路径都包含相同数目的黑色节点。

例如：图2.1所示的一棵红黑树：
图2.1

图2.1

定义节点名称：
父节点——P(Parent)
祖父节点——G(GrandParent)
叔叔节点——U(Uncle)
当前节点——C(Current)
兄弟节点——B(Brother)
左孩子——L(Left)
右孩子——R(Right)

3 性质

  根节点到任意叶子节点的路径长度，最多相差一半。若树存在最短路径，则最短路径上均为黑色节点，那么第五条性质保证根节点到达最长路径与最短路径所包含的黑色节点数目相同，若最短路径长为N，则最长路径M=N+红色节点数目，性质4要求红色节点必定不连续，因此红色节点数目最多为N，则最长路径与最短路径最多相差N。

4 2-3-4树和红黑树的等价关系

  如果一棵树满足红黑树，把红色节点收缩到其父节点，就变成了2-3-4树，所有红色节点都与其父节点构成3或4节点，其它节点为2节点。一颗红黑树对应唯一形态的2-3-4树，但是一颗2-3-4树可以对应多种形态的红黑树（主要是3节点可以对应两种不同的红黑树形态）。

例如：

img
img

5 查找

红黑树的查找操作与二叉搜索树查找方式一致，这里不再赘述。

6 插入

6.1 插入节点的父节点为黑色

  若待插入节点的父节点为黑色，则直接插入节点，并将插入的节点涂红，插入结束。父节点为黑色，插入红色节点并不会使红黑树违背5条性质。
此种情形对应的在2-3-4树中的插入操作为：待插入位置的节点为2-节点或者3-节点，直接插入节点。
图解：
img

6.2 插入节点的父节点为红色，叔叔节点为黑色

  若待插入节点的父节点为红色，叔叔节点为黑色，此种情形又需要区分节点的插入位置，根据插入位置的不同进行相应的调整。此种情形共有四种：

6.2.1 父节点P为G左孩子，插入位置为左孩子

  若待插入节点C的父节点P是祖父节点G的左孩子，并且插入节点的位置位于父节点P的左孩子。调整过程如下：

图解：
  1：插入后违背性质4，首先以祖父节点G为中心，执行右旋操作。
img
  2：右旋操作结束，将父节点P涂黑色，祖父节点G涂红色，调整完毕。
img

6.2.2 父节点P为G左孩子，插入位置为右孩子

  若待插入节点C的父节点P是祖父节点G的左孩子，并且插入节点的位置位于父节点P的右孩子。调整过程如下：

图解：
  1：插入后违背性质4，首先以父节点P为中心，执行左旋操作。
img
  2：左旋操作结束后，仍然违背性质4，此时的情形符合6.2.1。在以节点G为中心，执行右旋操作。右旋结束后，将节点C涂黑色，节点G涂红色，调整完毕。
img

6.2.3 父节点P为G右孩子，插入位置为右孩子

  若待插入节点C的父节点P是祖父节点G的右孩子，并且插入节点的位置位于父节点P的右孩子。此种情形是6.2.1情形的镜像。调整过程如下：

图解：
  1：插入后违背性质4，首先以祖父节点G为中心，执行左旋操作。
img
  2：左旋操作结束，将父节点P涂黑色，祖父节点G涂红色，调整完毕。
img

6.2.4 父节点P为G右孩子，插入位置为左孩子

  若待插入节点C的父节点P是祖父节点G的右孩子，并且插入节点的位置位于父节点P的左孩子。此种情形是6.2.2的镜像。调整过程如下：

图解：
  1：插入后违背性质4，首先以父节点P为中心，执行右旋操作。
img
  2：右旋操作结束后，仍然违背性质4，此时的情形符合6.2.3。在以节点G为中心，执行左旋操作。左旋结束后，将节点C涂黑色，节点G涂红色，调整完毕。
img

6.3 插入节点的父节点为红色，叔叔节点为红色

  若待插入节点C的父节点P为红色，且叔叔节点U为红色，则需要根据插入位置的不同，做出相应的调整。此种情形共有两种：

6.3.1 插入位置为左子树

img

6.3.2 插入位置为右子树

img
img

7 删除

7.1 删除红色叶子节点

图解：

img

7.2 删除红色节点，只有左子树或只有右子树

图解：
img

7.3 删除红色节点，既有左子树又有右子树

  如果要删除的节点不是叶子节点，用要删除节点的后继节点替换（只进行数据替换即可，颜色不变，此时也不需要调整结构），然后删除后继节点，后继节点的删除同样要遵循红黑树的删除过程。

7.4 删除的黑色节点仅有左子树或者仅有右子树

图解：
img
img

图中填充为绿色的节点代表既可以是红色也可以是黑色，下同。

7.5 删除黑色的叶子节点

删除黑色的叶子节点情况相对复杂，主要分为8种情况：

情形1：节点D的兄弟节点B为红色，且D是左孩子。

图解：
img
img

情形2：节点D的兄弟节点B为红色，且D是右孩子。

图解：
img
img

情形3：D为左孩子，D兄弟节点B为黑色，且远侄子节点为红色。

图解：
img
img

情形4：D为右孩子，D兄弟节点B为黑色，且远侄子节点为红色。

图解：
img
img

情形5：D为左孩子，兄弟节点B为黑色，远侄子节点为黑色，近侄子节点为红色。

图解：
img
img
img

情形6：D为右孩子，兄弟节点B为黑色，远侄子节点为黑色，近侄子节点为红色。

图解：
img
img
img

情形7：父节点P为红色，兄弟节点B和兄弟节点的两个孩子（只能是NIL节点）都为黑色的情况。

图解：
img

情形7对应2-3-4树删除操作中兄弟节点为2节点，父节点至少是个3节点，父节点key下移与兄弟节点合并。

情形8：父节点P，兄弟节点B和兄弟节点的两个孩子（只能为NIL节点）都为黑色的情况。

图解：
img
  情形8对应2-3-4树删除操作中兄弟节点为2节点，父亲节点也为2节点，父节点key下移与兄弟节点合并，已父节点看成新的节点D，继续回溯。

代码实现

RBTree.h

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
#pragma once

enum Color
{
	RED,
	BLACK
};

template<class K,class V>
struct RBTreeNode
{
	K key;
	V value;
	Color color;	//颜色
	RBTreeNode<K, V>* left;		//指向左孩子的指针
	RBTreeNode<K, V>* right;	//指向右孩子的指针
	RBTreeNode<K, V>* parent;	//指向父节点的指针

	RBTreeNode(const K& key=K(), const V&value=V())
		:key(key)
		, value(value)
		, color(RED)
		, left(NULL)
		, right(NULL)
		, parent(NULL)
	{}
};

template<class K,class V>
class RBTree
{
public:
	RBTree()
		:root(NULL)
	{}
	bool Insert(const K& key, const V& value);
	void InOrder()
	{
		InOrder(root);
		cout << endl;
	}
	bool Check();
protected:
	//左旋
	void RotateL(RBTreeNode<K, V>*& parent);
	//右旋
	void RotateR(RBTreeNode<K, V>*& parent);
	//中序遍历并打印
	void InOrder(RBTreeNode<K, V>* root);
	//检验红黑树的合法性
	bool CheckRBTree(RBTreeNode<K, V>* root, int blackNum,int CBNum);
protected:
	RBTreeNode<K, V>*root;
};

template<class K, class V>
bool RBTree<K, V>::Insert(const K& key, const V& value)
{
	if (root == NULL)
	{
		root = new RBTreeNode<K, V>(key, value);
		root->color = BLACK;
		return true;
	}
	//	找位置
	RBTreeNode<K, V>* cur = root;
	RBTreeNode<K, V>* parent = NULL;
	while (cur)
	{
		if (cur->key > key)
		{
			parent = cur;
			cur = cur->left;
		}
		else if (cur->key < key)
		{
			parent = cur;
			cur = cur->right;
		}
		else
		{
			return false;
		}
	}
	//插入
	cur = new RBTreeNode<K, V>(key, value);
	cur->parent = parent;
	if (parent->key > key)
		parent->left = cur;
	else if (parent->key < key)
		parent->right = cur;
	
	//检查颜色分配是否满足要求
	while (parent&&parent->color==RED)
	{
		RBTreeNode<K, V>* grandfather = parent->parent;
		if (parent == grandfather->left)
		{
			RBTreeNode<K, V>* uncle = grandfather->right;
			if (uncle&&uncle->color == RED)
			{	//第一种情况  变色
				grandfather->color = RED;
				parent->color =BLACK;
				uncle->color = BLACK;
				
				cur = grandfather;
				parent = grandfather->parent;
			}
			else if( (uncle&&uncle->color==BLACK)||uncle==NULL)
			{	
				if (cur == parent->left)
				{//第二种情况 右单旋		cur必然有黑色孩子
					parent->color = BLACK;
					grandfather->color = RED;
					RotateR(grandfather);
				}
				else
				{//第三种情况 左右双旋
					RotateL(parent);
					parent->color = BLACK;
					grandfather->color = RED;
					RotateR(grandfather);
				}
				break;
			}
		}
		else if (parent == grandfather->right)
		{
			RBTreeNode<K, V>* uncle = grandfather->left;
			if (uncle&&uncle->color == RED)
			{//第一种情况 变色
				grandfather->color = RED;
				parent->color = BLACK;
				uncle->color = BLACK;
				
				cur = grandfather;
				parent = cur->parent;
			}
			else if( (uncle&&uncle->color == BLACK)||uncle==NULL)
			{//第二种情况 左单旋 cur必然有黑孩子
				if (cur == parent->right)
				{
					parent->color = BLACK;
					grandfather->color = RED;
					RotateL(grandfather);
				}
				else if (cur==parent->left)
				{//第三种情况 右左双旋
					RotateR(parent);
					parent->color = BLACK;
					grandfather->color = RED;	
					RotateL(grandfather);
				}
				break;
			}
		}
	}
	root->color = BLACK;
	return true;
}
template<class K, class V>
void RBTree<K, V>::RotateL(RBTreeNode<K, V>*& parent)
{
	RBTreeNode<K, V>* ppNode = parent->parent;
	RBTreeNode<K, V>* subR = parent->right;
	RBTreeNode<K, V>* subRL = subR->left;

	parent->right = subRL;
	if (subRL) subRL->parent = parent;

	subR->left = parent;
	parent->parent = subR;

	if (ppNode == NULL)
	{
		subR->parent = NULL;
		root = subR;
	}
	else
	{
		subR->parent = ppNode;
		if (ppNode->left == parent)
			ppNode->left = subR;
		else if (ppNode->right == parent)
			ppNode->right = subR;
	}
	parent = subR;
}
template<class K, class V>
void RBTree<K, V>::RotateR(RBTreeNode<K, V>*& parent)
{
	RBTreeNode<K, V>* ppNode = parent->parent;
	RBTreeNode<K, V>* subL = parent->left;
	RBTreeNode<K, V>* subLR = subL->right;

	parent->left = subLR;
	if (subLR) subLR->parent = parent;

	subL->right = parent;
	parent->parent = subL;

	if (ppNode==NULL)
	{
		subL->parent = NULL;
		root = subL;
	}
	else
	{
		subL->parent = ppNode;
		if (parent == ppNode->left)
			ppNode->left = subL;
		else
			ppNode->right = subL;
	}
	parent = subL;
}
template<class K, class V>
void RBTree<K, V>::InOrder(RBTreeNode<K, V>* root)
{
	if (root == NULL)
		return;
	InOrder(root->left);
	cout << root->key << " ";
	InOrder(root->right);

}

//检验红黑树的合法性
template<class K, class V>
bool RBTree<K, V>::Check()
{
	//统计红黑树每条路径上黑色节点的数量
	int blackNum = 0;
	RBTreeNode<K, V>* cur = root;
	while (cur)
	{
		if (cur->color == BLACK)
			blackNum++;
		cur = cur->left;
	}
	int CBNum = 0;
	return CheckRBTree(root,blackNum,CBNum);
}
template<class K, class V>
bool RBTree<K, V>::CheckRBTree(RBTreeNode<K, V>* root, int blackNum, int CBNum)
{
	if (root == NULL)
		return true;
	if (root->color == BLACK)
	{
		CBNum++;
		if (root->left == NULL&&root->right == NULL)
		{	//走到了叶子节点 将该条路径上的黑色节点数量与之前统计的黑色节点数量做比较
			if (blackNum == CBNum)
			{
				return true;
			}
			else
			{
				cout << "叶子节点为" << root->key << "路径的黑色节点数目与最左侧支路的黑色节点数目不相等 ！" << endl;
				return false;
			}
		}
	}
	else if (root->parent&&root->parent->color == RED)
	{//判断是否存在连续的两个红色节点
		cout << root->parent->key << " 和 " << root->key << " 为两个连续的红色节点" << endl;
		return false;
	}
	//递归检验子路
	return CheckRBTree(root->left, blackNum, CBNum) && CheckRBTree(root->right, blackNum, CBNum);
}

main.cpp

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
#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
using namespace std;
#include"RBTree.h"

void TestRBTree()
{
	int array[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15, 20, 100,0,1,2,5};
	RBTree<int, int> tree;
	for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++)
	{
		tree.Insert(array[i], i);
	}

	tree.InOrder();
	bool ret=tree.Check();
	if (ret == true)
		cout << "RBTree is in Balanced !" << endl;
	else
		cout << "RBTree not in a state of balance !" << endl;

}

int main()
{
	TestRBTree();
	system("pause");
	return 0;
}
Rick Smith