高级数据结构与算法 | 红黑树（Red-Black Tree）_std红黑树

---

红黑树

红黑树的概念

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

红黑树的性质

1. 每个节点不是红色就是黑色
2. 根节点必须为黑节点
3. 如果一个节点是红的，则他的两个孩子是黑的（不存在连续的红结点）
4. 从某一节点出发到其所有的叶子节点，其中经过的黑色节点数量相等
5. 每个叶子节点是黑色的（这里的叶子节点指的是NULL节点）

根据这几种性质，是如何保证每一个节点的高度差不超过二倍呢？我们可以直接设想一下极端情况
对于一个结点，到其叶子所经过的最短路径全为黑节点，最长路径为一黑一红交错的路径。
在完全遵守上面所有的性质的情况下，最大的路径差即为下图，也就是二倍。

---

红黑树与AVL树

在之前的博客中，我介绍了另外一种平衡二叉树，AVL树，他和红黑树又有什么不同呢？为什么在大部分库里，如STL、Linux内核等大部分都采用的是红黑树呢？

首先就来分析他们的增删查改的效率。
因为红黑树保证了最大的路径差不超过二倍，所以其在最坏情况下，增删查改的效率是O(2logN)
而AVL树则因为多次单旋双旋保证了高度平衡，其最大的高度差不超过2，所以他的效率一直都是保持在O(logN)左右。
从这里来看，AVL树的效率比红黑树要高上不少，几乎接近两倍，但是因为其单位都是logN，这里的两倍几乎就可以忽略了。例如要查找十亿个的数据（只考虑查找），最坏情况下，AVL树要30次，而红黑树要60次，虽然差距是两倍，但是这两倍对于计算机来说几乎已经可以忽略不计。并且，AVL树的高度平衡是因为其通过大量的旋转来完成的，所以对于经常发生删除和插入的结构，红黑树的效率会更优，并且红黑树的实现比起AVL更加容易且易于控制，所以实际中使用红黑树更多。

这是之前看到的一张图，可以从上图看到，如果是比较查找时，此时红黑树略低于AVL树，但如果是插入或者删除，则稍微高于AVL，原因就是因为AVL需要维护其高度平衡的特性，所以进行更多的旋转，导致效率降低。

红黑树的实现

关于二叉搜索树的思路，以及旋转的思路在前两篇中已经写过，这里就不多赘述
数据结构 ： 二叉搜索树的原理以及实现（C++）
数据结构 ： AVL树的原理以及实现（C++）

红黑树的节点

	enum Color
	{
		BLACK,
		RED,
	};
	
	template<class T>
	struct RBTreeNode
	{
		typedef RBTreeNode<T> Node;

		RBTreeNode(const T& data = T(), const Color& color = RED) 
			: _left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _data(data)
			, _color(color)
		{}

		Node* _left;
		Node* _right;
		Node* _parent;
		T _data;
		Color _color;
	};
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

红黑树的节点和二叉搜索树差不多，只是多了一个颜色，在这里我为了代码更加直观所以用的是枚举

红黑树的插入

插入分为两个步骤

1. 按照二叉搜索树的特性找到插入的位置
2. 按照红黑树的特性进行调节

第一步骤之前几个博客都讲过了，这里就不多说，直接讲第二步骤。

首先依据红黑树的特性，我们要决定新增节点的颜色。
如果新插入的结点为红色，则有可能打破了不能有连续的红结点这一规则，而如果插入的是黑色，则又破坏了每个路径的黑节点数量相同这一规则。如果都会破坏的话，就需要选择一个方便修复的，而不能有连续的红结点这一规则，只需要进行一下颜色的变换或者旋转，就可以解决这个问题，所以新增节点都为红色。

接着来探讨插入时的各种状况。

情况1:插入节点的父节点为黑色

此时是最优情况，因为没有破坏任何规则，所以此时无需任何处理。

情况2：插入节点的父节点为红色，叔叔节点也为红色，祖父为黑色

此时的处理方法也很简单，因为出现了连续的红色，所以只需要进行颜色的修正即可解决。
这里将父亲和叔叔变黑，祖父变红即可解决。同时，因为祖父之上可能还有其他节点，还需要从祖父的位置继续向上调节。

情况3：孩子为红，父亲为红，叔叔为黑或者不存在，祖父为黑。孩子与父亲呈直线状态

这里有两种情况

1. 如果叔叔存在，则此时的孩子节点可能是下面的子树在进行变色处理时，将其从原本的黑色变为了红色。（否则不满足路径黑节点数量相同的性质）
2. 如果叔叔不存在，则此时的孩子节点是刚插入进来的结点，因为不能有连续的红结点，所以孩子和父亲必须有一个是黑色，但是此时又不满足黑节点数量相同的性质。

解决的方法也不难，只需要旋转+变色处理即可
和AVL树一样，因为父亲和孩子呈直线状态，所以只需要单旋即可。
如果父亲是祖父的左孩子，孩子是父亲的左孩子，此时祖父进行右单旋
如果父亲是祖父的右孩子，孩子是父亲的右孩子，此时祖父进行左单旋。

此时再将祖父变红，父亲变黑，即可完成处理

情况4：孩子为红，父亲为红，叔叔为黑或者不存在，祖父为黑。孩子与父亲呈折线状态
这种情况与上面的类似，如果此时孩子与父亲处理折线状态，就需要双旋 + 变色处理

如果父亲是祖父的左孩子，孩子是父亲的右孩子，父亲此时进行左单旋
如果父亲是祖父的右孩子，孩子是父亲的左孩子，父亲此时进行右单旋。

上图进行左单旋

此时我们发现，这个状态和情况3有点像，所以只需要交换父亲和孩子，就可以转换为情况3

接着再按照情况3再进行一次单旋处理即可。

bool Insert(const std::pair<K, V>& data)
{

	//按照二叉搜索树的规则先找到位置
	//创建根节点
	if (_root == nullptr)
	{
		_root = new Node(data, BLACK);

		return true;
	}

	Node* cur = _root;
	Node* parent = nullptr;

	while (cur)
	{
		if (data.first > cur->_data.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (data.first < cur->_data.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}

	//新插入节点为红色
	cur = new Node(data, RED);

	//保存插入的结点，因为后面会往上更新红黑树，所以cur可能会变化。
	Node* newNode = cur;

	//判断插入位置
	if (cur->_data.first > parent->_data.first)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	cur->_parent = parent;

	//更新红黑树，如果父节点的颜色为黑，则说明满足条件，不需要处理，如果为红，则说明不满足，需要处理。
	while (parent && parent->_color == RED)
	{
		Node* ppNode = parent->_parent;

		//如果父节点为祖父的左子树
		if (ppNode->_left == parent)
		{
			//此时判断叔叔节点的状态，红黑树状态取决于叔叔
			Node* uncle = ppNode->_right;

			//第一种情况，如果叔叔节点存在且为红，则直接把父亲和叔叔变黑，祖父节点边红即可。然后再从祖父的位置继续往上调整
			if (uncle && uncle->_color == RED)
			{
				//变色
				uncle->_color = parent->_color = BLACK;
				ppNode->_color = RED;

				//继续往上
				cur = ppNode;
				parent = cur->_parent;
			}
			/*
				叔叔节点为黑或者不存在，此时有两种情况
				情况二：cur为父节点的左子树，即直线状态。
				情况三：cur为父节点的右子树，即折线状态。

				情况二单旋一次后更改颜色即可完成
				对于情况三，如果将其进行一次旋转后再稍微处理，就可以转换成情况二
			 */
			else
			{
				//因为这里的双旋和AVL不一样，可以不用处理平衡因子，所以如果为折线则先旋转处理后，将其转换为直线处理即可。

				//第三种情况，折线状态，转换为直线状态处理
				if (parent->_right == cur)
				{
					RotateL(parent);
					//单旋后再交换节点，即可变成直线状态。
					std::swap(parent, cur);
				}

				//处理第二种状态
				RotateR(ppNode);

				parent->_color = BLACK;
				ppNode->_color = RED;

				//处理完成
				break;
			}

		}
		//如果父亲为祖父的右子树
		else
		{
			//此时叔叔为左子树。
			Node* uncle = ppNode->_left;

			if (uncle && uncle->_color == RED)
			{
				uncle->_color = parent->_color = BLACK;
				ppNode->_color = RED;

				cur = ppNode;
				parent = cur->_parent;
			}
			else
			{
				if (parent->_left == cur)
				{
					RotateR(parent);
					std::swap(cur, parent);
				}

				RotateL(ppNode);

				ppNode->_color = RED;
				parent->_color = BLACK;

				break;
			}
		}
	}

	//为了防止不小心把根节点改为红色，最后手动改为黑色即可
	_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

旋转的思路已经讲过很多次了，这里就直接给代码，如果想了解具体思路可以点击上面AVL树那一篇博客

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

	parent->_left = subLR;

	//如果subLR存在，则让他的父节点指向parent。
	if (subLR)
	{
		subLR->_parent = parent;
	}

	subL->_right = parent;

	Node* ppNode = parent->_parent;
	parent->_parent = subL;

	//两种情况
	//如果parent为根节点，则让subL成为新的根节点
	if (parent == _root)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	//如果不是根节点，则改变subL与其祖父节点的指向关系
	else
	{
		if (ppNode->_left == parent)
		{
			ppNode->_left = subL;
		}
		else
		{
			ppNode->_right = subL;
		}

		subL->_parent = ppNode;
	}
}

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

	parent->_right = subRL;

	if (subRL)
	{
		subRL->_parent = parent;
	}

	subR->_left = parent;
	Node* ppNode = parent->_parent;
	parent->_parent = subR;

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

		subR->_parent = ppNode;
	}
}
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

---

红黑树的查找

这里的查找和二叉搜索树一样，就不多说了

bool Find(const std::pair<K, V>& data)
{
	//根据二叉搜索树的性质，从根节点出发，比根节点大则查找右子树，比根节点小则查找左子树
	Node* cur = _root;

	while (cur)
	{
		//比根节点大则查找右子树
		if (data.first > cur->_data.first)
		{
			cur = cur->_right;
		}
		//比根节点小则查找左子树
		else if (data.first < cur->_data.first)
		{
			cur = cur->_left;
		}
		//相同则返回
		else
		{
			return true;
		}
	}

	//遍历完则说明查找不到，返回false
	return false;
}
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

---

红黑树的验证

要验证是否为红黑树，只需要判断其是否满足这三个性质。
1. 根节点必须为黑节点
2. 不存在连续的红结点
3. 从某一节点出发到其所有的叶子节点，其中经过的黑色节点数量相等

bool IsRBTree()
{
	if (_root == nullptr)
	{
		//空树也是红黑树
		return true;
	}

	//违反性质1
	if (_root->_color != BLACK)
	{
		return false;
	}

	//获取从根节点出发的任意一条子路径的黑色节点数，这里选取最左子树。
	Node* cur = _root;
	size_t blackCount = 0;
	size_t count = 0;

	while (cur)
	{
		if (cur->_color == BLACK)
		{
			blackCount++;
		}

		cur = cur->_left;
	}

	//递归判断其他路径的黑色节点数
	return _IsRBTree(_root, count, blackCount);
}

bool _IsRBTree(Node* root, size_t count, const size_t blackCount)
{
	//此时说明已经走到叶子节点，判断黑色节点数是否相等，不相等则违反性质3
	if (root == nullptr)
	{
		if (count != blackCount)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	//如果没走完，就接着判断其他情况

	//判断性质2，如果存在连续的红结点，则返回错误
	Node* parent = root->_parent;

	if (parent && root->_color == RED && parent->_color == RED)
	{
		return false;
	}

	//如果当前节点为黑色，则记录
	if (root->_color == BLACK)
	{
		count++;
	}

	//接着递归判断当前节点的所有路径
	return _IsRBTree(root->_left, count, blackCount) && _IsRBTree(root->_right, count, blackCount);
}
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

完整代码

#pragma once
#include<iostream>

namespace lee
{
	enum Color
	{
		BLACK,
		RED,
	};

	template<class K, class V>
	struct RBTreeNode
	{
		typedef RBTreeNode<K, V> Node;
		RBTreeNode(const std::pair<K, V>& data = std::pair<K, V>(), const Color& color = RED)
			: _left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _data(data)
			, _color(color)
		{}

		Node* _left;
		Node* _right;
		Node* _parent;
		std::pair<K, V> _data;
		Color _color;
	};


	template<class K, class V>
	class RBTree
	{
	public:
		typedef RBTreeNode<K, V> Node;

		RBTree()
			: _root(nullptr)
		{}

		~RBTree()
		{
			destory(_root);
		}

		void _InOrderTravel(Node* root) const
		{
			if (root == nullptr)
				return;

			_InOrderTravel(root->_left);

			std::cout << root->_data.first << ':' << root->_data.second << std::endl;

			_InOrderTravel(root->_right);
		}

		void InOrderTravel() const
		{
			_InOrderTravel(_root);
		}

		void destory(Node*& root)
		{
			Node* node = root;
			if (!root)
				return;

			destory(node->_left);
			destory(node->_right);

			delete node;
			node = nullptr;
		}

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

			parent->_left = subLR;

			//如果subLR存在，则让他的父节点指向parent。
			if (subLR)
			{
				subLR->_parent = parent;
			}

			subL->_right = parent;

			Node* ppNode = parent->_parent;
			parent->_parent = subL;

			//两种情况
			//如果parent为根节点，则让subL成为新的根节点
			if (parent == _root)
			{
				_root = subL;
				subL->_parent = nullptr;
			}
			//如果不是根节点，则改变subL与其祖父节点的指向关系
			else
			{
				if (ppNode->_left == parent)
				{
					ppNode->_left = subL;
				}
				else
				{
					ppNode->_right = subL;
				}

				subL->_parent = ppNode;
			}
		}

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

			parent->_right = subRL;

			if (subRL)
			{
				subRL->_parent = parent;
			}

			subR->_left = parent;
			Node* ppNode = parent->_parent;
			parent->_parent = subR;

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

				subR->_parent = ppNode;
			}
		}

		bool Find(const std::pair<K, V>& data)
		{
			//根据二叉搜索树的性质，从根节点出发，比根节点大则查找右子树，比根节点小则查找左子树
			Node* cur = _root;

			while (cur)
			{
				//比根节点大则查找右子树
				if (data.first > cur->_data.first)
				{
					cur = cur->_right;
				}
				//比根节点小则查找左子树
				else if (data.first < cur->_data.first)
				{
					cur = cur->_left;
				}
				//相同则返回
				else
				{
					return true;
				}
			}

			//遍历完则说明查找不到，返回false
			return false;
		}

		bool Insert(const std::pair<K, V>& data)
		{

			//按照二叉搜索树的规则先找到位置
			//创建根节点
			if (_root == nullptr)
			{
				_root = new Node(data, BLACK);

				return true;
			}

			Node* cur = _root;
			Node* parent = nullptr;

			while (cur)
			{
				if (data.first > cur->_data.first)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (data.first < cur->_data.first)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}

			//新插入节点为红色
			cur = new Node(data, RED);

			//保存插入的结点，因为后面会往上更新红黑树，所以cur可能会变化。
			Node* newNode = cur;

			//判断插入位置
			if (cur->_data.first > parent->_data.first)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
			cur->_parent = parent;

			//更新红黑树，如果父节点的颜色为黑，则说明满足条件，不需要处理，如果为红，则说明不满足，需要处理。
			while (parent && parent->_color == RED)
			{
				Node* ppNode = parent->_parent;

				//如果父节点为祖父的左子树
				if (ppNode->_left == parent)
				{
					//此时判断叔叔节点的状态，红黑树状态取决于叔叔
					Node* uncle = ppNode->_right;

					//第一种情况，如果叔叔节点存在且为红，则直接把父亲和叔叔变黑，祖父节点边红即可。然后再从祖父的位置继续往上调整
					if (uncle && uncle->_color == RED)
					{
						//变色
						uncle->_color = parent->_color = BLACK;
						ppNode->_color = RED;

						//继续往上
						cur = ppNode;
						parent = cur->_parent;
					}
					/*
						叔叔节点为黑或者不存在，此时有两种情况
						情况二：cur为父节点的左子树，即直线状态。
						情况三：cur为父节点的右子树，即折线状态。

						情况二单旋一次后更改颜色即可完成
						对于情况三，如果将其进行一次旋转后再稍微处理，就可以转换成情况二
					 */
					else
					{
						//因为这里的双旋和AVL不一样，可以不用处理平衡因子，所以如果为折线则先旋转处理后，将其转换为直线处理即可。

						//第三种情况，折线状态，转换为直线状态处理
						if (parent->_right == cur)
						{
							RotateL(parent);
							//单旋后再交换节点，即可变成直线状态。
							std::swap(parent, cur);
						}

						//处理第二种状态
						RotateR(ppNode);

						parent->_color = BLACK;
						ppNode->_color = RED;

						//处理完成
						break;
					}

				}
				//如果父亲为祖父的右子树
				else
				{
					//此时叔叔为左子树。
					Node* uncle = ppNode->_left;

					if (uncle && uncle->_color == RED)
					{
						uncle->_color = parent->_color = BLACK;
						ppNode->_color = RED;

						cur = ppNode;
						parent = cur->_parent;
					}
					else
					{
						if (parent->_left == cur)
						{
							RotateR(parent);
							std::swap(cur, parent);
						}

						RotateL(ppNode);

						ppNode->_color = RED;
						parent->_color = BLACK;

						break;
					}
				}
			}

			//为了防止不小心把根节点改为红色，最后手动改为黑色即可
			_root->_color = BLACK;

			return true;
		}

		/*
			判断是否为红黑树，就是判断其是否满足红黑树的特性

			特性：	1.根节点必须为黑节点
					2.不存在连续的红结点
					3.从某一节点出发到其所有的叶子节点，其中经过的黑色节点数量相等

		*/
		bool IsRBTree()
		{
			if (_root == nullptr)
			{
				//空树也是红黑树
				return true;
			}

			//违反性质1
			if (_root->_color != BLACK)
			{
				return false;
			}

			//获取从根节点出发的任意一条子路径的黑色节点数，这里选取最左子树。
			Node* cur = _root;
			size_t blackCount = 0;
			size_t count = 0;

			while (cur)
			{
				if (cur->_color == BLACK)
				{
					blackCount++;
				}

				cur = cur->_left;
			}

			//递归判断其他路径的黑色节点数
			return _IsRBTree(_root, count, blackCount);
		}

		bool _IsRBTree(Node* root, size_t count, const size_t blackCount)
		{
			//此时说明已经走到叶子节点，判断黑色节点数是否相等，不相等则违反性质3
			if (root == nullptr)
			{
				if (count != blackCount)
				{
					return false;
				}
				else
				{
					return true;
				}
			}
			//如果没走完，就接着判断其他情况

			//判断性质2，如果存在连续的红结点，则返回错误
			Node* parent = root->_parent;

			if (parent && root->_color == RED && parent->_color == RED)
			{
				return false;
			}

			//如果当前节点为黑色，则记录
			if (root->_color == BLACK)
			{
				count++;
			}

			//接着递归判断当前节点的所有路径
			return _IsRBTree(root->_left, count, blackCount) && _IsRBTree(root->_right, count, blackCount);
		}

	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
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
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403