🐱作者：一只大喵咪1201
🐱专栏：《数据结构与算法》
🔥格言：你只管努力，剩下的交给时间！

在学习AVL树的时候，我们知道，当修改AVL树的结构(插入，删除)时，会通过旋转来保证平衡因子不超过1，所以频繁的修改结构会导致效率低下，今天我们学习的红黑树就完美解决了这个问题。

红黑树

• 🍧红黑树
• • 🍨节点的定义
• 🍧红黑树的插入
• 🍧红黑树的调整
• • 🍨cur为红，p为红，g为黑，u存在且为红
  • 🍨cur红且为左子树，p为红，g为黑，u不存在/u存在且为黑
  • 🍨cur红且为右子树，p为红，g为黑，u不存在/u存在且为黑
• 🍧红黑树的验证
• 🍧红黑树与AVL树的比较
• 🍧总结

🍧红黑树

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

红黑树也是一种二叉搜索树，和AVL树一样，也是在二叉搜索树的基础上做一些限制来保证它的搜索效率。

• 红黑树原则： 最长路径不超过最短路径的二倍。

红黑树就是靠这个原则来维护它的结构的。

• 上图所示，最长路径是13->17->25->27->NULL(不止这一条)，路径长度是4。
• 最短路径是13->8->NULL(不止这一条)，路径长度是2。

此时就是红黑树的极限了，它相对于AVL树平衡性较低，根节点的左右子树高度差是2。但是它比AVL树修改结构时的效率高。

为了维护最长路径不超过最短路径的2倍这一原则，红黑树是通过几个性质来达到目的的：

• 每个节点不是红色就是黑色。
• 整颗树的根节点是黑色的。
• 如果一个节点是红色的，则它的两个孩子节点必须是黑色的(不会出现两个连续的红色节点)。
• 从任意节点到其所有后代节点的简单路径上，均包含相同数目的黑色节点。
• 每个叶子节点都是黑的(此处的叶子节点特指空节点NULL)。

这里重点解释两条性质：

1. 不会出现两个连续的红色节点。

如上图所示，节点8的左右子节点必须都是黑色的，不能出现红色。

2. 任意节点到其后代所有节点的简单路径上，黑色节点的个数相同。

• 简单路径：13->17->15->NULL，如上图绿色框。
• 复杂路径：13->8-1->NULL->6->NULL，如上图蓝色框。

复杂路径采用的是前序遍历的方式，而简单路径只是从某一节点出发，直接到其叶子节点。

• 红色框中的路径，黑色节点有两个(不算空节点NULL)。
• 蓝色框中的路径，合适节点也是有两个(不算空节点NULL)。

从任意节点出发到其所有叶子节点的简单路径，黑色节点个数都是相同的，包不包括空节点NULL都可以，因为所有叶子节点都有空节点NULL，默认情况下我们不包括空节点。

红黑树最优情况(左右最平衡)：

• 此时是最优情况，此时的平衡度最高。

最优情况：

• 全黑或者每条路径都是一黑一红相间的路径，并且是一颗满二叉树。

红黑树最差情况(左右最不平衡)：

• 此时情况是最差的，最长的路径是一黑一红，最短路径都是黑，平衡度是最低的。

最差情况：

• 左子树全黑，右子树一黑一红相间，或者反过来。
• 最短路径的长度：log₂(N+1)，等价于log₂N。
• 最长路径的长度：2*log₂N。

具化一下，十亿个数据，最短路径包含的个数大约是30个，而最长路径也不过是60个左右。对于计算机而言，30个和60个几乎是一样的，所以它们的搜索效率也可以看成是一样的。

这时反过来再看：

• 如果可以出现两个连续的红色节点，就不能保证最长路径不超过最短路径的二倍这一原则了。
• 如果不同简单路径上的黑色节点个数可以不一样，同样不能保证最长路径不超过最短路径的二倍这一原则了。

AVL树维持平衡非常直接，直接通过旋转来维持左右子树高度差不超过1这个原则。而红黑树就不是这么直接了，它是通过5个性质，尤其上上面这两条来间接维持最长路径不超过最短路径的二倍这一原则的。

🍨节点的定义

红黑树比二叉搜索树多一个表示颜色的成员变量。

//枚举红黑颜色
enum Color
{
	RED,
	BLACK
};

template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;//左节点
	RBTreeNode<K, V>* _right;//右节点
	RBTreeNode<K, V>* _parent;//父节点
	pair<K, V> _kv;//键值对
	Color _col;//颜色

	//构造函数
	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_col(RED)//新节点默认是红色
	{}
};

• 节点颜色是枚举变量，定义枚举时，只有红色REB和黑色BLACK。
• 构造函数中，节点的默认颜色给成红色。

🍧红黑树的插入

插入节点的过程和二叉搜索树一样，不同在于插入以后要进行调整，此时的调整是按照红黑树的规则进行调整，先来看插入：

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	bool insert(const pair<K, V>& kv)
	{
		//空树，新节点就是根
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;//根节点必须是黑色
			return true;
		}
		//不是空树
		Node* parent = nullptr;
		Node* cur = _root;
		//寻找插入位置
		while (cur)
		{
			//比节点大，向右寻找
			if (cur->_kv.first < kv.first)
			{
				parent = cur;//更新父节点
				cur = cur->_right;
			}
			//比节点小，向左寻找
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;//更新父节点
				cur = cur->_left;
			}
			//和节点相等不运行插入
			else
			{
				return false;
			}
		}
		//找到位置后开始插入
		cur = new Node(kv);//创建新节点
		cur->_col = RED;//新节点颜色给成红色
		//插入新节点
		//比父节点大，插入到右边
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		//比父节点小，插入到左边
		else if (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		//调整新节点

		//插入成功
		return true;
	}
	//中序打印
	void InOrder()
	{
		InOrder(_root);
	}
private:
	//中序打印实现
	void InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		InOrder(root->_right);
	}
protected:
	Node* _root = nullptr;
};

• 当插入的新节点作根节点时，需要将该节点的颜色变成黑色，符合红黑树的性质，因为默认情况下节点的颜色是红色的(节点构造函数的初始化中)。

• 在插入节点的时候，需要确保新节点的颜色是红色，当然这一步可以省略，因为我们在构造节点时就默认给了它红色，这里是为了严谨。

这是为什么呢？新节点是黑的又会怎样呢？

• 插入的新节点是黑的，必然会违背每条简单路径上黑色节点个数相同这一性质，因为别的路径上黑色节点数量没变。
• 插入的新节点是红的，有可能会违背不能有两个连续的红色节点这一性质。

此时我们选择哪种呢？当然是选择代价小的。

• 新插入节点是红色，有可能违背不能有两个连续红节点的原则，如果违背了，只需要调整这一个路径上节点的颜色。如果没有违背都不用进行调整。
• 新插入节点是黑色的，必然违背每条简单路径黑色节点数相同的原则，需要调整每一条路径。

相对来说，插入新节点的颜色是红色代价比较小。

这部分代码在二叉搜索树和AVL树中都有，本喵就不再讲解了，此时的是仅仅是一颗二叉搜索树，接下来就需要我们对这颗树进行调整，使它成为红黑树。

🍧红黑树的调整

调整就是要维护最长路径不超过最短路径的二倍这一原则，但是并不是直接去达到这个目的，而是通过维护红黑树的那几条性质来间接达到这个目的。

需要调整的情况可以分为三种：

🍨cur为红，p为红，g为黑，u存在且为红

• cur：表示当前节点，可能是新插入节点，也可能是待调整节点。
• p：表示父节点，是单词parent的首字母。
• g：表示祖父节点，是grandfather的首字母。
• u：表示叔叔节点，是uncle的首字母。

先来看具象图：

cur是新插入的节点(红色)：

• 新插入节点cur是红色，违背了不能有两个连续红色节点的性质。节点g到其两个叶子节点的简单路径中，黑色节点个数都是1。

调整过程：

• 先将节点p和u变成黑色。
• 再将节点g变成红色。
• 更新亲戚关系。

此时从节点g到其两个叶子节点的简单路径上，黑色节点仍然都是1，而且没有两个连续的红色节点。

在上图基础上增加两层节点：

最开始的cur是新插入节点，c/d/e都是下面红色框中三种中的一种，此时从根节点到其所有叶子节点的简单路径上，黑色节点的个数都是2。

调整过程：

• 先将节点p和u变成黑色，再将g变成红色，同时将g更新成cur，并且将g，p，u也做相应的更新。
• 再将新的p和u变成合适，新的g变成红色，同时将g再更新为cur。

根据上面规律，来看抽象图：

cur是更新后待调整的节点，a/b/c/d/e是红黑树，且黑色节点个数相同。

调整过程：

• 先将节点p和u变成红色。
• 再将g变成黑色。
• 更新亲戚关系

调整过后就完全符合红黑树的性质。

来看代码实现：

• 当父亲节点是红色时，和cur的红色违背了不能有两个连续红色节点的性质，所以需要更新，如果父亲节点是黑色则不用更新。
• 需要调整节点所在的子树是祖父节点的左子树。
• 颜色调整完毕后，需要更新cur和parent节点，方便继续向上调整。

cur节点是父节点的右子树也是上诉方法。

🍨cur红且为左子树，p为红，g为黑，u不存在/u存在且为黑

这里本喵就不再画具象图了，直接上抽象图：

先看节点u不存在：

此时节点u不存在，cur为待调整的红色节点。

调整过程：

• 先以节点g为轴点，进行有单旋。
• 再将节点g变成红色，节点p变成黑色，并且成为子树的新根。

调整过后，左右子树的黑色节点个数仍然不变。

需要先进行旋转的原因：

最开始从祖父节点到其左右子树的简单路径上黑色节点的个数都是1。而父节点是必须要变成黑色的，如果直接按照第一种情况那样，将父节点变成黑色，祖父节点变成红色，那么左边路径中比右边路径中黑色节点就多一个，违背了左右简单路径黑色节点个数相同的性质。

• p为左子树，cur为左子树，先进行右单旋，再将父节点变成黑色，祖父节点变成红色。
• p为右子树，cur为右子树，先进行左单旋，再将父节点变成黑色，祖父节点变成红色。

至于p和cur都是右子树的图本喵就不画了。

再看节点u存在且为黑：

cur为待调整的红色节点，起初左子树黑色节点有1个，右子树黑色节点有两个。

调整过程：

• 先以祖父节点为轴点进行右单旋。
• 再将父节点变成黑色，祖父节点变成红色。

调整过后，左边路径黑色节点个数还是1，右边路径黑色节点个数还是2，且没有两个连续的红色节点。

同样的，必须先进行旋转，否则就会减少右边路径中的黑色节点，可以自己去画一下来验证。

根据上面示意图，可以看到叔叔节点不存在和存在且为黑，它们的调整方式是一样的，都是先旋转再变色。

来看代码实现：

右单旋在AVL树的时候就实现过了， 这里直接复用就可以，这样来看，代码还是比较简单的。

🍨cur红且为右子树，p为红，g为黑，u不存在/u存在且为黑

这里本喵就不再画u不存在的抽象图了，直接画u存在且为黑的抽象图：

起初cur是红色，并且是父节点的右子树，左边简单路径只有一个黑色节点，右边简单路径有两个黑色节点。

调整过程：

• 先以父节点为轴点进行左单旋。
• 再以祖父节点为轴点进行右单旋。
• 再变色，将cur节点变成黑色，祖父节点变成红色。

经过调整过后，左边路径中的黑色节点个数还是1，右边路径中的黑色节点个数也还是2。

• 父节点是左子树，cur是右子树，先进行左右双旋，再变色，将cur变成黑色，祖父节点变成红色。
• 父节点是右子树，cur是左子树，先进行右左双旋，再变色，将cur变成黑色，祖父节点变成红色。

来看代码实现：

同样，左旋和右旋直接复用在AVL中的就行，只需要进行变色，让cur为黑，祖父节点为红。

注意： 这种情况和第二种情况都是属于先旋转再变色的，而且在变色后并不用继续更新亲戚关系，直接break跳出循环即可。

• 第一种情况下，调整过后，子树的根节点是红色，有可能再次违背不能有两个连续红色节点的性质。
• 第二和三种情况下，调整过后，子树的根节点是黑色，不会违背不能有两个连续红色节点的性质。

调整过程的总结：

这样一看分类非常多，但其实就是三大类。

• uncle存在且为黑和uncle不存在的操作是一样的。
• 是左子树还是右子树，只是旋转方向不同。

红黑树的调整，关键在于叔叔节点。

//调整新节点
		//parent是红色且存在，需要调整
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			//parent都是左子节点
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				//cur是红，p是红，u存在且为红，g为黑
				if (uncle && uncle->_col == RED)
				{
					//颜色调整
					parent->_col = uncle->_col = BLACK;//父亲和叔叔节点变成黑
					grandfather->_col = RED;//祖父节点变成红

					//更新亲戚关系
					cur = grandfather;
					parent = cur->_parent;
				}
				//cur是红色，p为红色，u不存在/u存在且为黑色，g为黑色
				else
				{
					//cur是左子树
					if (cur == parent->_left)
					{
						//先进行右单旋
						RotateR(grandfather);
						//变色
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					//cur是右子树
					else
					{
						//先进左右双旋
						RotateL(parent);
						RotateR(grandfather);
						//变色
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;//待旋转的调整完毕后，子树根节点是黑色
				}
			}
			//parent是右子节点
			else
			{
				Node* uncle = grandfather->_left;
				//情况一：叔叔存在且为红
				if (uncle && uncle->_col == RED)
				{
					//父亲和叔叔节点变成黑，祖父节点变成红
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					//更新亲戚关系
					cur = grandfather;
					parent = cur->_parent;
				}
				//叔叔不存在或者存在且为黑
				else
				{
					//情况二：cur是右子树
					if (cur == parent->_right)
					{
						//先进行左单旋
						RotateL(grandfather);
						//变色
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					//情况三：cur是左子树
					else
					{
						//先进行右单旋
						RotateR(parent);
						//再进行左单旋
						RotateL(grandfather);
						//变色
						grandfather->_col = RED;
						cur->_col = BLACK;
					}
					//旋转调整后，子树根节点是黑色，不用再调整
					break;
				}
			}
		}

整个调整部分的代码。

调整过后：

在最后返回之前，要让根节点的颜色为黑色。

🍧红黑树的验证

和AVL树一样，也需要验证一下我们的红黑树写的是否正确。同样需要写专门验证的函数，不能只看插入的结果，这样的话只能验证二叉搜索树是对的。

写一个验证红黑树的函数：

检测一棵树是否是红黑树，就要根据它的那几点性质来检测。

• 如果是空树，直接返回真，它就是红黑树。
• 如果根节点不是黑的，那它必然不是红黑树，如果是黑的则不一定。
• 将最左路径中的黑色节点个数求出来，和每条路径进行比较，只要有不相等的，那么它必然不是红黑树。

比较整颗树不同简单路径中黑色节点的个数，以及判断是否有两个连续的红色节点，使用递归更加方便。

• 在递归到每条简单路径的根节点时，比较一下该路径和最左路径中黑色节点的个数，如果不相等则它必然不是红黑树。
• 要判断当前节点和其父节点是否是连续的红色节点，若判断当前节点和其子节点，则会很复杂。

这个参数能使用引用吗？前面经常在递归时候使用引用，但是这里不可以。

• 当递归到某一层的时候，blackNum会在继续递归的时候传下去，在递归到后面层中改变blackNum，并不会影响到这一层的blackNum。
• 如果这一层只有左子树，没有右子树，先递归的左子树，在递归左子树的过程中会改变blackNum，当递归回到这一层继续递归右子树的时候，需要的blackNum是这一层的blackNum，而不是从左子树返回了的blackNum。
• 如果使用引用类型，那么在递归的过程中，blackNum会越来越大，就导致判断出错。

有兴趣的小伙伴可以画一下递归展开图就都明白了。

如上图中代码所示，我们自己创造的三个测试用例，通过插入的方式形成的树都是红黑树，验证结果返回了真。

和AVL树一样，这样测试不具有一般性，下面用随机数来测试：

void TestRBTree2()
{
	//生成随机数种子
	srand((unsigned int)time(nullptr));
	const size_t N = 10000;
	RBTree<int, int> t;
	for (size_t i = 0; i < N; i++)
	{
		size_t value = rand();
		t.insert(make_pair(value, value));
		//cout << value << ":" << value << endl;
		//t.IsRBTree();
	}
	cout << t.IsRBTree() << endl;
}

运行多次，可以看到，结果都是1，也就是说这10000个随机数构成的二叉搜索树是红黑树。说明我们之前写的插入是正确的。

和AVL树一样，红黑树的删除我们也不实现，因为比较复杂，当删除一个数据以后，同样需要进行颜色改变，最差时会从叶子更新到根，效率比较低，有兴趣的小伙伴可以自己去了解一下。

🍧红黑树与AVL树的比较

• 红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O($lo{g}_{2}N$)。
• 红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数。
• 所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

红黑树的应用：

• C++STL库–map/set、multimap/multiset。
• linux内核
• 其他一些库

🍧总结

红黑树比较抽象，它并不像AVL树那样直接维护平衡因子，而是通过维护红黑树的几个性质来间接维护最长路径不超过最短路径的二倍这个原则。现在我们已经对红黑树有了清晰的认识，下面就可以模拟实现map和set了，因为这两个容器的底层就是红黑树。