C++:平衡二叉搜索树之红黑树

一、红黑树的概念

红黑树， 和AVL都是二叉搜索树， 红黑树通过在每个节点上增加一个储存位表示节点的颜色， 可以是RED或者BLACK， 通过任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树能够确保没有一条路径会比其他路径长出两倍，因此红黑树是接近平衡的。

与AVL树相比，红黑树的插入和删除操作更具优势，因为红黑树是接近平衡的，AVL树是绝对平衡的， 因此插入删除等操作时，红黑树需要旋转的次数是比AVL树少的。

二、红黑树的性质

1. 每个节点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子节点是黑色的
4. 一条路径上没有连续的红色节点， 每条路径上黑色节点的数量是相同的

下面就是一个红黑树的示例：

根据红黑树的性质我们知道：一个红黑树中，最短路径 * 2 >= 最长路径

理论上：最短路径：全黑 最长路径：一黑一红交替

三、红黑树节点的定义

下面是红黑树节点的定义代码：

//节点的颜色定义
enum Colour
{
	RED,
	BLACK
};
//节点结构体
template<class K, class V>
struct RBTreeNode
{
	pair<K, V> _kv;//节点的数据
	RBTreeNode<K, V>* _left;//节点的左孩子
	RBTreeNode<K, V>* _right;//节点的右孩子
	RBTreeNode<K, V>* _parent;//节点的双亲节点
	Colour _col;//节点的颜色
    
    //节点的构造函数
	RBTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(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

四、红黑树的插入

红黑树是在二叉搜索树的基础上加上使其近似平衡的限制条件， 因此红黑树的插入可以分成以下两步：

1、按照二叉搜索树的性质插入新节点

2、检测新节点插入后，红黑树的性质是否遭到破坏

新节点的默认颜色是红色，因此，如果双亲节点是黑色就没有违反任何红黑树的性质，不需要调整，但是如果新插入节点的双亲节点是红色时， 就违反了不能有相连的红色节点的规则，此时需要对红黑树进行分情况讨论：

cur为当前节点， p为父节点， g为祖父节点， u为叔父节点

4.1情况一：cur 为红， p为红， g为黑， u存在且为黑

注意：这里的树，可能是一棵完整的树， 也可能是一个子树

此时abcde子树都为空

这个时候我们只需要进行变色处理， 将p 和 u节点变为黑色， 将g改为红色

调整完以后，如果g是根节点， 需要将g改为黑色， 因为红黑树的性质规定根节点的颜色必须是黑色。

如果g是子树，并且g的双亲节点是红色的话就需要继续向上调整， 如下图所示：

4.2情况二： cur为红， p为红， g为黑， u不存在/u存在且为黑

这里说明u的情况有两种：

1.u不存在， 此时cur一定是新增节点， 如果cur不是新增节点的话， 那么cur和p一定有一个节点的颜色是黑色， 但是那样就不满足每条路径黑色节点的数目相同这一性质。

p是g的左子节点， cur是p的左子节点， 那么就对g进行右单旋：

变色处理：p, g变色 – p变黑色， g变红色

p是g的右子节点， cur是p的右子节点， 那么就对g进行左单旋：

变色处理：p, g变色 – p变黑色， g变红色

p是g的左子节点， cur是p的右子节点，先对p进行左单旋， 再对g做右单旋：

变色处理：cur, g变色 – cur变黑色， g变红色

先进行左单旋；

再进行右单旋：

p是g的右子节点， cur是p的左子节点， 先对p进行右单旋， 再对g进行左单旋：

变色处理：cur， g变色 – cur变黑色， g变红色

先进行右单旋：

再进行左单旋：

2.u存在且为黑， 那么cur节点原来的颜色一定是黑色， 现在是红色的原因就是因为cur的子树在调整的过程中将cur的颜色更新成了红色。

p是g的左子节点， cur是p的左子节点， 那么就对g进行右单旋：

变色处理：p, g变色 – p变黑色， g变红色

p是g的右子节点， cur是p的右子节点， 那么就对g进行左单旋：

变色处理：p, g变色 – p变黑色， g变红色

p是g的左子节点， cur是p的右子节点，先对p进行左单旋， 再对g做右单旋：

变色处理：cur, g变色 – cur变黑色， g变红色

先进行左单旋：

再进行右单旋：

p是g的右子节点， cur是p的左子节点， 先对p进行右单旋， 再对g进行左单旋：

变色处理：cur， g变色 – cur变黑色， g变红色

先进行右单旋：

再进行左单旋：

左单旋代码实现：

//左单旋
	void RotateL(Node* parent)
	{
		Node* SubR = parent->_right;
		Node* SubRL = SubR->_left;
		parent->_right = SubRL;
		if (SubRL)
		{
			SubRL->_parent = parent;
		}

		Node* parentP = parent->_parent;
		SubR->_left = parent;
		parent->_parent = SubR;
		if (parentP == nullptr)
		{
			_root = SubR;
			SubR->_parent = nullptr;
		}
		else
		{
			if (parentP->_left == parent)
			{
				parentP->_left = SubR;
				SubR->_parent = parentP;
			}
			else
			{
				parentP->_right = SubR;
				SubR->_parent = parentP;
			}
		}

	}
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

右单旋代码实现：

//右单旋
	void RotateR(Node* parent)
	{
		Node* SubL = parent->_left;
		Node* SubLR = SubL->_right;
		parent->_left = SubLR;
		if (SubLR)
			SubLR->_parent = parent;

		Node* parentP = parent->_parent;
		SubL->_right = parent;
		parent->_parent = SubL;

		if (parentP == nullptr)
		{
			_root = SubL;
			SubL->_parent = nullptr;
		}
		else
		{
			if (parentP->_left == parent)
			{
				parentP->_left = SubL;
				SubL->_parent = parentP;
			}
			else
			{
				parentP->_right = SubL;
				SubL->_parent = parentP;
			}
		}
	}
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

插入函数整体代码实现：

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

		cur->_parent = parent;
		//处理
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			// g
			//p  u结构
			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//uncle不存在或者存在且为黑-》旋转加变色
				{
					if (cur == parent->_left)
					{
						//cur为parent的左子结点时进行右旋
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//双旋
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			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->_right)
					{
						//cur为父亲的右子节点时对g进行左单旋
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//双旋 -》 右左双旋
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_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
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

五、红黑树相关接口的实现

查找函数的实现：

依旧是根据二叉搜索树的查找规则：

//查找函数
	Node* Find(const K& key)
	{
		if (_root == nullptr)
			return nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else
				return cur;
		}

		return nullptr;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

容量高度相关：

返回有效节点个数：

//有效节点个数
	int Size()
	{
		_Size(_root);
	}

    int _Size(Node* root)
	{
		return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;
	}

1
2
3
4
5
6
7
8
9
10
11

二叉树高度：

//平衡二叉树高度
	int Height()
	{
		_Height(_root);
	}

    int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;

		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);

		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

中序遍历：

//中序遍历
	void Inorder()
	{
		_inorder(_root);
		cout << endl;
	}

    void _inorder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_inorder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_inorder(root->_right);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

六、红黑树的验证

我们要通过代码来验证我们所实现的红黑树是否是符合红黑树的性质的。

红黑树的验证分为以下两步：

1. 验证其是否满足二叉搜索树也就是中序遍历是否有序
2. 验证其是否满足红黑树的性质

验证代码：

1、验证是否为二叉搜索树：

//中序遍历
	void Inorder()
	{
		_inorder(_root);
		cout << endl;
	}

    void _inorder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_inorder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_inorder(root->_right);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2、验证是否满足红黑树的性质：

//判断是否为红黑树
	bool IsBalance()
	{
		if (_root == nullptr)
			return true;

		if (_root->_col == RED)
		{
			return false;
		}

		// 参考值
		int refNum = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++refNum;
			}

			cur = cur->_left;
		}

		return Check(_root, 0, refNum);
	}

    bool Check(Node* root, int blackNum, const int refNum)
	{
		if (root == nullptr)
		{
			//cout << blackNum << endl;
			if (refNum != blackNum)
			{
				cout << "存在黑色节点的数量不相等的路径" << endl;
				return false;
			}

			return true;
		}

		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << root->_kv.first << "存在连续的红色节点" << endl;
			return false;
		}

		if (root->_col == BLACK)
		{
			blackNum++;
		}

		return Check(root->_left, blackNum, refNum)
			&& Check(root->_right, blackNum, refNum);
	} 
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

通过以上几段代码就能完成对我们实现的红黑树验证。

七、红黑树与AVL数的比较

红黑树和AVL树都是平衡二叉搜索树， 进行增删查改的操作时的时间复杂度都是O(logN)， 红黑树不追求绝对平衡， AVL树追求绝对平衡，相对而言红黑树在维持平衡时的旋转次数要少于AVL树， 因此在经常进行插入和删除的结构中红黑树的性能一般要优于AVL树， 因此是实际中使用红黑树更多。

八、红黑树的应用

1. C++ STL库中的map/set 、mutil_map/mutil_set的实现
2. java库
3. linux内核

不止以上三处使用， 这里仅是为了举例。

---

关于红黑树的介绍到这里就结束了， 希望大家通过这篇文章能都红黑树有一定的理解， 以下是红黑树的具体代码实现链接：

红黑树具体实现代码