【SLT库】红黑树的原理学习 | 模拟实现

👓️博主简介:

前言

我们已经学习完了二叉搜索树和它的其中一种优化方式 - AVL树，它是靠旋转去优化我们树的插入方式，从而避免了单一子树过长的问题，本章节我们再来讲一个优化的方式，它会比 AVL 树的效率快一点，也是我们 STL 库中 map/set 封装的底层结构，我们本章节还是会使用到 AVL 树和 二叉搜索树的知识，大家一定要熟练掌握前者后再来学习哦。

一、红黑树的概念

红黑树是一颗二叉搜索树，他的每个结点增加一个存储位来表示结点颜色，可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出 2 倍，因而是接近平衡的。

1.1、红黑树的规则

红黑树的想要平衡我们二叉树，使其不会出现一条子树非常长的情况，主要依靠的不是疯狂旋转，而是以下的 4 条规则，这些规则使我们二叉树也能够实现相对平衡，我们来看看吧。

规则：

• 每个结点不是红色就是黑色
• 根结点是黑色的
• 如果一个结点是红色的，则它的两个孩子结点必须是黑色的，也就是说任意一条路径不会有连续的红色结点
• 对于任意一个结点，从该结点到其所有 nullptr 结点的简单路径上，均包含相同数量的黑色结点

注意：

我们的路径是从根结点算到 nullptr 结点，而非从根结点算到最后一个子结点。就比如下面的图中，题目的路径总数分别为 10 条、16 条、8 条、6 条。《算法导论》等书籍上补充了一条：每个叶子结点 (NIL) 都是黑色的规则。他这里所指的叶子结点不是传统的意义上的叶子结点，而是我们说的空结点，有些书籍上也把 NIL 叫做外部结点。NIL 是为了方便准确的标识出所有路径，《算法导论》在后续讲解实现的细节中也忽略了 NIL 结点，所以我们知道⼀下这个概念即可。

1.2、红黑树如何确保最长路径不超过最短路径的 2 倍

我们对红黑树的规则进行分析，我们来尝试思考一下为什么我们的红黑树能够保持最长路径不超过最短路径的两倍的？

• 首先，我们规则 4 可知，从根结点到 nullptr 结点的每条路径都有相同的黑色结点，那我们可以选取一个极端情况，就是有一颗树的最短路径就是全是黑色结点的路径，假设最短路径长度为 bh（black height）
• 其次，由规则 2 和 3 可知，任意一条路径不会有连续的红色结点，所以在极端情况下，最长路径就是一黑一红相隔组成，那么最长路径的长度为 2 * bh
• 综合红黑树的 4 点规则，理论上的全黑最短路径和一黑一红的最长路径并不是在每颗红黑树都存在。假设任意一条从根到 nullptr 结点路径长度为 x，那么 bh <= x <= 2 * bh。

所以我们红黑树的长度最极端的情况就是最长路径是最短路径的两倍，红黑树的这 4 条规则就限制了红黑树，使其最长路径不超过最短路径的 2 倍。

1.3、红黑树效率

红黑树的表达相对 AVL 树要抽象一些，AVL 树通过高度差直观的控制了平衡。红⿊树通过 4 条规则的颜色约束，间接的实现了近似平衡，他们效率都是同一档次，但是相对而⾔，插入相同数量的结点，红⿊树的旋转次数是更少的，因为他对平衡的控制没那么严格。

假设 N 是红黑树中的结点数量，h 为最短路径的长度，那么 2 ^ h - 1 <= N <= 2 ^ (h * 2) - 1，由此推出 h 约等于 logN，也就是意味着红黑树增删查改最坏也就是走最长路径 2 * logN，那么时间复杂度还是 O(logN)。

二、红黑树实现

2.1、红黑树结构

红黑树的结构与 AVL 树相比会多一个颜色变量，我们通过颜色变量来对我们的二叉树插入时进行调控，其他的和我们的 AVL 树是一样的。

颜色变量我们用枚举来实现：

enum Colour
{
	RED,
	BLACK
};

结点类型和 AVL 树差不多，新增一个 Colour 变量即可：

template<class K, class V>
struct RBTreeNode
{
	// 这⾥更新控制平衡也要加⼊parent指针
	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)
	{}
};

红黑树的类和 AVL 树一样：

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
private:
	Node* _root = nullptr;
};

2.2、红黑树插入

（1）红黑树插入一个值的流程

红黑树的插入代码不是很难，但是十分的抽象，我们先来看看它插入的一个具体流程，我们从这一点入手来看看它是怎么平衡树的。

流程：

1. 插入一个值按二叉搜索树规则进行插入，插入后我们只需要观察是否符合红黑树的 4 条规则
2. 如果是空树插入，新增结点是黑色结点（规则 2）。如果是非空树插入，新增结点必须是红色结点，因为非空树插入，新增黑色结点就破坏了规则 4，规则 4 是很难维护的。
3. 非空树插入后，新增结点必须是红色结点，如果父亲结点是黑色的，则没有违法任何规则，插入结束。
4. 非空树插入后，新增结点必须红色结点，如果父亲结点是红色的，则违法规则 3。进一步分析，c 为红色，p为红色，g必为黑（如果 g 也是红，p此时也是红，那违反了规则 3），这三个颜色固定了，关键的变化看 u 的情况，需要根据 u 分为以下几种情况分别处理。

说明：
下文中假设我们把新增结点标识为 c (cur)，c 的⽗亲标识为 p(parent)，p 的⽗亲标识为 g(grandfather)，p 的兄弟标识 u(uncle)。

（2）情况1：变色

我们区分不同情况，主要就是去判断 u 的颜色情况，把我们的红黑树分为上图中几种种不同情况。最简单的这里就不说了，就是 p 为黑色结点，此时插入一个红色结点的 c，就直接插入后就可以了。我们来看看第一种情况。

条件：
c 为红，p 为红，g 为黑，u 存在且为红，则将 p 和 u 变黑，g 变红。再把 g 当作新的 c，继续往上更新。

分析：
因为 p 和 u 都是红色，g 是黑色，把 p 和 u 变成黑色，左边子树路径各增加一个黑色结点，g 再变红，相当于保持 g 所在子树的黑色结点的数量不变，同时解决了 c 和 p 连续红色结点的问题，需要继续往上更新是因为，g 是红色，如果 g 的父亲还是红色（因为 g 原本是黑色，所以 g 的父亲可以是黑色也可以是红色），那么就还需要继续处理；如果 g 的父亲是黑色，则处理结束了。如果 g 就是整棵树的根，再把 g 变回黑色。

注意：
情况一只变色，不旋转。所以无论 c 是 p 的左还是右，p 是 g 的做还是右，都是上面的变色处理方式。

• 跟 AVL 树类似，上图我们展示了一种具体情况，但是实际中需要这样处理的有很多情况
• 下面第一张图将以上类似的情况处理进行了抽象表达，d/e/f 代表每条路径拥有 hb 个黑色结点的子树，a/b 代表每条路径拥有 hb - 1 个黑色结点的根为红色的子树，hb >= 0
• 剩下的图，分别展示了 hb == 0/hb == 1/hb == 2 的具体情况组合分析，当 hb == 2 时，这里组合情况上百亿种，这些样例是帮助我们理解，不论情况多少种，多么复杂，处理方式都是一样的，变色再往上处理即可，所以我们只需要看抽象图即可。

代码实现：
这个代码的实现是非常容易的，因为我们去改变我们的 p/u/g 的颜色即可。
先是判断我们是否满足情况一的条件：u 存在并且颜色为红。同时我们要注意区分我们 p/u 分别是在 g 的左边还是右边。

if (parent == grandfather->_left)
{
	if (uncle && uncle->_col == RED)
}
// or
if (parent == grandfather->_right)
{
	if (uncle && uncle->_col == RED)
}

此时让我们的 p/u/g 变色。

// u存在且为红 -> 变⾊再继续往上处理
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;

（3）情况2：单旋 + 变色

上面的情况学完，我们就能发现红黑树只是理论比较抽象，但是其实它的代码还是蛮简单的，我们情况 2 也是如此，但是这里用到了 AVL 树的一个旋转的情况，我们如果对旋转还不是特别了解或者不熟，建议看看上一章节。

条件：
c 为红，p 为红，g 为黑，u 不存在或者 u 存在且为黑，u 不存在，则 c 一定是新增结点，u 存在且为黑，则 c 一定不是新增，c 之前是黑色的，是在 c 的子树中插入，符合情况 1，变成将 c 从黑色变成红色，更新上来的。

如果我们 u 不存在，但是 c 却不是新增结点，而是更新上来的，此时，如果 c 原本是黑色，那 p 路径就比 u 的那个路径多了一个黑色结点，违法了规则 4，如果 c 原本是红色，也就是说原本 p 和 c 都是红色，违反了规则 3。所以 c 只能是新增结点。

如果我们 u 存在且为黑，但是 c 是新增的，也就是说在 c 新增前，我们 u 路径比 p 路径多一个 黑色结点，这不符合规则 4，所以我们 p 路径之前一定有一个 黑色结点，且此时变成红色了，所以只能是 c 结点。

分析：
p 必须变成黑色，才能解决连续红色结点的问题，u 不存在或者是黑色的，这里单纯的变色无法解决问题，需要旋转 + 变色。

• 如果 u 不存在，此时无论 g/c/p 的颜色怎么变，都无法满足规则，因为我们一定要让 p/c 其中一个变黑，此时 p 路径一定会比 u 路径多一个黑色结点，一定会违反规则 4。
• 如果 u 存在，此时 c 一定是更新上来的，此时如果让我们 p 变成黑色，g 是黑色或者红色，u也是黑色不变，这个操作相当于是给我们 p 路径单独增加了一个黑色结点，如果此时让 g 变成红色，那就相当于让我们 u 单独的减少了一个结点，因为只是一个路径增加或者减少，这样操作一定会违反规则 4。

综上我们一定得去进行旋转，只是单独修改颜色已经无法保证满足规则了。

如果 p 是 g 的左，c 是 p 的左，那么以 g 为旋转点进行右单旋，再把 p 变黑，g 变红即可。p 变成这棵树新的根，这样子树黑色的结点数量不变，没有连续的红色结点了，且不需要往上更新，因为 p 的父亲是黑色还是红色或者空都不违法规则（此时 p 变成了 g，而且 p 是黑色的）。

如果 p 是 g 的右，c 是 p 的右，那么以 g 为旋转点进行左单旋，再把 p 变黑，g 变红即可。p 变成这棵树新的根，这样子树黑色的结点数量不变，没有连续的红色结点了，且不需要往上更新，因为 p 的父亲是黑色还是红色或者空都不违法规则。

代码实现：
我们单旋 + 转换颜色的操作也很容易，单旋上一章讲了，这里就直接调用上一章节实现的单旋函数了。
同样的，先是判断我们是否满足情况二的条件：u 不存在或者颜色为黑，同时 p 与 g 的方向和 c 与 p 的方向相同（单旋特点）。当然由于我们 u 除了红色的情况，就只剩下黑色和不存在的情况了，所以我们实现了情况 1，情况 2直接else 即可，这里只要判断是不是单旋即可。

if (parent == grandfather->_left)
{
	if (cur == parent->_left)
}
// or
if (parent == grandfather->_right)
{
	if (cur == parent->_right)
}

此时我们执行旋转 + 换色的逻辑即可（p 变黑，g 变红即可）。

//  g
// p u
//c
//单旋
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
//or
//  g
// u p
//    c
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;

（4）情况3：双旋 + 变色

情况 3 与情况 2 其实是没有什么区别的，因为主要都是旋转 + 变色，而情况 3 的变色也不是特别复杂，只要理解了情况 2 和双旋，这个就能轻松实现了。

条件：
c 为红，p 为红，g 为⿊，u 不存在或者u存在且为黑，u 不存在，则 c 一定是新增结点，u 存在且为黑，则 c 一定不是新增，c 之前是黑色的，是在 c 的子树中插入，符合情况 1，变色将 c 从黑色变成红色，更新上来的。
和情况 2 是一样的道理。
如果我们 u 不存在，但是 c 却不是新增结点，而是更新上来的，此时，如果 c 原本是黑色，那 p 路径就比 u 的那个路径多了一个黑色结点，违法了规则 4，如果 c 原本是红色，也就是说原本 p 和 c 都是红色，违反了规则 3。所以 c 只能是新增结点。

如果我们 u 存在且为黑，但是 c 是新增的，也就是说在 c 新增前，我们 u 路径比 p 路径多一个 黑色结点，这不符合规则 4，所以我们 p 路径之前一定有一个 黑色结点，且此时变成红色了，所以只能是 c 结点。

分析：
p 必须变黑，才能解决连续红色结点的问题，u 不存在或者是黑色的，这⾥单纯的变色无法解决问题，需要旋转+变色。

• 如果 u 不存在，此时无论 g/c/p 的颜色怎么变，都无法满足规则，因为我们一定要让 p/c 其中一个变黑，此时 p 路径一定会比 u 路径多一个黑色结点，一定会违反规则 4。
• 如果 u 存在，此时 c 一定是更新上来的，此时如果让我们 p 变成黑色，g 是黑色或者红色，u也是黑色不变，这个操作相当于是给我们 p 路径单独增加了一个黑色结点，如果此时让 g 变成红色，那就相当于让我们 u 单独的减少了一个结点，因为只是一个路径增加或者减少，这样操作一定会违反规则 4。

综上我们一定得去进行旋转，只是单独修改颜色已经无法保证满足规则了。

如果 p 是 g 的左，c 是 p 的右，那么先以 p 为旋转点进行左单旋，再以 g 为旋转点进行右单旋，再把 c 变黑，g 变红即可。c 变成这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为 c 的父亲是黑色还是红⾊或者空都不违反规则（此时 c 变成了 g，而且 c 是黑色的）。

如果 p 是 g 的右，c 是 p 的左，那么先以 p 为旋转点进行右单旋，再以 g 为旋转点进行左单旋，再把 c 变黑，g 变红即可。c 变成这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为 c 的父亲是黑色还是红色或者空都不违反规则。

代码实现：
我们双旋 + 转换颜色的操作也很容易，双旋上一章讲了，这里就直接调用上一章节实现的双旋函数了。
同样的，先是判断我们是否满足情况三的条件：u 不存在或者颜色为黑，同时 p 与 g 的方向和 c 与 p 的方向不同（双旋特点）。当然由于我们 u 除了红色的情况，就只剩下黑色和不存在的情况了，所以我们实现了情况 1，情况 3直接else 即可，这里只要判断是不是双旋即可。

if (parent == grandfather->_left)
{
	if (cur == parent->_right)
}
// or
if (parent == grandfather->_right)
{
	if (cur == parent->_left)
}

此时我们执行旋转 + 换色的逻辑即可（c 变黑，g 变红即可）。

//  g
// p u
//  c
//双旋
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
//or
//  g
// u p
//  c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;

（5）插入代码实现

我们插入代码前半部分就是二叉搜索树的查找插入位置的办法，在插入后在用红黑树的方法去优化我们的树使其平衡。

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;
	}
	else
	{
		parent->_left = 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)
			{
				// u存在且为红 -> 变⾊再继续往上处理
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;
				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				// u存在且为⿊或不存在 -> 旋转+变⾊
				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
		{
			//  g
			// u p
			Node* uncle = grandfather->_left;
			// 叔叔存在且为红，-> 变⾊即可
			if (uncle && 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;
}

2.3、红黑树的查找

按⼆叉搜索树逻辑实现即可，搜索效率为 O(logN)

Node* Find(const K& key)
{
	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;
}

2.4、红黑树的验证

这里获取最长路径和最短路径，检查最长路径不超过最短路径的2倍是不可行的，因为就算满足这个条件，红黑树也可能颜色不满足规则，当前暂时没出问题，后续继续插入还是会出问题的。所以我们还是去检查 4 点规则，满足这 4 点规则，一定能保证最长路径不超过最短路径的 2 倍。

1. 规则 1 枚举颜色类型，天然实现保证了颜⾊不是黑色就是红色
2. 规则 2 直接检查根即可
3. 规则 3 前序遍历检查，遇到红色结点查孩子不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查父亲的颜色就方便多了。
4. 规则 4 前序遍历，遍历过程中用形参记录根到当前结点的 blackNum（黑色结点数量），前序遍历遇到黑色结点就++blackNum，⾛到空就计算出了一条路径的黑色结点数量。再任意一条路径黑色结点数量作为参考值，依次比较即可。

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);
}

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);
}

总结

以上便是我们红黑树的全部内容啦，红黑树的代码其实蛮简单的，主要就是思想比较抽象，我们想要学好它就得仔细琢磨，搞懂我们不同情况下的 u。多多画图、多多理解，搞懂了就会觉得非常容易啦，下一章节我们便来尝试封装我们的 map/set 容器，大家下一章再见。

🎇坚持到这里已经很厉害啦，辛苦啦🎇 ʕ • ᴥ • ʔ づ♡ど