二叉树算法 - 红黑树的动态平衡实现原理分析

Wednesday. May 08, 2019 - 2 mins

PHP 数据结构与算法二叉树算法

数据结构与算法系列（三十六）

插入节点

红黑树规定，插入的节点必须是红色的。而且，二叉排序（查找）树中新插入的节点都是放在叶子节点上。首先，我们来看两种最简单的情况：

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

除此之外，其他情况都会违背红黑树的特性，所以我们需要进行动态调整，与平衡二叉树不同，调整的过程除了左右旋转之外，还涉及到节点颜色的调整。

新节点插入之后，如果红黑树的平衡被打破，那一般会有下面三种情况。我们只需要根据每种情况的特点，不停地调整，就可以让红黑树继续符合定义，也就是继续保持平衡。

有了前面平衡二叉树的铺垫，相信理解起来红黑树的构建过程将会更加轻松。为了方便表述，我们把正在处理的节点叫关注节点。

CASE 1：如果关注节点是 a（待插入节点），它的叔叔节点（父亲的兄弟节点，从二叉排序树的角度来说叫伯伯节点更合适？） d 是红色，我们就依次执行下面的操作：

将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色；
将关注节点 a 的祖父节点 c 的颜色设置成红色；
关注节点变成 a 的祖父节点 c；
跳到下面的 CASE 2 或者 CASE 3 继续处理。

CASE 2：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的右子节点，我们就依次执行下面的操作：

关注节点变成节点 a 的父节点 b；
围绕新的关注节点 b 左旋；
跳到 CASE 3。

CASE 3：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的左子节点，我们就依次执行下面的操作：

围绕关注节点 a 的祖父节点 c 右旋；
将关注节点 a 的父节点 b、兄弟节点 c 的颜色互换。
调整结束，至此就构造出来一棵红黑树。

注：在看上面三个 CASE 的时候要动态的去看，从 CASE 1 跳到 CASE 2 或 CASE 3，或者从 CASE 2 跳到 CASE 3，或者从 CASE 3 开始，不要分割开来。如果从 CASE 1 跳到到 CASE 2 或 CASE 3，后两者的关注节点 a 就是 CASE 1 中最终的关注节点 c。

删除节点

删除节点的平衡调整更加复杂，可以分为两步，第一步是针对删除节点初步调整。初步调整只是保证整棵红黑树在一个节点删除之后，仍然满足最后一条定义的要求，也就是说，每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；第二步是针对关注节点进行二次调整，让它满足红黑树的第三条定义，即不存在相邻的两个红色节点。

1、针对删除节点的初步调整

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

CASE 1：如果要删除的节点是 a，它只有一个子节点 b，那我们就依次进行下面的操作：

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

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

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