教育改变生活

标题: 图解：什么是红黑树？（二） [打印本页]

作者: 李玮 时间: 2020-11-10 15:12
标题: 图解：什么是红黑树？（二）
再看红黑树

来看它的五条定义：

1.节点颜色有红色和黑色

【2-3树到红黑树的转化已经解释过】

2.根节点必为黑色

【2-3树中如果根节点为2节点，那么它本来就对应红黑树中黑节点；如果根节点为3节点，也可以用黑色节点表示较大的那个元素，然后较小的元素作为左倾红节点存在于红黑树中】

3.所有叶子节点都是黑色

【此处提到的叶子其实是空链接，因篇幅问题不便全部画出】

####4.任意节点到叶子节点经过的黑色节点数目相同

【红黑树中的红节点是和黑色父节点绑定的，在2-3树中本来就是同一层的，只有黑色节点才会在2-3树中真正贡献高度，由于2-3树的任一节点到空链接距离相同，因此反应在红黑树中就是黑色完美平衡】

5.不会有连续的红色节点

【2-3树中本来就规定没有4节点，2-3-4树中虽然有4节点，但是要求在红黑树中体现为一黑色节点带两红色儿子，分布左右，所以也不会有连续红节点】

相信在你的视角中，红黑树已经不再是这五条僵硬的定义了，它背后正浮现着一颗2-3树概念模型。虽然你已经有了这样的认识，但是红黑树作为真正的实现模型，我们还是要回到这个实现本身来探究它的一系列操作。在开始前，我准备了两个基础知识，希望能帮助到你。

1.作为二叉查找树

二叉查找树的节点有一个元素X和两个指针域，左指针指向小于X的元素，右指针指向大于X的元素。

假设我们的插入序列是1~10，那么这颗树会演变成只有右链接的形式，树高会增加到10层，这个时候已经不具备O(LogN)的查找时间复杂度，因为这颗树退化成了链表。

因此对二叉树进行平衡调整是很重要的一个环节，无论是AVL还是红黑树，它们本质上都是希望尽可能保证这颗二叉查找树中的元素尽量均衡的分布在树的两侧。

当我们向一颗二叉查找树中插入一个元素Y的时候，我们会一直与树中的节点进行大小比较，如果Y小于当前元素，就往左走，如果Y大于当前元素，就往右走，直到达到叶子节点，这个时候我们可以把Y插入这颗二叉查找树了。

由于这次的插入动作，整棵树可能会发生一些不平衡，因此我们需要在插入后进行一次平衡调整，使得整棵树恢复到平衡的状态（具体如何调整，要看树是AVL还是红黑树亦或是其他的平衡树）。

二叉查找树的删除是一个很有意思的问题，不同于插入的是，待删除的元素并不能保证一定出现在树中的叶子节点。这将带来一个棘手的情景，即我们需要从树的中间部分取走一个元素，而且在取走后还需要经过调整来使得整颗树满足平衡的性质。从树的中间部分直接取走一个节点的场景实在是太多，也牵扯到了太多相关的节点，这种操作很难实现。

好在有人提出了一个观点，我们对查找树中一个节点的删除，其实可以不必真的改动这个节点的位置。由于查找树的特殊性质，将某个元素节点删除后，它有两个最佳替代者，分别是有序序列中的前驱元素和后继元素。

我们还是以一个包含元素1~10的二叉查找树为例，如果我们希望删除5所在的节点，那么让4或者6替代它的位置都是可行的。作为前驱元素的4，会存放在5所在节点的左子树的最右侧；作为后继元素的6，会存放在5所在节点的右子树的最左侧。

关于这个结论，大家只需稍加思索便可以明白。

现在我们又让问题简化了，也就是说，删除某个节点的时候，我们先找到它的前驱元素或者后继元素（随便选一个），将它的前驱元素直接填到待删除的节点，然后再把它的前驱元素或者后继元素删除。

这个时候问题就转化成了在二叉查找树中删除一个没有左子树的节点（或者是一个没有右子树的节点），我们只需要将这个节点删除再进行对应的平衡调整即可（虽然还是需要调平，但是比直接在树中层删除一个同时具备左右儿子的节点要容易很多）。

注意，此处并没有强调是针对红黑树的操作，因为红黑树和AVL都是二叉查找树，它们都适用这个方法。

介绍一下树的旋转

为了调平一颗二叉树，使得其左右节点数目分布均匀，通常会选择旋转的手段。你可以把一颗二叉树某节点的左右子树想象成天平上待称量的物品，如果哪边重了，我们就从重的那边拿出一部分，加到轻的那边，以此保持相对的平均。

在二叉树中这种调整的操作就是旋转，下面给出了两个示例，希望大家能够仔细探究，旋转是二叉树调平的精髓。

介绍一下树的旋转

理解了这些之后，再去看红黑树的插入删除，就能够理解旋转和染色背后的意义了。我们选择算法4中的左倾红黑树作演示：首先看插入

如图所示，对于左倾红黑树的插入一共有三种可能的情况。

第一种，待插入元素比黑父大，插在了黑父的右边，而黑父左边是红色儿子。这种情况会导致在红黑树中出现右倾红节点。
注意，这种情况对应着2-3树中出现了临时4节点，我们在2-3树中的处理是将这个临时4节点分裂，左右元素各自形成一个2节点，中间元素上升到上层跟父节点结合。所以，我们在红黑树中的动作是，将原本红色的左右儿子染黑（左右分裂），将黑父染红（等待上升结合）。

第二种情况，待插入元素比红父小，且红父自身就是左倾。听起来有点绕，看图就会明白，其实就是说红父和待插入元素同时靠在了左边，形成了连续的红节点。
这种情况我们需要用两步来调整。由于我们插入的是红色节点，其实不会破坏黑色完美平衡，所以要注意的是在旋转和染色的过程种继续保持这种完美黑色平衡。
首先对红父的父亲进行一次右旋，这次右旋不会破坏黑色平衡，但是也没有解决连续红色的问题。
接下来将12所在节点与15所在节点交换颜色，这样的目的是为了消除连续红色，并且这个操作依旧维持了黑色平衡。现在我们已经得到了情况1的场景，直接按情况1处理即可。

第三种情况，待插入元素比红父大，且红父自身就是左倾。
也就是说插入的这个节点形成了一个右倾的红色节点，对右倾的处理很简单，将红父进行一次左旋，就能使得右倾红节点变为左倾，现在出现了连续的左倾红节点，直接按情况2处理即可。

在插入时，可以体会到左倾红黑树对于左倾的限制带来的好处，因为在原树符合红黑树定义的情况下，如果父亲是红的，那么它一定左倾，同时也不用考虑可能存在的右倾兄弟（如果有，那说明原树不满足红黑树定义）。

这种限制消除了很多需要考虑的场景，让插入变得更加简单。

左倾红黑树的删除

左倾红黑树的删除需要借鉴上文中提到的二叉查找树通用的删除策略，当我们要删除某个节点的时候选择它的前驱节点或者后继节点元素来替代它，转而删除它的前驱/后继节点。

在这个例子中，我选择用后继节点来替代被删除节点。

假设我们需要删除的节点它的右子树如图所示，那么对该节点的删除实际上转为了对2的删除。

我们从当前的根节点出发，利于2-3树中预合并的策略逐层对红黑树进行调整。具体的做法是，每次都保证当前的节点是2-3树中的非2节点，如果当前节点已经是非2节点，那么直接跳过；如果当前节点是2节点，那么根据兄弟节点的状况来进行调整：

如果兄弟是2节点，那么从父节点借一个元素给当前节点，然后与兄弟节点一起形成一个临时4节点。
如果兄弟是非2节点，那么兄弟上升一个元素到父节点，同时父节点下降一个元素到当前节点，使得当前节点成为一个3节点。

这样的策略能够保证最后走到待删除节点的时候，它一定是一个非2节点，我们可以直接将其元素删除。

接下来要考虑的是修复工作，由于红黑树定义的限制，我们在调整的过程中出现了一些本不该存在的红色右倾节点（因为生成了概念模型中的临时4节点），于是我们顺着搜索的方向向上回溯，如果遇到当前节点具备右倾的红色儿子，那么对当前节点进行一次左旋，这时原本的右儿子会来到当前节点的位置，然后将右儿子与当前节点交换颜色，我们就将右倾红节点修复成了左倾红节点，同时我们并没有破坏黑色节点的平衡。

右倾转左倾是一个很基本的操作，我们以35，44为例，你既可以将35作为黑节点，44作为右倾红色儿子；也可以将44作为黑节点，35作为左倾红儿子。事实上我们对于右倾的修复就是换了一种树形而已。一路回溯到当前根节点，直至路径中不再包含任何的红色右倾节点，至此修复工作全部完成。

总结

这篇文章的目的旨在从概念模型2-3树出发介绍一颗红黑树的前世今生。希望大家能够跳出枯燥的五条定义，更加本质地认识红黑树中的各种操作来源。

虽然本文只是介绍了相对简单的左倾红黑树，但是如果能够将左倾红黑树认识的很清楚，那么普通红黑树也只是多了一些情况而已。

对于还有精力阅读算法导论的读者，我给出一点自己的经验：

插入阶段与左倾红黑树比较相似
配图中的部分节点标识不太清楚，要反复对照原文阅读
删除阶段，算法导论中将删除黑节点X带来的黑色平衡破坏解释为，给X的子节点添上额外的一层黑色，让X的子节点变为【双重黑】或者【既黑又红】的。
我其实不太接受这种解释，经过考虑，我认为其实这个表达可以更直接一点：既然删除了某个黑色节点，那么必然会破坏以这个黑色节点为路径上的黑色平衡，表现为路径中缺少一个黑。
如果你仔细研究算法导论中的四个删除场景，会发现它们在做的事情其实都是从兄弟节点的路径想办法移动一个黑色节点过来。
因此，如果实在无法理解【双重黑】，【既黑又红】，那么直接按照“某条路径欠黑，所以要想办法补充一个黑色节点”这个思路来思考吧！
还是删除阶段，四个删除场景该如何记忆？我们假设删除的是某个左倾节点，其实决定场景变化的就是三个因素：这个节点的兄弟颜色；兄弟的左右儿子的颜色；这个节点的父节点的颜色。这样子粗略估计有2x2x2x2共16种情况。实际上会少很多，我们从兄弟的颜色入手。请注意如果兄弟是红色，那么当前节点的父亲和兄弟的儿子其实都是黑色。而当兄弟是黑色的时候，我们只需要满足兄弟的右儿子是红色，就能通过一次调整来实现平衡（具体请参照算法导论）。
另外提醒注意的是，一定要想好记忆的顺序。算法导论中的删除调平4种情况中，只有情况4是绝对终态，也就是说到达了这种状态后只需要一次调整绝对能达到平衡。所以我们的出发点一定是从这种状态开始，对于另外几种情况，我们要想的不是怎么去达到最终平衡，而是怎么能让它一步一步转为情况4。这样子你的思路就会清晰很多，记忆的压力也会减小。如果细心的话，你可以回想一下本文是按照怎样的顺序介绍左倾红黑树的插入的，为什么是这样的顺序？
一个数据结构可视化网站，它的红黑树是基于2-3-4树的，跟算法导论中基本一样（除了删除时候对前驱/后继节点的选择），可以用它当做检验。https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

写在最后

最后，如果你被问到红黑树，也许你可以试着反问面试官一个问题：“您应该知道红黑树的五条定义，如果我构造一颗只有黑色节点的红黑树，这样子可行吗？因为这样子没有破坏任何一条红黑树的规则。”

如果他回答可行。

继续问：“那么请问红黑树中要红节点干什么呢？红节点的真实意义是什么呢？”

你们的故事就开始了，而我和你的算法故事也才刚开始。

欢迎光临教育改变生活 (http://bbs.goldoar.com/)