红 黑 树

一、红黑树的概念

在 AVL 树中删除一个结点，旋转可能要持续到根结点，此时效率较低

红黑树也是一种二叉搜索树，通过在每个结点中增加一个位置来存储红色或黑色，并对结点的着色进行限制，使得该二叉搜索树的最长路径不超过最短路径的两倍，即红黑树是一颗近似平衡的二叉搜索树，他不像 AVL 树的平衡那么严格，所以红黑树在插入和删除时，也不需要大量的旋转，并且搜索效率差不了 AVL 多少

红黑树是一颗二叉搜索树并且满足如下规则：

• 每个节点不是红色就是黑色
• 根结点是黑色的
• 每个红结点的左右孩子一定是黑色
• 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点
• 叶结点都是黑色的(这里的叶结点指的是空节点)

根据上述规则可以得到：最短路径：全黑结点的路径，最长路径：一黑一红的路径，所以红黑树可以保证最长路径不超过最短路径的一半

二、红黑树的实现

1. 红黑树的存储结构

// 结点的颜色
enum Color { RED, BLACK };

// 红黑树的结点
template<class K, class V>
struct RBTreeNode
{
	std::pair<K, V> _kv;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	Color _color;	// 结点的颜色

	RBTreeNode<K, V>(const std::pair<K, V>& kv = std::pair<K, V>(K(), V()))
		: _kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _color(RED)	// 为了方便树的结构调整，新结点默认为红色
	{}
};

// 红黑树
template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	RBTree<K, V>()
		: _root(nullptr)
	{}

private:
	Node* _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

2. 红黑树的插入

首先按照二叉搜索树的方式插入结点，保证插入结点之后还是二叉搜索树，为了方便树的结构调整，插入结点默认为为红色，当插入结点完成之后，可能会违反红黑树的性质，此时有三种情况

• 插入结点的父节点是黑色：没有违反红黑树的性质

• 插入结点的父节点是红色，叔节点存在且为红：违反了红黑树的性质，此时需要对父节点和爷爷结点进行变色

由于父节点是红色的，所以爷爷结点一定存在且为黑，变色完之后，如果 g 结点是根结点，则将 g 结点变为黑色，否则将 g 结点所在的子树当做新插入的结点，继续向上调整

• 插入结点的父节点是红色，叔节点不存在或存在且为黑：违反了红黑树的性质，此时需要对爷爷结点所在的子树进行旋转然后再对结点进行变色

由于父节点是红色的，所以爷爷结点一定存在且为黑，变色完之后，子树的根结点是黑色的，不用继续向上调整

u 存在且为黑的情况，一定是由 u 存在且为红的情况继续向上调整而来的

// 右旋
void RotateR(Node* parent)
{
	Node* pparent = parent->_parent;
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	parent->_left = subLR;
	if (subLR) subLR->_parent = parent;

	subL->_right = parent;
	parent->_parent = subL;

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

// 左旋
void RotateL(Node* parent)
{
	Node* pparent = parent->_parent;
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	parent->_right = subRL;
	if (subRL) subRL->_parent = parent;

	subR->_left = parent;
	parent->_parent = subR;

	if (pparent == nullptr) _root = subR;
	else
	{
		if (pparent->_left == parent) pparent->_left = subR;
		else pparent->_right = subR;
	}
	subR->_parent = pparent;
}
		
// 插入
bool Insert(const std::pair<K, V>& kv)
{
	// 按照二叉搜索树的方式插入结点，保证该树插入结点之后还是二叉搜索树
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_root->_color = BLACK;
		return true;
	}

	Node* parent = nullptr;
	Node* cur = _root;
	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);
	if (parent->_kv.first > kv.first) parent->_left = cur;
	else parent->_right = cur;

	cur->_parent = parent;

	// 更新颜色
	while (parent && parent->_color == RED)
	{
		Node* grandfather = parent->_parent;
		if (grandfather->_left == parent)
		{
			Node* uncle = grandfather->_right;
			
			// u 存在且为红
			// u 不存在或存在且为黑
			//		p 为 g 的左，cur 为 p 的左 右单旋
			//		p 为 g 的左，cur 为 p 的右 先左旋再右旋
			if (uncle && uncle->_color == RED)
			{
				grandfather->_color = RED;
				parent->_color = BLACK;
				uncle->_color = BLACK;

				// 继续判断是否违反了红黑树的性质
				cur = grandfather;
				parent = grandfather->_parent;
			}
			else
			{
				if (parent->_left == cur)
				{
					RotateR(grandfather);
					grandfather->_color = RED;
					parent->_color = BLACK;
				}
				else
				{
					RotateL(parent);
					RotateR(grandfather);
					grandfather->_color = RED;
					cur->_color = BLACK;
				}
			}
		}
		else
		{
			Node* uncle = grandfather->_left;

			// u 存在且为红
			// u 不存在或存在且为黑
			//		p 为 g 的右，cur 为 p 的右 左单旋
			//		p 为 g 的右，cur 为 p 的左 先右旋再左旋
			if (uncle && uncle->_color == RED)
			{
				grandfather->_color = RED;
				parent->_color = BLACK;
				uncle->_color = BLACK;

				// 继续判断是否违反了红黑树的性质
				cur = grandfather;
				parent = grandfather->_parent;
			}
			else
			{
				if (parent->_right == cur)
				{
					RotateL(grandfather);
					grandfather->_color = RED;
					parent->_color = BLACK;
				}
				else
				{
					RotateR(parent);
					RotateL(grandfather);
					grandfather->_color = RED;
					cur->_color = BLACK;
				}
			}
		}
	}

	_root->_color = 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
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