数据结构与算法——红黑树

前面我们提到了二叉查找树，支持快速的查找、插入和删除操作。中序遍历二叉查找树，可以输出有序的数据序列，非常高效。

但是，二叉查找树存在一个问题，一般情况下二叉查找树的搜索、插入、删除的复杂度等于树高，时间复杂度为 ，不过在频繁的插入、删除过程中，可能会出现树的高度远大于 的情况，导致各种操作效率急剧下降，最坏的情况下，二叉树会退化为链表，时间复杂度为 。

由于这个原因，所以出现了很多改进版的平衡二叉树查找树，比如 AVL 树，红黑树等。

工程中，红黑树用的最多，这也是我们为什么以红黑树为代表来介绍。

平衡二叉查找树

平衡二叉查找树是改进版的二叉查找树。一般的二叉查找树的查询复杂度取决于目标节点到树根节点的距离，即深度。因此当目标节点的深度普遍较大的时候，查询的平均复杂度会上升。为了实现更高效率的查询，诞生了平衡二叉查找树。

那么平衡二叉查找树是怎样提高查询效率的呢，平衡二叉查找树规定，树中任意节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是 。例如上面提到的 AVL 树，它就是严格符合上面的这个定义。

但也有一些平衡二叉树并没有严格符合上面的定义（树中任意节点对应的两棵子树的最大高度差为1），比如我们今天要介绍的红黑树，它从根节点到各个叶子节点的最长路径，有可能会比最短路径大一倍。

平衡二叉查找树这种二叉树之所以出现，是为了解决普通二叉查找树在频繁的插入，删除操作时，时间复杂度退化的问题。所以最终能够解决这个问题就好，并不一定要严格符合平衡二叉查找树的定义。所谓“平衡”，简单来说就是让整棵树左右子树比较“平衡”，不要出现相差很大的情况。这样树的高度就能相对小一些，对应的各个操作的效率就会高一些。

红黑树

顾名思义，之所以叫红黑树，是因为它的每个节点都带有一个颜色属性，颜色为红色或黑色。另外还有如下额外的要求：

1. 根节点是黑色
2. 节点是红色或黑色
3. 所有叶子节点都是黑色，叶子节点为 NIL 节点，不储存数据
4. 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

下图是一个红黑树的示例：

红黑树

这些约束确保了红黑树的关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的。

红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。

操作

因为每一个红黑树也是一个特化的二叉查找树，因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。但是，在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。所以我们会在执行插入和删除的时候对节点颜色进行修改和树旋转，用来保证红黑树的性质。

颜色修改很简单，就是在红黑两种颜色之间变化，那么树旋转是什么呢？树旋转是对二叉树的一种操作，不影响元素的顺序，但会改变树的结构，将一个节点上移、一个节点下移。从旋转上的不同又分为左旋转和右旋转。我们通过图来看一下：

image image

理解树旋转过程的关键，在于理解其中不变的约束。旋转操作不会导致叶节点顺序的改变（可以理解为旋转操作前后，树的中序遍历结果是一致的），旋转过程中也始终受二叉搜索树的主要性质约束：右子节点比父节点大、左子节点比父节点小。

插入操作

我们来看一下插入数据的过程。

我们首先以二叉查找树的方法增加节点并标记它为红色。（如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑节点，这个是很难调整的。但是设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过颜色调换（color flips）和树旋转来调整。）

其中有两种特殊的情况：

• 如果插入节点的父节点是黑色的，那我们什么都不用做，它仍然满足红黑树的定义。
• 如果插入的节点是根节点，那我们直接改变它的颜色，把它变成黑色就可以了。

除此之外，其他的插入操作都会破坏红黑树的性质，我们都需要通过改变颜色和树旋转进行调整。

红黑树的平衡调整过程是一个迭代的过程。我们把正在处理的节点叫做关注节点。关注节点会随着不停地迭代处理，而不断发生变化。最开始的关注节点就是新插入的节点。

新的节点插入之后，如果红黑树的性质被破坏，一般会有三种情况，我们只需要根据每种情况，做出对应的调整，使其继续符合红黑树的性质即可。我们来具体看一下三种情况的调整过程。在此之前我们，我们将使用术语叔父节点来指一个节点的父节点的兄弟节点，父节点的父节点叫做祖父节点。

情况一：关注节点 a，它的叔父节点 d 是红色

• 将 a 的父节点b，叔父节点 d 的颜色都设置为黑色；
• 将 a 的祖父节点 c 的颜色设置为红色；
• 关注节点由 a 变成 c；
• 跳转到情况二或者情况三。

情况二：关注节点是 a，它的叔父节点 d 是黑色，关注节点 a 是其父节点 b 的右子节点

• 关注节点变成节点 a 的父节点 b；
• 围绕新的关注节点 b 左旋；
• 跳到情况三。

情况三：关注节点是 a，它的叔父节点 d 是黑色，关注节点 a 是其父节点 b 的左子节点

• 围绕关注节点 a 的祖父节点 c 右旋；
• 将关注节点 a 的父节点 b、兄弟节点 c 的颜色互换。
• 调整结束。

删除操作

红黑树的插入操作还不是很困难，但删除操作就困难多了。

删除操作的平衡调整分为两步，第一步是针对删除节点初步调整。初步调整只是保证整棵红黑树在一个节点删除之后，仍然满足最后一条定义的要求，也就是说，每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；第二步是针对关注节点进行二次调整，让它满足红黑树的第四条定义， 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）

1. 针对删除节点初步调整

这里需要注意一下，红黑树的定义中“只包含红色节点和黑色节点”，经过初步调整之后，为了保证满足红黑树定义的最后一条要求，有些节点会被标记成两种颜色，“红 - 黑”或者“黑 - 黑”。如果一个节点被标记为了“黑 - 黑”，那在计算黑色节点个数的时候，要算成两个黑色节点。

情况一：如果要删除的节点是 a，它只有一个子节点 b

• 删除节点 a，并且把节点 b 替换到节点 a 的位置，这一部分操作跟普通的二叉查找树的删除操作一样；
• 节点 a 只能是黑色，节点 b 也只能是红色，其他情况均不符合红黑树的定义。这种情况下，我们把节点 b 改为黑色；
• 调整结束，不需要进行二次调整。

情况二：如果要删除的节点 a 有两个非空子节点，并且它的后继节点就是节点 a 的右子节点 c。

• 如果节点 a 的后继节点就是右子节点 c，那右子节点 c 肯定没有左子树。我们把节点 a 删除，并且将节点 c 替换到节点 a 的位置。这一部分操作跟普通的二叉查找树的删除操作无异；
• 然后把节点 c 的颜色设置为跟节点 a 相同的颜色；
• 如果节点 c 是黑色，为了不违反红黑树的最后一条定义，我们给节点 c 的右子节点 d 多加一个黑色，这个时候节点 d 就成了“红 - 黑”或者“黑 - 黑”；
• 这个时候，关注节点变成了节点 d，第二步的调整操作就会针对关注节点来做。

情况三：如果要删除的是节点 a，它有两个非空子节点，并且节点 a 的后继节点不是右子节点

• 找到后继节点 d，并将它删除，删除后继节点 d 的过程参照 CASE 1；
• 将节点 a 替换成后继节点 d；把节点 d 的颜色设置为跟节点 a 相同的颜色；
• 如果节点 d 是黑色，为了不违反红黑树的最后一条定义，我们给节点 d 的右子节点 c 多加一个黑色，这个时候节点 c 就成了“红 - 黑”或者“黑 - 黑”；
• 这个时候，关注节点变成了节点 c，第二步的调整操作就会针对关注节点来做。

2. 针对关注节点进行二次调整

经过初步调整之后，关注节点变成了“红 - 黑”或者“黑 - 黑”节点。针对这个关注节点，我们再分四种情况来进行二次调整。二次调整是为了让红黑树中不存在相邻的红色节点。

情况一：如果关注节点是 a，它的兄弟节点 c 是红色的

• 围绕关注节点 a 的父节点 b 左旋；
• 关注节点 a 的父节点 b 和祖父节点 c 交换颜色；
• 关注节点不变；
• 继续从四种情况中选择适合的规则来调整。

情况二：如果关注节点是 a，它的兄弟节点 c 是黑色的，并且节点 c 的左右子节点 d、e 都是黑色的

• 将关注节点 a 的兄弟节点 c 的颜色变成红色；
• 从关注节点 a 中去掉一个黑色，这个时候节点 a 就是单纯的红色或者黑色；
• 给关注节点 a 的父节点 b 添加一个黑色，这个时候节点 b 就变成了“红 - 黑”或者“黑 - 黑”；
• 关注节点从 a 变成其父节点 b；
• 继续从四种情况中选择符合的规则来调整。

情况三：如果关注节点是 a，它的兄弟节点 c 是黑色，c 的左子节点 d 是红色，c 的右子节点 e 是黑色

• 围绕关注节点 a 的兄弟节点 c 右旋；节点 c 和节点 d 交换颜色；
• 关注节点不变；
• 跳转到情况四，继续调整。

情况四：如果关注节点 a 的兄弟节点 c 是黑色的，并且 c 的右子节点是红色的

• 围绕关注节点 a 的父节点 b 左旋；
• 将关注节点 a 的兄弟节点 c 的颜色，跟关注节点 a 的父节点 b 设置成相同的颜色；
• 将关注节点 a 的父节点 b 的颜色设置为黑色；
• 从关注节点 a 中去掉一个黑色，节点 a 就变成了单纯的红色或者黑色；
• 将关注节点 a 的叔父节点 e 设置为黑色；
• 调整结束。

总结

红黑树的插入和删除操作每一步都伴随着调整操作，目的就是为了让其继续满足红黑树的定义。从而保证整体的性能。