这篇文章算是我写博客写公众号以来画图最多的一篇文章了,没有之一,我希望尽可能多地用图片来形象地描述红黑树的各种操作的前后变换原理,帮助大家来理解红黑树的工作原理,下面,多图预警开始了。 在讲红黑树之前,我们首先来了解下下面几个概念:二叉树,排序二叉树以及平衡二叉树。 二叉树二叉树指的是每个节点最多只能有两个字数的有序树。通常左边的子树称为 二叉树简单的示意图如下: 代码定义: class Node { 排序二叉树所谓排序二叉树,顾名思义,排序二叉树是有顺序的,它是一种特殊结构的二叉树,我们可以对树中所有节点进行排序和检索。
排序二叉树简单示意图: 排序二叉树退化成链表排序二叉树的左子树上所有节点的值小于根节点的值,右子树上所有节点的值大于根节点的值,当我们插入一组元素正好是有序的时候,这时会让排序二叉树退化成链表。 正常情况下,排序二叉树是如下图这样的: 但是,当插入的一组元素正好是有序的时候,排序二叉树就变成了下边这样了,就变成了普通的链表结构,如下图所示: 正常情况下的排序二叉树检索效率类似于二分查找,二分查找的时间复杂度为 O(log n),但是如果排序二叉树退化成链表结构,那么检索效率就变成了线性的 O(n) 的,这样相对于 O(log n) 来说,检索效率肯定是要差不少的。
关于 O(log n) 的分析下面这篇文章讲解的非常好,感兴趣的可以看下这篇文章 二分查找的时间复杂度,文章是拿二分查找来举例的,二分查找和平衡二叉树的时间复杂度是一样的,理解了二分查找的时间复杂度,再来理解平衡二叉树就不难了,这里就不赘述了。 继续回到我们的主题上,为了解决排序二叉树在特殊情况下会退化成链表的问题(链表的检索效率是 O(n) 相对正常二叉树来说要差不少),所以有人发明了 平衡二叉树平衡二叉数又被称为 AVL 树,AVL 树的名字来源于它的发明作者 G.M. Adelson-Velsky 和 E.M. Landis,取自两人名字的首字母。 官方定义:它或者是一颗空树,或者具有以下性质的排序二叉树:它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1,且它的左子树和右子树都是一颗平衡二叉树。 两个条件:
红黑树讲了这么多概念,接下来主角红黑树终于要上场了。
其实红黑树和上面的平衡二叉树类似,本质上都是为了解决排序二叉树在极端情况下退化成链表导致检索效率大大降低的问题,红黑树最早是由 Rudolf Bayer 于 1972 年发明的。 红黑树首先肯定是一个排序二叉树,它在每个节点上增加了一个存储位来表示节点的颜色,可以是 RED 或 BLACK 。 Java 中实现红黑树大概结构图如下所示: 红黑树的特性
针对上面的 5 种性质,我们简单理解下,对于性质 1 和性质 2 ,相当于是对红黑树每个节点的约束,根节点是黑色,其他的节点要么是红色,要么是黑色。 对于性质 3 中指定红黑树的每个叶子节点都是空节点,而且叶子节点都是黑色,但 Java 实现的红黑树会使用 null 来代表空节点,因此我们在遍历 Java里的红黑树的时候会看不到叶子节点,而看到的是每个叶子节点都是红色的,这一点需要注意。 对于性质 5,这里我们需要注意的是,这里的描述是从任一节点,从任一节点到它的子树的每个叶子节点黑色节点的数量都是相同的,这个数量被称为这个节点的黑高。 如果我们从根节点出发到每个叶子节点的路径都包含相同数量的黑色节点,这个黑色节点的数量被称为树的黑色高度。树的黑色高度和节点的黑色高度是不一样的,这里要注意区分。 其实到这里有人可能会问了,红黑树的性质说了一大堆,那是不是说只要保证红黑树的节点是红黑交替就能保证树是平衡的呢? 其实不是这样的,我们可以看来看下面这张图: 左边的子树都是黑色节点,但是这个红黑树依然是平衡的,5 条性质它都满足。 这个树的黑色高度为 3,从根节点到叶子节点的最短路径长度是 2,该路径上全是黑色节点,包括叶子节点,从根节点到叶子节点最长路径为 4,每个黑色节点之间会插入红色节点。 通过上面的性质 4 和性质 5,其实上保证了没有任何一条路径会比其他路径长出两倍,所以这样的红黑树是平衡的。 其实这算是一个推论,红黑树在最差情况下,最长的路径都不会比最短的路径长出两倍。其实红黑树并不是真正的平衡二叉树,它只能保证大致是平衡的,因为红黑树的高度不会无限增高,在实际应用用,红黑树的统计性能要高于平衡二叉树,但极端性能略差。 红黑树的插入想要彻底理解红黑树,除了上面说到的理解红黑树的性质以外,就是理解红黑树的插入操作了。 红黑树的插入和普通排序二叉树的插入基本一致,排序二叉树的要求是左子树上的所有节点都要比根节点小,右子树上的所有节点都要比跟节点大,当插入一个新的节点的时候,首先要找到当前要插入的节点适合放在排序二叉树哪个位置,然后插入当前节点即可。红黑树和排序二叉树不同的是,红黑树需要在插入节点调整树的结构来让树保持平衡。 一般情况下,红黑树中新插入的节点都是红色的,那么,为什么说新加入到红黑树中的节点要是红色的呢? 这个问题可以这样理解,我们从性质5中知道,当前红黑树中从根节点到每个叶子节点的黑色节点数量是一样的,此时假如新的黑色节点的话,必然破坏规则,但加入红色节点却不一定,除非其父节点就是红色节点,因此加入红色节点,破坏规则的可能性小一些。 接下来我们重点来讲红黑树插入新节点后是如何保持平衡的。 给定下面这样一颗红黑树: 当我们插入值为66的节点的时候,示意图如下: 很明显,这个时候结构依然遵循着上述5大特性,无需启动自动平衡机制调整节点平衡状态。 如果再向里面插入值为51的节点呢,这个时候红黑树变成了这样。 这样的结构实际上是不满足性质4的,红色两个子节点必须是黑色的,而这里49这个红色节点现在有个51的红色节点与其相连。 这个时候我们需要调整这个树的结构来保证红黑树的平衡。 首先尝试将49这个节点设置为黑色,如下示意图。 这个时候我们发现黑高是不对的,其中 60-56-45-49-51-null 这条路径有 4 个黑节点,其他路径的黑色节点是 3 个。 接着调整红黑树,我们再次尝试把45这个节点设置为红色的,如下图所示: 这个时候我们发现问题又来了,56-45-43 都是红色节点的,出现了红色节点相连的问题。 于是我们需要再把 56 和 43 设置为黑色的,如下图所示。 于是我们把 68 这个红色节点设置为黑色的。 对于这种红黑树插入节点的情况下,我们可以只需要通过变色就可以保持树的平衡了。但是并不是每次都是这么幸运的,当变色行不通的时候,我们需要考虑另一个手段就是旋转了。 例如下面这种情况,同样还是拿这颗红黑树举例。 现在这颗红黑树,我们现在插入节点65。 我们尝试把 66 这个节点设置为黑色,如下图所示。 这样操作之后黑高又出现不一致的情况了,60-68-64-null 有 3 个黑色节点,而60-68-64-66-null 这条路径有 4 个黑色节点,这样的结构是不平衡的。 或者我们把 68 设置为黑色,把 64 设置为红色,如下图所示: 但是,同样的问题,上面这颗红黑树的黑色高度还是不一致,60-68-64-null 和 60-68-64-66-null 这两条路径黑色高度还是不一致。 这种情况如果只通过变色的情况是不能保持红黑树的平衡的。 红黑树的旋转接下来我们讲讲红黑树的旋转,旋转分为左旋和右旋。 左旋文字描述:逆时针旋转两个节点,让一个节点被其右子节点取代,而该节点成为右子节点的左子节点。 文字描述太抽象,接下来看下图片展示。 首先断开节点PL与右子节点G的关系,同时将其右子节点的引用指向节点C2;然后断开节点G与左子节点C2的关系,同时将G的左子节点的应用指向节点PL。 接下来再放下 gif 图,希望能帮助大家更好地理解左旋,图片来自网络。 右旋文字描述:顺时针旋转两个节点,让一个节点被其左子节点取代,而该节点成为左子节点的右子节点。 右旋的图片展示: 首先断开节点G与左子节点PL的关系,同时将其左子节点的引用指向节点C2;然后断开节点PL与右子节点C2的关系,同时将PL的右子节点的应用指向节点G。 右旋的gif展示(图片来自网络): 介绍完了左旋和右旋基本操作,我们来详细介绍下红黑树的几种旋转场景。 左左节点旋转(插入节点的父节点是左节点,插入节点也是左节点)如下图所示的红黑树,我们插入节点是65。 操作步骤如下可以围绕祖父节点 69 右旋,再结合变色,步骤如下所示: 左右节点旋转(插入节点的父节点是左节点,插入节点是右节点)还是上面这颗红黑树,我们再插入节点 67。 这种情况我们可以这样操作,先围绕父节点 66 左旋,然后再围绕祖父节点 69 右旋,最后再将 67 设置为黑色,把 69 设置为红色,如下图所示。 右左节点旋转(插入节点的父节点是右节点,插入节点左节点)如下图这种情况,我们要插入节点68。 这种情况,我们可以先围绕父节点 69 右旋,接着再围绕祖父节点 66 左旋,最后把 68 节点设置为黑色,把 66 设置为红色,我们的具体操作步骤如下所示。 右右节点旋转(插入节点的父节点是右节点,插入节点也是右节点)还是来上面的图来举例,我们在这颗红黑树上插入节点 70 。 我们可以这样操作围绕祖父节点 66 左旋,再把旋转后的根节点 69 设置为黑色,把 66 这个节点设置为红色。具体可以参看下图: 红黑树在 Java 中的实现Java 中的红黑树实现类是 TreeMap ,接下来我们尝试从源码角度来逐行解释 TreeMap 这一套机制是如何运作的。 // TreeMap中使用Entry来描述每个节点 TreeMap 的put方法。 public V put(K key, V value) { //插入节点后修复红黑树 TreeMap的插入节点和普通的排序二叉树没啥区别,唯一不同的是,在TreeMap 插入节点后会调用方法fixAfterInsertion(e)来重新调整红黑树的结构来让红黑树保持平衡。 我们重点关注下红黑树的fixAfterInsertion(e)方法,接下来我们来分别介绍两种场景来演示fixAfterInsertion(e)方法的执行流程。 第一种场景:只需变色即可平衡同样是拿这颗红黑树举例,现在我们插入节点 51。 当我们需要插入节点51的时候,这个时候TreeMap 的 put 方法执行后会得到下面这张图。 接着调用fixAfterInsertion(e)方法,如下代码流程所示。 当第一次进入循环后,执行后会得到下面的红黑树结构。 在把 x 重新赋值后,重新进入 while 循环,此时的 x 节点为 45 。 执行上述流程后,得到下面所示的红黑树结构。 这个时候x被重新赋值为60,因为60是根节点,所以会退出 while 循环。在退出循序后,会再次把根节点设置为黑色,得到最终的结构如下图所示。 最后经过两次执行while循环后,我们的红黑树会调整成现在这样的结构,这样的红黑树结构是平衡的,所以路径的黑高一致,并且没有红色节点相连的情况。 第二种场景 旋转搭配变色来保持平衡接下来我们再来演示第二种场景,需要结合变色和旋转一起来保持平衡。 给定下面这样一颗红黑树: 现在我们插入节点66,得到如下树结构。 同样地,我们进入fixAfterInsertion(e)方法。 最终我们得到的红黑树结构如下图所示: 调整成这样的结构我们的红黑树又再次保持平衡了。 演示 TreeMap 的流程就拿这两种场景举例了,其他的就不一一举例了。 红黑树的删除因为之前的分享只整理了红黑树的插入部分,本来想着红黑树的删除就不整理了,有人跟我反馈说红黑树的删除相对更复杂,于是索性还是把红黑树的删除再整理下。 删除相对插入来说,的确是要复杂一点,但是复杂的地方是因为在删除节点的这个操作情况有很多种,但是插入不一样,插入节点的时候实际上这个节点的位置是确定的,在节点插入成功后只需要调整红黑树的平衡就可以了。 但是删除不一样的是,删除节点的时候我们不能简单地把这个节点设置为null,因为如果这个节点有子节点的情况下,不能简单地把当前删除的节点设置为null,这个被删除的节点的位置需要有新的节点来填补。这样一来,需要分多种情况来处理了。 删除节点是根节点直接删除根节点即可。 删掉节点的左子节点和右子节点都是为空直接删除当前节点即可。 删除节点有一个子节点不为空这个时候需要使用子节点来代替当前需要删除的节点,然后再把子节点删除即可。 给定下面这棵树,当我们需要删除节点69的时候。 首先用子节点代替当前待删除节点,然后再把子节点删除。 最终的红黑树结构如下面所示,这个结构的红黑树我们是不需要通过变色+旋转来保持红黑树的平衡了,因为将子节点删除后树已经是平衡的了。 还有一种场景是当我们待删除节点是黑色的,黑色的节点被删除后,树的黑高就会出现不一致的情况,这个时候就需要重新调整结构。 还是拿上面这颗删除节点后的红黑树举例,我们现在需要删除节点67。 因为67 这个节点的两个子节点都是null,所以直接删除,得到如下图所示结构: 这个时候我们树的黑高是不一致的,左边黑高是3,右边是2,所以我们需要把64节点设置为红色来保持平衡。 删除节点两个子节点都不为空删除节点两个子节点都不为空的情况下,跟上面有一个节点不为空的情况下也是有点类似,同样是需要找能替代当前节点的节点,找到后,把能替代删除节点值复制过来,然后再把替代节点删除掉。
那么什么叫做前驱,什么叫做后继呢? 前驱或者后继都是最接近当前节点的节点,当我们需要删除当前节点的时候,也就是找到能替代当前节点的节点,能够替代当前节点肯定是最接近当前节点。 在当前删除节点两个子节点不为空的场景下,我们需要再进行细分,主要分为以下三种情况。 第一种,前驱节点为黑色节点,同时有一个非空节点如下面这样一棵树,我们需要删除节点64: 首先找到前驱节点,把前驱节点复制到当前节点: 接着删除前驱节点。 这个时候63和60这个节点都是红色的,我们尝试把60这个节点设置为红色即可使整个红黑树达到平衡。 第二种,前驱节点为黑色节点,同时子节点都为空前驱节点是黑色的,子节点都为空,这个时候操作步骤与上面基本类似。 如下操作步骤: 因为要删除节点64,接着找到前驱节点63,把63节点复制到当前位置,然后将前驱节点63删除掉,变色后出现黑高不一致的情况下,最后把63节点设置为黑色,把65节点设置为红色,这样就能保证红黑树的平衡。 第三种,前驱节点为红色节点,同时子节点都为空给定下面这颗红黑树,我们需要删除节点64的时候。 同样地,我们找到64的前驱节点63,接着把63赋值到64这个位置。 然后删除前驱节点。 删除节点后不需要变色也不需要旋转即可保持树的平衡。 作者:JasonGaoH |
|