[C++][数据结构]红黑树的介绍和模拟实现

前言

之前我们简单学习了一下搜索树和平衡搜索树，今天我们来学习一下红黑树

简介

概念

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

性质

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

实现

基本结构

我们默认新插入的节点为红色，因为根据第四条规则，黑色节点不能轻易添加

template<class K, class V>
struct RBTreeNode
{
	using Node = RBTreeNode<K, V>;
	Node* _left;
	Node* _right;
	Node* _parent;
	pair<K, V> _kv;
	Color _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

插入

插入节点最终的颜色的关键是看叔叔节点

1. 原因：
   我的父节点是红的，那我的爷爷节点一定是黑的，并且爷爷一定存在（因为根节点不为红色），所以就是看叔叔节点的颜色来判断插入结点的颜色

2. 修改原则：
   a. 叔叔存在且为红，则将父节点和叔叔节点变黑再将爷爷节点变红，

   • 更新cur节点为爷爷节点，直到更新到根节点

b. 叔叔为黑或叔叔不存在

• 叔叔不存在，说明cur是新增的节点，直接就是红色
• 叔叔为黑，那么cur不可能是新增，不然parent不满足第四条规则

针对第二点，我们需要考虑会不会最长路径超出最短路径的二倍或者面临下面这种情况（出现连续的红色节点且无法修改），那么这里我们就必须要进行旋转+变色。
（与AVL的旋转相同）
（好像有个小规律：parent始终为黑色）

旋转的规则：
p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，
p为g的右孩子，cur为p的右孩子，则进行左单旋转
p变黑，g变红

c. cur为红，p为红，g为黑，u不存在/u为黑
更新规则：

• p为g的左孩子，cur为p的右孩子：左右双旋+变色
• p为g的右孩子，cur为p的左孩子：右左双旋+变色

bool Insert(const pair<K, V>& kv)
{
	
	//1.按照搜索树规则插入：先找到合适的位置，然后链接
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_root->_col = BLACK;
		return true;
	}//如果树为空，特殊判断

	Node* parent = nullptr;
	Node* cur = _root;
	while (cur != nullptr)
	{
		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);		//默认新节点是红色
	if (parent->kv.first > kv.first)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_right = cur;
	}
	cur->_parent = parent;

	//持续更新parent，直到更新到根节点
	while (parent && parent->_col == RED)
	{
		Node* grandfather = parent->_parent;
		//根据父亲，找叔叔
		if (parent == grandfather->_left)
		{
			Node* uncle = grandfather->_right;
			//情况一：叔叔存在且为红
			if (uncle != nullptr && uncle->_col == RED)
			{
				//变色
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				//更新节点
				cur = grandfather;
				parent = cur->_parent;
			}
			//情况二：叔叔不存在或者为黑
			else
			{
				if (cur == parent->_left)
				{
					//       g
					//    p    u
					// c
					RotateR(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else
				{
					//       g
					//    p     u
					//      c
					RotateL(parent);
					RotateR(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;
			}
		}
		else
		{
			Node* uncle = grandfather->_left;
			if (uncle != nullptr && uncle->_col == RED)
			{
				//变色
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				//更新节点
				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				//结构图
				//      g
				//   u     p
				//            c
				if (cur == parent->_right)
				{
					RotateL(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else
				{
					//		g
					//   u     p
					//      c
					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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

验证

要验证这棵树是不是红黑树，要根据他的规则去判断

1. 根节点是黑色的
2. 不能有连续的红色节点
3. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点

所以我们可以根据这三点去判断

	bool Check(Node* cur)
	{
		if (cur == nullptr)
			return true;

		if (cur->_col == RED && cur->_parent->_col == RED)
		//第二点
		//根据孩子找父亲
		{
			cout << cur->_kv.first << "存在连续的红色节点" << endl;
			return false;
		}

		return Check(cur->_left)
			&& Check(cur->_right);
	}

	bool IsBalance()
	{
		if (_root && _root->_col == RED)
			return false;
		//第一点

		return Check(_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

以上是对于第一点和第二点的验证，对于第三点，我们要求每两条路径的黑色节点数量，判断是否相等，
我们可以用老方法：增加参数个数

	bool Check(Node* cur, int blackNum, int refBlackNum)
	{
		if (cur == nullptr)
		{
			if (refBlackNum != blackNum)
			{
				throw("黑色节点的数量不相等");
			}
			return true;
		}

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

		if (cur->_col == BLACK)
			++blackNum;
		
		return Check(cur->_left, blackNum, refBlackNum)
			&& Check(cur->_right, blackNum, refBlackNum);
	}

	bool IsBalance()
	{
		if (_root && _root->_col == RED)
			return false;

		int refBlackNum = 0;
		Node* cur = _root;
		while (cur)
		{
			if(cur->_col == BLACK)
				refBlackNum++;

			cur = cur->_left;
		}

		return Check(_root, 0, refBlackNum);
	}
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

结语

红黑树的实现还没写完，下一篇文章会介绍红黑树的迭代器的简单实现和map和set是如何封装的 ，下次见~