最近学习了二叉搜索树中的红黑树,感觉收获颇丰,在此写一篇文章小结一下学到的知识,顺便手写一下Java代码。
引言
先来讲讲什么是二叉搜索树,二叉搜索树有如下特点:他是以一颗二叉树(最多有两个子结点)来组织的,对于树中的某个节点,其左子树的所有元素均小于该节点,其右子树的元素均大于该节点。我们知道一颗有N个节点的二叉树的高度至少为lgN,然后在树上的操作都与其高度有关,因此限制树的高度就显得非常有必要。当一个二叉搜索树的高度是lgN时,在该树上的插入删除搜索等操作均为O(lgN)的时间复杂度,但当二叉搜索树不小心插入成了链表,高度为N的时候,在树上的操作就变为O(N)了。因此我们有许多种平衡二叉树通过特定的方法来限制树的高度,红黑树就是其中的一种。红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,它在每个节点上增加了一个存储位来表示节点的颜色,可以为红色或黑色。通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束,红黑树确保没有一条路径会比其他路径长出2倍,因此是近似于平衡的。
红黑树的性质
一颗红黑树是满足以下红黑性质的二叉搜索树:
- 每个节点是红色或黑色
- 根是黑色
- 叶节点(null)是黑色的
- 红色的节点的两个子结点均为黑色
- 对于每个节点,从该节点到其所有后代的简单路径上,均包含相同数目的黑色节点(我们把到叶节点的黑色节点数称为黑高)
Java中树的节点类如下:
1 | // 颜色枚举 |
旋转
红黑树的关键操作在于其插入和删除操作,但在讲解这两步关键操作之前,我们得定义一些辅助方法来让我们更好的完成任务,该辅助方法就是树的旋转,示意图如下:
旋转由两种,分别是左旋和右旋,相信上图已经表示的非常明确,这里就不再细说,值得注意的是:在旋转操作中只有指针的改变,其他属性都保持不变。对旋转前后的树使用中序遍历将得到相同的结果。
下面是旋转的Java代码:
1 | /** |
插入
终于来到红黑树的第一个关键步骤了:插入操作。
对与插入操作我们利用如下思想解决:我们先把红黑树看成一个普通的二叉搜索树,对其进行插入操作,插入完成后,我们把新加入的节点染成红色,此时红黑树的红黑性质被破坏,然后再通过特定的方法来维护红黑树的性质。
插入的Java代码如下:
1 | /** |
好,终于来到重点了,红黑树的插入操作前半部分与一般二叉搜索树别无二致,区别在于最后把新加入的节点染成红色和恢复红黑树性质的部分。我们先来思考一下往红黑树插入一个红节点会破坏红黑树的什么性质?首先性质1、3、5是不会受影响的,那么当我们插入的节点是红黑树的根结点时会影响性质2,根节点变成了红色,此时我们把根节点染成黑色即可。当我们插入节点的父节点是红色时会影响性质4,红色节点有一个为红色的子结点。对于以上这些影响我们分为3种情况来处理:
关键词:叔节点
下面我们假设插入的节点为z(红色),其父节点为x(红色,为祖父节点的左节点,右节点情况镜像处理即可),其叔节点为y(未知),祖父节点为w(黑色)
情况1:插入节点z的叔节点y为红色
此时的情况如图所示(下图省略了部分不关键的子树):
此时的处理方法很简单,我们只需把祖父节点的黑色“扒”下来放到父节点X和叔节点Y即可,此时对于节点Z就保持了红黑树的性质4,然而进行了此操作后我们还需要对祖父节点W进行继续遍历,因为此时祖父节点有可能违反了红黑树的性质。当我们遍历的祖父节点为根结点时,把根结点变为黑色即可。
情况2:插入节点z的叔节点y是黑色的,且z是一个右孩子
情况3:插入节点z的叔节点y是黑色的,且z是一个左孩子
这两种情况可以放一起讨论,因为我们会把情况2转化为情况3,示意图如下:
左上角为情况2,此时叔节点w为黑色,且插入节点z为父节点x的右孩子,此时我们对父节点x进行一次左旋,然后交换x和z的引用,即可转换为右上角的情况3.
右上角为情况3,此时叔节点w为黑色,且插入节点z为父节点x的左孩子,此时我们进行如下操作即可恢复红黑树的性质:
- 交换父节点x和祖父节点w的颜色
- 对祖父节点w进行右旋
上面的操作既修正了对性质4的违反,也没有引起对其他红黑树性质的违反,因此我们此时可以结束对红黑树的性质修复工作。
下面给出红黑树插入时性质修复的Java代码:
1 | /** |
删除
讲完插入,我们来讲讲删除操作。与插入类似,再删除前我们先把红黑树当成是一颗普通的二叉搜索树来处理删除节点的操作。但在把节点删除过后,由于删除节点会带走一种颜色,因此我们需要记录下被删除的颜色和删除颜色的位置,最后我们再考虑如何修复树的红黑性质。二叉搜索树删除节点分为三种情况,这里简单提一下:
- 删除节点没有子节点:直接把删除节点的位置置空即可
- 删除节点有一个子节点:用该子节点顶替删除节点的位置
- 删除节点有两个子节点:这是比较复杂的情况,此时我们要从删除节点的两边子树中寻找一个节点来顶替其位置,我们可以找右子树的最小节点或左子树的最大节点,本文给出的代码为寻找右子树的最小节点。同时在代码中我们把删除节点的颜色赋给顶替节点,从而使实际删除颜色的节点为顶替节点。
Java代码如下:
1 | /** |
接下来我们来考虑一下一上的删除操作会影响红黑树的什么性质。
首先,如果删除的节点颜色为红色,则不会影响任何红黑性质。但如果删除的颜色是黑色,则可能影响性质2(根节点是黑色的),也可能影响性质4(红色的节点的两个子结点均为黑色),也可能影响性质5(对于每个节点,从该节点到其所有后代的简单路径上,均包含相同数目的黑色节点)。那么当删除的节点颜色为黑色时,对于如何修复删除后的红黑性质,我们采用以下思考方式:
我们假设修复位置的节点具有两种颜色,该节点原来的颜色,以及我们被删除的黑色。那么:
- 如果该节点原来为红色,那么我们被删除的黑色可以直接覆盖其颜色不影响任何红黑性质
- 如果该节点是黑色同时他也是根节点,那么我们可以简单的“消除”掉节点上面的一层黑色
- 如果该节点是黑色,但不是根节点,我们只能通过旋转和重新着色的方法转换修复的位置或退出循环
以下把修复删除红黑性质的工作分为4中情况,此处假设修复位置节点为A(黑色,此处假设为父节点的左节点,右节点请镜像处理),其父节点为B,兄弟节点为C,兄弟节点的左子节点为D,兄弟节点的右子节点为E。
关键词:兄弟节点
情况1:A的兄弟节点为红色
如上图所示,此时我们先交换父节点B和兄弟节点C的颜色,然后对父节点B进行左旋,以上操作并不会影响红黑树性质,而我们也把情况1转化为了别的情况。
情况2:A的兄弟节点为黑色,其子节点均为黑色(下图灰色代表未知颜色)
此时的处理方法很简单,因为A节点和其兄弟节点C均为黑色,且C的子节点也均为黑色,因此我们可以把A节点和C节点的黑色上移到父节点B上,再把修复位置换为父节点B,针对父节点B继续进行修复。(如果父节点B是红色或根节点就可以停止修复了~)
情况3:A的兄弟节点为黑色,兄弟节点的左子节点为红色,右子节点为黑色
此时我们首先交换兄弟节点C与其左子红色节点D的颜色,然后对兄弟节点C进行右旋,把情况3转化为情况4继续处理。
情况4:A的兄弟节点为黑色,兄弟节点的右子节点为红色
此时我们进行如下变换操作:
- 把父节点B和兄弟节点的右子节点E染成黑色,兄弟节点C染成父节点颜色
- 对父节点B进行左旋
以上操作在没有破坏红黑树性质的情况下,消除了节点A的一重黑色,因此至此修复过程可以结束了。
删除时修复过程的Java代码如下:
1 | /** |
打印与测试函数
这里给出本人用来测试和打印红黑树的Java函数:
1 | public static void main(String[] args) { |
ps:没写不知道,一写吓一跳,用Java来实现红黑树还是有挺多麻烦点的:
- 在Java中不知道如何修改根引用,所以最后都在函数上补了返回值
- 刚开始没考虑null叶节点其实是算黑色节点的情况,后来补充了一个静态变量作为叶节点
- 用静态变量当叶节点使得叶节点是共享的,不能修改叶节点的left,right,p指针,因此又再删除时添加了fixParent变量
- 删除时拥有两个子树,但右子树没有左节点的情况是个坑……
总而言之,红黑树的5个性质,3种插入情况,4种删除情况记住就大概没什么问题了~