红黑树 （Red-Black Tree）

前言

红黑树是一种平衡二叉树的变种，想要理解红黑树，一定要提先了解二叉搜索树（BST）和平衡二叉树（AVL Tree）。 关于这一知识的讲解，请看移步到我的平衡搜索二叉树（AVL）这篇博客文章。

相对于平衡二叉树，在节点的数据结构中额外存储了一个color字段，记录 Red 或者 Black。

性质

• 根节点是黑色节点
• 所有叶子节点（NIL节点）都是黑色的
• 任意节点的颜色，要么是黑色的要么是红色的
• 红色节点的子节点为黑色节点（即相邻的两个节点不可能同时为红色）
• 任意节点到每个叶子节点的所有路径中，所包含的黑色节点的数量是相同的

下图是一个标准的红黑树：

性质之间的组合：“任意节点到每个叶子节点的所有路径中，所包含的黑色节点的数量是相同的 & 红色节点的子节点是黑色节点”。这就保证了红黑树的“平衡性”。

红黑树的这种平衡叫做“黑色完美平衡”。如何在插入的时候仍然保持这种平衡就是我们所要学习的了。

由于这种平衡，其查询的复杂度自然也是O(log n)的。

插入操作

新节点会作为红色节点像二叉排序树一样，先找到插入位置然后插入到红黑树中。

这里有个问题，为什么要以红色节点插入红黑树中呢？这是因为如果以黑色节点插入，那必然会导致不同路径上的黑色节点数量不一致了，一定会破坏平衡。而红色节点插入后不一定会破坏平衡。

这也是红黑树相对于AVL树的优点，虽然平衡性上没有AVL严格，但是插入和删除的操作性能更好。

当完成插入后，若破坏掉了红黑树的平衡了，就进行平衡的调整。

插入的几种场景

1. 红黑树为空树时

直接插入作为根节点，并变色为黑色。

2. 插入节点的Key已经存在

把节点的value值更新掉，其他的（颜色）保持不变。

3. 若新值插入后，插入节点的父节点是黑色节点

直接插入，不影响平衡。

4. 若新值插入后，插入节点的父节点是红色节点

根据“红色节点的子节点为黑色节点”性质，显然这不满足红黑树的约束，即破坏了“黑色平衡”，故需要调整平衡。

而如何去调整平衡又分为更加细致的场景，在下文中会逐渐展开。

三种调整平衡的操作

• 左旋
• 右旋
• 变色

其中左旋、右旋在 AVL 中就已经用过了，针对“LL、RR、LR、RL”四种情况进行不同的旋转。变色即进行节点的颜色变换。

破坏平衡的插入的具体分析与处理

前文中谈到当插入后，插入节点的父节点是红色节点时就会破坏掉树的平衡。

下面的各种情形都是基于插入节点的父亲节点是红色的场景的，这一条件能推导出：插入节点如果有祖父节点那么该祖父节点一定是黑色的。

其实一定有祖父节点，如果没有说明其红色的父节点是根节点，但是红色节点是不可能作为根节点的。

根据处理方式的不同，我们将划分出两种不同的情形，其中第二种有更为细致的子情形：

• 叔叔节点存在并且为红色节点
• 叔叔节点不存在时或存在时为黑色节点

图中各节点的名称带有一些寓意：

N：表示新节点

P：表示父亲节点

U：表示叔叔节点

G：表示祖父节点

接下来我们就来看看在更加细致的不同情况下具体是如何调整平衡的。记住，G只能是黑色的。

1. 叔叔节点存在并且为红色节点

因为P、U都是红色，所以G为黑色（如果G为红色，那么P、G都应该为黑色才对）。

我们现在尝试去调整“黑色平衡”，我们如果把P染成黑色：

那么[G, P, N] 和 [G, U]路径上的黑色节点数量就不同了。

在P没变黑之前，[G, P, N] 和 [G, U]路径上的黑色节点数量一定是相同的。

所以如果要把P染黑，同时就需要把U染黑。

那是不是这样就可以了呢？如果单纯只看G领导的这颗树，那确实已经满足红黑树的性质了，但是如果G是一颗子树呢？

显然我们在G这颗子树中黑色节点在根节点到叶子节点的路径中的数量增加了1，一定会破坏掉整体的平衡。所以需要把G变成红色来维护这种平衡：

反之，如果G不是一颗子树，G就是当前红黑树的树根，那么G压根就不需要再变色了。这是唯一一种会增加红黑树路径中黑色节点数量的插入。

像图中这种情况，G作为一个红色节点显然它的父亲节点不能是红色节点，故还需要继续处理平衡。

此时就可以采取递归的思想，将变红的G节点作为新的插入节点重新插入到去除了G节点的树中。

反之，如果G的父节点是黑色的，就不需要做任何处理了。

故对以上处理过程进行总结：

• 将P、U节点变色为黑色；

• 若G为根节点，则保持黑色不变；反之变红。

• 若G需要变为红色，如果其父亲节点为红色节点，则需要递归重新插入G节点到红黑树中。

这一场景的处理过程其实比较简单，一步一步解释并配图是为了展现思考的过程，避免直接给出结论，不知其所以然。

2. 叔叔节点不存在或者存在但为黑色节点

1️⃣ N与P保持同一的向左方向

例如下面两种情况：

此时都可以通过G的右旋，并将P置为黑色、G变为红色就可以调整为平衡。

图中是省略了P U的子节点（子树）信息的或者是由Case中的变色导致的，否则不是一个红黑树，因为[G, P] 和 [G, U]路径上的黑色节点数不一致。把图补全后如下所示：

2️⃣ P 向左，N 向右边

这种有点LR型的样子。处理方式 P 先左旋变成LL型，再进行G的右旋。

3️⃣ N与P保持同一的向右方向

与1️⃣类似，通过左旋完成。

4️⃣ P 向右，N 向左

与3️⃣类似，先右旋再左旋。

红黑树与AVL树的区别

平衡条件的差异

• AVL树: 严格平衡，每个节点的左右子树高度差最多为1。
• 红黑树: 相对宽松，只要求从根到叶子的最长路径不超过最短路径的两倍。

这意味着，在插入和删除操作中，AVL树需要更频繁地调整（旋转）以保持平衡，代价更高。

旋转次数

• AVL树: 插入或删除节点后，可能需要多次旋转来恢复平衡。
• 红黑树: 插入或删除节点后，最多需要3次旋转来恢复平衡。

由于红黑树的调整次数少，它在操作频繁的情况下（例如大规模插入或删除）性能会优于AVL树。

适用场景

• 红黑树更常用于需要高频插入和删除的场景，例如：
  • Java的TreeMap和TreeSet。
  • Linux内核中的CFS调度器。
• AVL树更适合读多写少的场景，因为它的查找性能更接近完美的平衡树。