[转]红黑树回顾

原文链接:http://liuliqiang.info/post/red-black-tree/
在我学习数据结构和算法一段时间之后,就被灌输了二分查找的性能非常好的观念,确实,这也没什么毛病,毕竟 O(logn) 的复杂度确实已经很好了。那么,习惯得,我也将二叉树认为是查找元素的不二选择,好像这在通常情况下问题也不大。

但是,当理论遇到现实的时候,事情就变得有点糟糕了,例如二叉树的理想状态应该是平衡二叉树,也就是说对于每一个分支,左右子树的高度差最多就是一个,这样可以保证查找一个元素的时间复杂度是 O(logn)。事实上,这很难做到,我是说在不修正的情况下,要想让一棵二叉树随时保持平衡,那么我们就需要在增加或删除元素的时候做平衡处理,而这处理的代价经常都会是 O(logn)。

为了在尽可能保持二叉树的优点的同时,又尽可能解决缺点,有很多类似的树型结构被发现,其中有 2-3树/AVL 树/红黑树/B树/B+树等等,每种都有其独特并且优异的地方,而在这篇文章中,我就以红黑树为例,温习一下红黑树的知识。

红黑树与AVL树的比较:
AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多;
红黑是用非严格的平衡来换取增删节点时候旋转次数的降低;
所以简单说,如果你的应用中,搜索的次数远远大于插入和删除,那么选择AVL,如果搜索,插入删除次数几乎差不多,应该选择RB。
红黑树的特点
一棵二叉查找树如果满足以下的红黑性质,那么这就是一棵红黑树:

每个节点要么是红的,要么是黑的
根节点是黑的
每个叶节点(NULL)是黑的
如果一个节点是红的,那么它的两个儿子都是黑的
对于每个节点,从该节点到其子孙节点的所有路径上包含相同数目的黑节点
对第 4 个点稍作解释,其实可以说成是没有父子节点都是红的情况,但是,却可以存在父子节点都是黑的情况。

对于一棵红黑树来说,那么它一定满足这些性质,那么只有两种情况会破坏这些性质,那就是插入 和 删除,所以我们需要做一些特别的操作来使 红黑树 能够继续满足条件。

插入节点
往一棵红黑树中插入一个节点时,我们要遵循一些规则:

插入的节点最开始一定是设置成红的
插入的节点的位置一开始一定是叶子节点的位置
只有当父节点的颜色也是红的时候,我们才需要考虑调整
这就是一棵简单的红黑树:

这里将元素4 插入到原来的红黑树中,所以,这里也就破坏红黑性质了,这也是唯一一种需要转换的情况,那就是父子节点都是红的。对于父子节点都是红的,我们需要考虑两种情况:

新的节点在父节点的左树
新的节点在父节点的右树
但是,处理这个问题,有时候很简单得完成,那就是第三种情况:

父节点的兄弟节点也是红的
这个时候我们归纳一下,插入一个新元素的时候,红黑特性被破坏,我们有三种情况需要处理:

父节点的兄弟节点也是红的
新的节点在父节点的左子树
新的节点在父节点的右子树
下面我们就对这三种情况一一解决。

父节点的兄弟节点也是红的
对于这种情况,我们上面的示例就恰恰是这样的:

这个时候因为 5 和 8 都是红的,所以我们可以这么操作:

将 5 和 8 变为黑,然后将 7 变成红
即可,这样我们就让新插入的节点不会破坏 红黑性质 了,因为对于节点 7 来说,我们可以保证它到子节点中的黑节点个数不变,这样的话,整棵树的黑节点路径原则也不会被破坏。

变换之后就是:

但是,可以发现,父节点被变换颜色之后又和它的父节点产生了冲突,这个时候就不能通过变换兄弟节点的颜色来解决了。但是,我们可以发现,现在 2 和 7 的情况就是我们的另外一种情况:新的节点在父节点的右子树

新的节点在父节点的右子树
对于父节点的兄弟不是红色的,并且新的节点在父节点的左树的情况:

这就是刚才解决新插入节点之后的新情况,对节点 7 和节点 2 产生了冲突,这个时候我们需要解决。这里需要引入一个新的概念叫做旋转,旋转包含左旋和右旋,其实他们是对称操作:

所以这里需要利用 左旋 的操作,根据上图的指引,我们进行以节点 2 为根进行 左旋 后的结果是:

这个时候又遇到情况了,那就是节点 2 和节点 7 又冲突了并且就是最后一种情况:新的节点在父节点的左子树

新的节点在父节点的左子树
当遇到这种情况的时候,我们就要进行 右旋 操作,右旋操作有个前提就是

将父节点设置为 Black
将父节点的父节点设置为 Red
右旋 父节点的父节点
右旋 之后的结果应该是:

这个时候可以发现这棵二叉查找树 已经满足了所有的 红黑性质,也就是说这又是一棵红黑树,也就是将插入操作调整完毕了。

插入小结
可以看到,这个简单的操作就涉及到了 3 种类型,其实过程中可能不止做一种类型的转换,还会涉及到 2 种或者 3 种类型的转换。

父节点的兄弟节点也是红的
将父节点和兄弟节点都改成黑的
将父节点的父节点改成红的
新的节点在父节点的右子树
左旋
新的节点在父节点的右子树
将父节点设置为 Black
将父节点的父节点设置为 Red
右旋父节点的父节点
删除节点
红黑树中的删除和普通二叉查找树的删除差不多,也就多了一项红黑节点调整。所以假设我们先不考虑红黑调整,那么删除一个节点就是:

这就是一个普通的删除二叉查找树的步骤,其中 tree_successor 就是搜索下一个用来替换当前节点的值,这里需要说明的是这个被用来替换的值肯定是叶子节点,或者说只有右子树的节点,没有其他情况。然后我们所谓的删除就是将两个值调换,将替换的值删掉。

现在是时候考虑一下红黑平衡了,考虑一下,什么时候需要红黑平衡?根据这里的代码,我们可以发现真正被删除的是 y,所以,有两种情况需要考虑:

y 是红色的,那么删除红色节点之后,并不会影响后续节点路径中黑色节点的个数,也不会导致两个红色节点成为父子节点,那么也就是说是安全的,无需红黑平衡了。
y 是黑色的,那么这个时候被删除了,和 y 有关的路径就少了一个黑色节点,那么我们可以考虑将这个黑色节点下移,转给 y 的儿子 x,也就是说 x 必须承担一个黑色。
这个时候又需要考虑两种情况了,对于 x 来说,也有两种可能,那就是:

x 是红色的,那么我们直接将 x 转变为黑色,那么整个路径上黑色节点的个数也平衡了,而且也不会有两个红色成为父子节点,就成功了。
x 是黑色的,那么显然不能再提供一个黑色,那么只能继续迁移,需要记住,此时 x 承担了 2 个黑色的责任,需要找人承担一个
对于 x 需要承担 2 个黑色的情况,我们有几种情况要考虑:

x 的兄弟 w 是红色的

那么对于这种情况,我们可以考虑进行一个左旋,然后再改变一下兄弟节点的颜色:

这里考虑将 节点D 进行一个左旋,那么旋转之后的结果就是:

我们将 B/D 的颜色进行一个转换,然后我们需要注意的是 x 对应的节点也还必须承担多一个黑色,然而这个 x 已经是黑色了,所以还得转接,但是,很明显,兄弟节点不是红色了,不能旋转了,那我们就需要考虑另外一种情况了。

x 的兄弟 w 是黑色的,而且 w 的两个孩子都是黑色的

因为 x 不能承担多一个黑色,所以我们考虑 w 的情况,首先考虑 w 有两个孩子,并且两个孩子都是黑色的,那么就是这样子的:

rb-case2-01.png

对于这种情况,我们可以将 节点D 的颜色变为红色,这样的话可以发现左右都差一个黑色,那么我们就将这差的一个黑色让 父节点c 承担,虽然图示中 父节点c 的颜色是红色的,但是事实上红黑都有可能:

如果是红色,那么直接变成黑色就大功告成了
如果是黑色,那么就需要多贡献一个黑色,如果不能贡献,那只能继续根据各种情况递归下去

所以变换之后应该是这样的:

rb-case2-02.png

x 的兄弟 w 是黑色的,而且 w 的左子节点是红色,右子节点是黑色

这种情况我们可以用图示来表示:

rb-case3-01.png

对于这种情况,我们不能一次性迁移 节点x 的状态,那只能退而求其次,找出一个中间状态,构建这个中间状态:

rb-case3-02.png

这里讲 节点C 的位置提升为父节点,然后将原来的 父节点D 将为 节点C 的子节点,并且改变为红色,然后我们再讨论这种情况。

x 的兄弟 w 是黑色的,并且 w 的右子节点是红色

这里我们可以发现我们只关注 节点w 的右子节点,并且为红色即可,不需要关注左子节点,这个时候我们可以这样表示这个图:

rb-case4-01.png

这时,我们可以将 节点D 左旋,然后就得到了这种情况:

rb-case4-02.png

这里有几点地方需要指出来:

原来 节点w 的右节点E 变成了 Black
原来 节点D 的颜色变成了 节点B 的颜色
父节点B 的颜色一定变成 Black

这时,我们再看这张图,会发现 x 不见了,也就是说没有任何节点需要多提供一个黑色,也就是说我们这棵红黑树平衡了。

以上就是我们需要考虑的删除一个节点之后红黑不平衡的问题了,其实核心要点就是记住 变量x 就是表示这个节点需要多提供一个黑色,所以当 x 是 Root 或者是红色的时候,那么我们就成功了,因为:

如果 root 需要提供多一个黑色,那么其实完全就不用多提供了,因为 root 无父节点需要平衡。
如果是红色节点需要提供多一个黑色,那么尽管把它变成黑色好了,因为把它变成黑色不会影响我们的红黑特性,最可能影响到的一条特性就是任何路径上的黑色节点数一样,但是因为包含这个节点的路径都少了一个,所以尽管变成黑色就可以了。
小结
红黑树的目的就是尽可能保持二叉搜索树的平衡,保证二叉搜索树的搜索速度,同时又要提高插入元素的速度,所以红黑树要设立红黑特性,保证在这两方面之间得到权衡。和 AVL 树相比:

如果你的插入和搜索频率差不多,那么就用 红黑树
如果插入远远少于查询,那么用 AVL树 划算
Reference
算法导论
教你透彻了解红黑树
二叉树可视化工具

发表评论

邮箱地址不会被公开。 必填项已用*标注


*