红黑树详解

2020 年 5 月 11 日
笔记
数据结构基础：树

红黑树（英语：Red–Black Tree，简称 RB-Tree）是一种平衡的二叉查找树，用途广泛。例如：

Java 中的：java.util.TreeMap，java.util.TreeSet；
C++ STL 中的：map，multimap，multiset。

它是在 1972 年由 Rudolf Bayer 发明的，他称之为 “对称二叉 B 树”，它现代的名字（即 “红黑树”）是 Leo J. Guibas 和 Robert Sedgewick 于 1978 年写的一篇论文中获得的。

红黑树的实现比较复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的，它可以在 \(O(logn)\) 时间内做查找，插入和删除操作。

红黑树有四个性质（也有书籍和博客上说是五个性质，其实四个性质足矣）：

每个结点要么是红的，要么是黑的；
根结点是黑色的；
如果一个结点是红色的，则它的两个孩子都是黑色的；
对于任意一个结点，其到叶子结点的每条路径上都包含相同数目的黑色结点。

红黑树的实现和理解还是很复杂的，所以建议读者在阅读本文前，最好已经理解和掌握了二叉查找树和 AVL 树。

具体实现与代码分析

和 AVL 树通过约束左右子树高度不同，红黑树是通过它的四条性质来实现 “平衡状态”，在插入结点或者删除结点时，可能会造成某个结点违反了上述的某条性质，那么红黑树的做法就是通过 “重新着色” 和 “旋转” 两种方式使之重新符合性质。

“重新着色” 这很简单，现在来看下 “旋转” 是怎么旋转的。一共有两种旋转方式：左旋和右旋。

左旋

void RBTree::rotate_left(Node* x)
{
	Node* y = x->right;

	x->right = y->left;
	if (y->left)
		y->left->parent = x;
	y->parent = x->parent;

	if (x == root)
		root = y;
	else if (x == x->parent->left)
		x->parent->left = y;
	else
		x->parent->right = y;

	y->left = x;
	x->parent = y;
}

右旋

void RBTree::rotate_right(Node* x)
{
	Node* y = x->left;

	x->left = y->right;
	if (y->right)
		y->right->parent = x;
	y->parent = x->parent;

	if (x == root)
		root = y;
	else if (x == x->parent->right)
		x->parent->right = y;
	else
		x->parent->left = y;

	y->right = x;
	x->parent = y;
}

很容易看出，左旋和右旋其实就是两个镜像操作而已。

好了，真是千呼万唤始出来，重点终于来了！

插入操作

将红黑树当作一颗二叉查找树，将结点插入，插入后，该树仍然是一棵二叉查找树，但是它可能已经不是红黑树了，所以接下来就要通过 “旋转” 和 “重新着色” 来使它重新成为红黑树。

首先，我们把新插入的结点着色为红色。为什么偏偏是红色呢？先回顾下红黑树的四条性质：

每个结点要么是红的，要么是黑的；
根结点是黑色的；
如果一个结点是红色的，则它的两个孩子都是黑色的；
对于任意一个结点，其到叶子结点的每条路径上都包含相同数目的黑色结点。

将插入的结点着色为红色，不会违背 “性质4″。而少违背一条性质，就意味着我们需要处理的情况越少。

接着，我们再来看看插入结点会遇到哪几种情况，分析发现，一共有三种：

被插入结点是根结点，那我们把此结点涂为黑色就行了；
被插入结点的父亲结点是黑色的，那么什么也不需要做，结点被插入后，仍然是红黑树。
被插入结点的父亲结点是红色的，那么此时是违背 “性质 3” 的，需要调整。

那么，如何调整呢？分析一下，此种情况，被插入结点是一定存在祖父（即父亲的父亲）结点的，且可以进一步再划分为 6 种情况，因为涉及到镜像操作，所以我们只需理解其中一边镜像的 3 种情况即可。

为方便叙述，我们把 “新插入结点” 称为 “当前结点”，那么 “当前结点” 的父亲的父亲就叫做 “祖父结点”，而 “祖父结点” 如果还有一个儿子的话，我们就称其为 “叔叔结点”。

Case 1 ：当前结点的父亲是红色，叔叔存在且也是红色

图中，”结点 1″ 为 “当前结点”。那么我们的处理策略就是：
- 将 “父亲结点” 改为黑色；
- 将 “叔叔结点” 改为黑色；
- 将 “祖父结点” 改为红色；
- 将 “祖父结点” 设为 “当前结点”，继续进行操作。
处理完后，图中显示的两条路径上，黑色结点数相同且和原图数目一致。
Case 2：当前结点的父亲是红色，叔叔不存在或是黑色，且当前结点是其父亲的右孩子

图中，”结点 2″ 为 “当前结点”。那么我们的处理策略就是：
- 将 “父亲结点” 设为 “当前结点”；
- 以新的 “当前结点” 为支点进行左旋。
处理完后，我们发现依旧不满足红黑树的性质，别急，这就是 “Case 3″。
Case 3：当前结点的父亲是红色，叔叔不存在或是黑色，且当前结点是其父亲的左孩子

图中，”结点 1″ 为 “当前结点”。那么我们的处理策略就是：
- 将 “父亲结点” 改为黑色；
- 将 “祖父结点” 改为红色；
- 以 “祖父结点” 为支点进行右旋。
处理完后，图中显示的两条路径上，黑色结点数相同且和原图数目一致。

代码如下：

void RBTree::insert_rebalance(Node* x)
{
	x->color = red;

	while (x != root && x->parent->color == red)
	{
		if (x->parent == x->parent->parent->left)
		{
			Node* y = x->parent->parent->right;

			if (y && y->color == red)           /* Case 1 */
			{
				x->parent->color = black;
				y->color = black;
				x->parent->parent->color = red;
				x = x->parent->parent;
			}
			else
			{
				if (x == x->parent->right)      /* Case 2 */
				{
					x = x->parent;
					rotate_left(x);
				}

				x->parent->color = black;       /* Case 3 */
				x->parent->parent->color = red;
				rotate_right(x->parent->parent);
				break;
			}
		}
		else  /* left <-> right */
		{
			Node* y = x->parent->parent->left;

			if (y && y->color == red)
			{
				x->parent->color = black;
				y->color = black;
				x->parent->parent->color = red;
				x = x->parent->parent;
			}
			else
			{
				if (x == x->parent->left)
				{
					x = x->parent;
					rotate_right(x);
				}

				x->parent->color = black;
				x->parent->parent->color = red;
				rotate_left(x->parent->parent);
				break;
			}
		}
	}

	root->color = black;
}

Node* RBTree::insert(int key)
{
	if (root == nullptr)
	{
		root = new Node(key);
		root->color = black;
		return root;
	}

	Node* cur = root;
	Node* pre = nullptr;

	while (cur)
	{
		pre = cur;
		if (key < cur->key)
			cur = cur->left;
		else if (key > cur->key)
			cur = cur->right;
		else
			return nullptr; /* 不可重复插入 */
	}

	cur = new Node(key);
	cur->parent = pre;

	if (key < pre->key)
		pre->left = cur;
	else
		pre->right = cur;

	insert_rebalance(cur);

	return cur;
}

删除操作

首先，和删除一棵普通二叉查找树的结点相同，我们会遇到三种情况：

“被删结点” 没有孩子，如果它是红色的，那么可以直接删除；如果是黑色的，这点比较特殊，读者直接跟读代码就可以理解，很简单；
“被删结点” 只有一个孩子，那么删除该结点后，用这个孩子去替换它即可；
“被删结点” 有两个孩子，那么先找出它的 “后继结点”，然后用 “后继结点” 去替换 “被删结点”，把问题转化为删除 “后继结点” ，也就是说， “后继结点” 才是真正的 “被删结点”。

为方便接下来的叙述，我们把 “被删结点” 称为 “原先结点”，而用来替换 “被删结点” 的结点称为 “当前结点”。

接着，我们来看看 “原先结点” 被删掉后，会遇到哪几种情况，分析发现，一共有四种：

“原先结点” 为黑色，”当前结点” 为红色，那么我们把 “原先结点” 删掉后，拿 “当前结点” 去替换它，并修改颜色为黑色即可；
“原先结点” 为黑色，”当前结点” 为黑色，这种情况比较复杂，待会再说；
“原先结点” 为红色，”当前结点” 为红色，那么我们把 “原先结点” 删掉后，直接拿”当前结点” 去替换它即可；
“原先结点” 为红色，”当前结点” 为黑色，这和 “情况 3″ 一样，直接拿”当前结点” 去替换它即可。

最后，我们只需看下上述的 “情况 2″。这种情况可以进一步再划分为 8 种情况，因为涉及到镜像操作，所以我们只需理解其中一边镜像的 4 种情况即可（注意，下面的图片上，”原先结点” 已被删除，故未画出，我们只画出了 “当前结点” ）：

Case 1：当前结点是黑色，兄弟结点是红色

“结点 1” 为 “当前结点”。观察上图，因 “原先结点” 已被删除，故路径2->1上少了一个黑色结点（右侧路径的黑色结点未画完全），那么我们的处理策略就是：
- 将 “兄弟结点” 改为黑色；
- 将 “父亲结点” 改为红色；
- 以 “父亲结点” 为支点进行左旋；
- 左旋后，重新设置 “兄弟结点”。
处理完后，我们发现路径2->1上依旧是 2 个黑色结点，说明当前状态并不满足红黑树性质。其实，这是进入了下面的 Case 2，Case 3，和 Case 4 阶段了，请继续往下看。
Case 2：当前结点是黑色，兄弟结点是黑色，两个孩子为空或是黑色

“结点 1” 为 “当前节点”。观察上图，因 “原先结点” 已被删除，故路径2->1上少了一个黑色结点，那么我们的处理策略就是：
- 将 “兄弟结点” 改为红色；
- 将 “父亲结点” 设置为新的 “当前结点”，继续进行操作。
处理完后，我们发现路径2->1上还是只有 1 个黑色结点，且有两个红色结点相连，说明当前状态不满足红黑树性质，但是我们发现只要把 “结点 2” 着色为黑色不就行了么，这也就是erase_rebalance()代码最后出现if(x) x->color = black;的缘由之一（x指向的是 “当前结点”）。
Case 3：当前结点是黑色，兄弟结点是黑色，兄弟结点的左孩子是红色，右孩子为空或是黑色

“结点 1” 为 “当前结点”。观察上图，因 “原先结点” 已被删除，故路径2->1上少了一个黑色结点，那么我们的处理策略就是：
- 将 “兄弟结点” 的左孩子改为黑色；
- 将 “兄弟结点” 改为红色；
- 以 “兄弟结点” 为支点进行右旋；
- 右旋后，重新设置 “当前结点” 的 “兄弟结点”。
处理完后，我们发现图中2->1上还是只有 1 个黑色结点，说明当前状态不满足红黑树性质。其实这是进入了Case 4。
Case 4：当前结点是黑色，兄弟结点是黑色，兄弟结点的右孩子是红色，左孩子为空或红黑皆可

“结点 1” 为 “当前结点”。观察上图，因 “原先结点” 已被删除，故路径 2->1 上少了一个黑色结点，那么我们的处理策略就是：
- 将 “父亲结点” 的颜色赋给 “兄弟结点”；
- 将 “父亲结点” 改为黑色；
- 将 “兄弟结点” 的右孩子改为黑色；
- 以 “父亲结点” 为支点进行左旋；
处理完后，一切 OK。

代码如下：

void RBTree::erase_rebalance(Node* z)
{
	Node* y = z;
	Node* x = nullptr;
	Node* x_parent = nullptr;

	if (y->left == nullptr)
		x = y->right;
	else if (y->right == nullptr)
		x = y->left;
	else /* 结点 z 的孩子都存在 */
	{
		y = y->right;
		while (y->left)
			y = y->left; /* 找到后继结点 */

		x = y->right;
	}

	/* y != z 说明结点 z 的孩子都存在 */
	if (y != z)
	{
		z->left->parent = y;
		y->left = z->left;

		if (y != z->right)
		{
			x_parent = y->parent;
			if (x)
				x->parent = y->parent;
			y->parent->left = x;
			y->right = z->right;
			z->right->parent = y;
		}
		else
			x_parent = y;

		if (root == z)
			root = y;
		else if (z->parent->left == z)
			z->parent->left = y;
		else
			z->parent->right = y;

		y->parent = z->parent;
		swap(y->color, z->color);
		y = z;
	}
	else
	{
		x_parent = y->parent;
		if (x)
			x->parent = y->parent;

		if (root == z)
			root = x;
		else if (z->parent->left == z)
			z->parent->left = x;
		else
			z->parent->right = x;
	}
	
	/* 
	经过上边的处理，y 指向真正要删除的结点（即文中所定义的 "原先结点"）；x 为 y 的左孩子
	或右孩子（也可能为空），作为结点 y 被删除后的替补结点（即文中所定义的 "当前结点"）。
	*/

	if (y->color == black)
	{
		if (x != root && (x == nullptr || x->color == black))
		{
			if (x == x_parent->left)
			{
				Node* w = x_parent->right;

				if (w->color == red)                                     /* Case 1 */
				{
					w->color = black;
					x_parent->color = red;
					rotate_left(x_parent);
					w = x_parent->right;
				}

				if ((w->left == nullptr || w->left->color == black) &&   /* Case 2 */
					(w->right == nullptr || w->right->color == black))
				{
					w->color = red;
					x = x_parent;
					x_parent = x_parent->parent;
				}
				else
				{
					if (w->right == nullptr || w->right->color == black) /* Case 3 */
					{
						if (w->left)
							w->left->color = black;
						w->color = red;
						rotate_right(w);
						w = x_parent->right;
					}

					w->color = x_parent->color;                          /* Case 4 */
					x_parent->color = black;
					if (w->right)
						w->right->color = black;
					rotate_left(x_parent);
				}
			}
			else  /* left <-> right */
			{
				Node* w = x_parent->left;

				if (w->color == red)
				{
					w->color = black;
					x_parent->color = red;
					rotate_right(x_parent);
					w = x_parent->left;
				}

				if ((w->right == nullptr || w->right->color == black) &&
					(w->left == nullptr || w->left->color == black))
				{
					w->color = red;
					x = x_parent;
					x_parent = x_parent->parent;
				}
				else
				{
					if (w->left == nullptr || w->left->color == black)
					{
						if (w->right)
							w->right->color = black;
						w->color = red;
						rotate_left(w);
						w = x_parent->left;
					}

					w->color = x_parent->color;
					x_parent->color = black;
					if (w->left)
						w->left->color = black;
					rotate_right(x_parent);
				}
			}
		}

		if (x)
			x->color = black;
	}
}

void RBTree::erase(int key)
{
	Node* z = find(key);

	if (z)
	{
		erase_rebalance(z);
		delete z;
	}
}

完整代码

#include <iostream>
#include <algorithm>

using namespace std;

enum { red = 0, black = 1 };

struct Node
{
	int key;
	bool color;
	Node* parent;
	Node* left;
	Node* right;
	Node(int key = 0)
	{
		this->key = key;
		this->color = red;
		this->parent = this->left = this->right = nullptr;
	}
};

class RBTree
{
private:
	Node* root;

private:
	void rotate_left(Node* x);
	void rotate_right(Node* x);
	void destroy(Node* node);
	void insert_rebalance(Node* x);
	void erase_rebalance(Node* z);
	void in_order(Node* node);

public:
	RBTree();
	~RBTree();
	Node* insert(int key);
	Node* find(int key);
	void erase(int key);
	void print();
};

RBTree::RBTree()
{
	root = nullptr;
}

void RBTree::destroy(Node* node)
{
	if (node == nullptr)
		return;

	destroy(node->left);
	destroy(node->right);
	delete node;
}

RBTree::~RBTree()
{
	destroy(root);
	root = nullptr;
}

void RBTree::rotate_left(Node* x)
{
	Node* y = x->right;

	x->right = y->left;
	if (y->left)
		y->left->parent = x;
	y->parent = x->parent;

	if (x == root)
		root = y;
	else if (x == x->parent->left)
		x->parent->left = y;
	else
		x->parent->right = y;

	y->left = x;
	x->parent = y;
}

void RBTree::rotate_right(Node* x)
{
	Node* y = x->left;

	x->left = y->right;
	if (y->right)
		y->right->parent = x;
	y->parent = x->parent;

	if (x == root)
		root = y;
	else if (x == x->parent->right)
		x->parent->right = y;
	else
		x->parent->left = y;

	y->right = x;
	x->parent = y;
}

Node* RBTree::find(int key)
{
	Node* z = root;

	while (z)
	{
		if (key < z->key)
			z = z->left;
		else if (key > z->key)
			z = z->right;
		else
			return z;
	}

	return z;
}

void RBTree::insert_rebalance(Node* x)
{
	x->color = red;

	while (x != root && x->parent->color == red)
	{
		if (x->parent == x->parent->parent->left)
		{
			Node* y = x->parent->parent->right;

			if (y && y->color == red)           /* Case 1 */
			{
				x->parent->color = black;
				y->color = black;
				x->parent->parent->color = red;
				x = x->parent->parent;
			}
			else
			{
				if (x == x->parent->right)      /* Case 2 */
				{
					x = x->parent;
					rotate_left(x);
				}

				x->parent->color = black;       /* Case 3 */
				x->parent->parent->color = red;
				rotate_right(x->parent->parent);
				break;
			}
		}
		else  /* left <-> right */
		{
			Node* y = x->parent->parent->left;

			if (y && y->color == red)
			{
				x->parent->color = black;
				y->color = black;
				x->parent->parent->color = red;
				x = x->parent->parent;
			}
			else
			{
				if (x == x->parent->left)
				{
					x = x->parent;
					rotate_right(x);
				}

				x->parent->color = black;
				x->parent->parent->color = red;
				rotate_left(x->parent->parent);
				break;
			}
		}
	}

	root->color = black;
}

Node* RBTree::insert(int key)
{
	if (root == nullptr)
	{
		root = new Node(key);
		root->color = black;
		return root;
	}

	Node* cur = root;
	Node* pre = nullptr;

	while (cur)
	{
		pre = cur;
		if (key < cur->key)
			cur = cur->left;
		else if (key > cur->key)
			cur = cur->right;
		else
			return nullptr; /* 不可重复插入 */
	}

	cur = new Node(key);
	cur->parent = pre;

	if (key < pre->key)
		pre->left = cur;
	else
		pre->right = cur;

	insert_rebalance(cur);

	return cur;
}

void RBTree::erase_rebalance(Node* z)
{
	Node* y = z;
	Node* x = nullptr;
	Node* x_parent = nullptr;

	if (y->left == nullptr)
		x = y->right;
	else if (y->right == nullptr)
		x = y->left;
	else /* 结点 z 的孩子都存在 */
	{
		y = y->right;
		while (y->left)
			y = y->left; /* 找到后继结点 */

		x = y->right;
	}

	/* y != z 说明结点 z 的孩子都存在 */
	if (y != z)
	{
		z->left->parent = y;
		y->left = z->left;

		if (y != z->right)
		{
			x_parent = y->parent;
			if (x)
				x->parent = y->parent;
			y->parent->left = x;
			y->right = z->right;
			z->right->parent = y;
		}
		else
			x_parent = y;

		if (root == z)
			root = y;
		else if (z->parent->left == z)
			z->parent->left = y;
		else
			z->parent->right = y;

		y->parent = z->parent;
		swap(y->color, z->color);
		y = z;
	}
	else
	{
		x_parent = y->parent;
		if (x)
			x->parent = y->parent;

		if (root == z)
			root = x;
		else if (z->parent->left == z)
			z->parent->left = x;
		else
			z->parent->right = x;
	}
	
	/* 
	经过上边的处理，y 指向真正要删除的结点（即文中所定义的 "原先结点"）；x 为 y 的左孩子
	或右孩子（也可能为空），作为结点 y 被删除后的替补结点（即文中所定义的 "当前结点"）。
	*/

	if (y->color == black)
	{
		if (x != root && (x == nullptr || x->color == black))
		{
			if (x == x_parent->left)
			{
				Node* w = x_parent->right;

				if (w->color == red)                                     /* Case 1 */
				{
					w->color = black;
					x_parent->color = red;
					rotate_left(x_parent);
					w = x_parent->right;
				}

				if ((w->left == nullptr || w->left->color == black) &&   /* Case 2 */
					(w->right == nullptr || w->right->color == black))
				{
					w->color = red;
					x = x_parent;
					x_parent = x_parent->parent;
				}
				else
				{
					if (w->right == nullptr || w->right->color == black) /* Case 3 */
					{
						if (w->left)
							w->left->color = black;
						w->color = red;
						rotate_right(w);
						w = x_parent->right;
					}

					w->color = x_parent->color;                          /* Case 4 */
					x_parent->color = black;
					if (w->right)
						w->right->color = black;
					rotate_left(x_parent);
				}
			}
			else  /* left <-> right */
			{
				Node* w = x_parent->left;

				if (w->color == red)
				{
					w->color = black;
					x_parent->color = red;
					rotate_right(x_parent);
					w = x_parent->left;
				}

				if ((w->right == nullptr || w->right->color == black) &&
					(w->left == nullptr || w->left->color == black))
				{
					w->color = red;
					x = x_parent;
					x_parent = x_parent->parent;
				}
				else
				{
					if (w->left == nullptr || w->left->color == black)
					{
						if (w->right)
							w->right->color = black;
						w->color = red;
						rotate_left(w);
						w = x_parent->left;
					}

					w->color = x_parent->color;
					x_parent->color = black;
					if (w->left)
						w->left->color = black;
					rotate_right(x_parent);
				}
			}
		}

		if (x)
			x->color = black;
	}
}

void RBTree::erase(int key)
{
	Node* z = find(key);

	if (z)
	{
		erase_rebalance(z);
		delete z;
	}
}

void RBTree::in_order(Node* node)
{
	if (node == nullptr)
		return;

	in_order(node->left);
	cout << "( " << node->key << ", " << node->color << " )" << endl;
	in_order(node->right);
}

void RBTree::print()
{
	in_order(root);
	cout << endl;
}

int main()
{
	cout << "red: " << red << ", black: " << black << endl << endl;

	RBTree rb_tree;

	/* test "insert" */
	rb_tree.insert(7);
	rb_tree.insert(2);
	rb_tree.insert(1); rb_tree.insert(1);
	rb_tree.insert(5);
	rb_tree.insert(3);
	rb_tree.insert(6);
	rb_tree.insert(4);
	rb_tree.insert(9);
	rb_tree.insert(8);
	rb_tree.insert(11); rb_tree.insert(11);
	rb_tree.insert(10);
	rb_tree.insert(12);
	rb_tree.print();

	/* test "find" */
	Node* p = nullptr;
	cout << ((p = rb_tree.find(2)) ? p->key : -1) << endl;
	cout << ((p = rb_tree.find(100)) ? p->key : -1) << endl << endl;

	/* test "erase" */
	rb_tree.erase(1);
	rb_tree.print();
	rb_tree.erase(9);
	rb_tree.print();
	rb_tree.erase(11);
	rb_tree.print();

	return 0;
}

数据测试如下：

( 1, 1 )
( 2, 1 )
( 3, 1 )
( 4, 0 )
( 5, 1 )
( 6, 1 )
( 7, 1 )
( 8, 1 )
( 9, 0 )
( 10, 0 )
( 11, 1 )
( 12, 0 )

2
-1

( 2, 1 )
( 3, 1 )
( 4, 1 )
( 5, 1 )
( 6, 1 )
( 7, 1 )
( 8, 1 )
( 9, 0 )
( 10, 0 )
( 11, 1 )
( 12, 0 )

( 2, 1 )
( 3, 1 )
( 4, 1 )
( 5, 1 )
( 6, 1 )
( 7, 1 )
( 8, 1 )
( 10, 0 )
( 11, 1 )
( 12, 0 )

( 2, 1 )
( 3, 1 )
( 4, 1 )
( 5, 1 )
( 6, 1 )
( 7, 1 )
( 8, 1 )
( 10, 0 )
( 12, 1 )

时间复杂度

最坏情况，输入的序列为升序或降序，此时红黑相间的路径长度是全黑路径长度的 2 倍，时间复杂度为 \(O_{worst}(2logn)\)。

平均情况，时间复杂度为 \(O_{avg}(logn)\)。

需注意的地方

有三个需要注意的地方。

insert_rebalance

insert_rebalance 操作可能会有 \(O(logn)\) 量级的回溯（第一个注意点）。

当程序进入 insert_rebalance 的 while (x != root() && x->parent->color == red) 后，它只会有如下 6 种运行方式：

Case 1；
Case 1 —-> Case 1 —-> Case 1 ……；
Case 1 —-> …… —-> Case 2 —-> Case 3；
Case 1 —-> …… —-> Case 3；
Case 2 —-> Case 3；
Case 3；

而这回溯就发生在第 2，3，4 种，我们就以第 2 种的为例，如下图，

“结点 1” 为新插入结点，此时属于 “Case 1：当前结点的父亲是红色，叔叔存在且也是红色”。那么我们的处理策略就是：

将 “父亲结点” 改为黑色；
将 “叔叔结点” 改为黑色；
将 “祖父结点” 改为红色；
将 “祖父结点” 设为 “当前结点”，继续进行操作。

但处理完后，根据代码 while (x != root() && x->parent->color == red)，我们发现 “当前结点” 又进入了 Case 1。假设每次处理完后都会进入 Case 1，那么这样的处理操作会直到根结点才会结束。

另外，根据运行方式第 3，4，5，6 种，我们发现，一旦 Case 3 处理完后，整个 insert_rebalance 随之结束，这就是为什么在 Case 3 的处理代码下方加入一行 break; 的原因（第二个注意点）。

erase_rebalance

可能会有人好奇 erase_rebalance 为何使用 if (x != root() && (x == nullptr || x->color == black))，而不是 while (x != root() && (x == nullptr || x->color == black))。

那是因为 erase_rebalance 不存在回溯问题（第三个注意点）。

当程序进入 if (x != root() && (x == nullptr || x->color == black)) 后，它只会有如下 6 种运行方式：

Case 1 —-> Case 2；
Case 1 —-> Case 3 —-> Case 4；
Case 1 —-> Case 4;
Case 2；
Case 3 —-> Case 4；
Case 4;

与 AVL 树的比较

对比之下，我们发现：AVL 树可以说是完全平衡的平衡二叉树，因为它的硬性规定就是左右子树高度差不超过 1；而红黑树，更准确地说，它应该是 “几于平衡” 的平衡二叉树，在最坏情况下，红黑相间的路径长度是全黑路径长度的 2 倍。

有趣的是，某些底层数据结构（如 Linux, STL ……）选用的都是红黑树而非 AVL 树，这是为何？

对于 AVL 树，在插入或删除操作后，都要利用递归的回溯，去维护从被删结点到根结点这条路径上的所有结点的平衡性，回溯的量级是需要 \(O(logn)\) 的，其中插入操作最多需要两次旋转，删除操作可能是 1 次、2 次或 2 次以上。而红黑树在 insert_rebalance 的时候最多需要 2 次旋转，在 erase_rebalance 的时候最多也只需要 3 次旋转。
其次，AVL 树的结构相较红黑树来说更为平衡，故在插入和删除结点时更容易引起不平衡。因此在大量数据需要插入或者删除时，AVL 树需要 rebalance 的频率会更高，相比之下，红黑树的效率会更高。

参考

SGI_STL. stl_tree.h.
维基百科. 红黑树.
//algs4.cs.princeton.edu/33balanced/.
//www.cs.princeton.edu/~rs/talks/LLRB/Java/.
//www.cnblogs.com/skywang12345/p/3624291.html

Tags: 数据结构基础：树