Java 集合 | 红黑树 | 前置知识

一、前言

0tnv1e.png
0tnv1e.png

为啥要学红黑树吖?

因为笔者最近在赶项目的时候,不忘抽出时间来复习 Java 基础知识,现在准备看集合的源码啦啦。听闻,HashMapjdk 1.8 的时候,底层的数据结构发生了变化,变成了数组+链表+红黑树。很好,没了解过红黑树,所以就趁今天闲暇学习一下啦

二、什么是红黑树?

2.1 有啥用处?

红黑树从本质上来说就是一颗二叉查找树,但是在二叉树的基础上增加了着色相关的性质,使得红黑树可以保证相对平衡,从而保证红黑树的增删改查的时间复杂度最坏也能达到 O(log N)

2.2 红黑树的六条性质你知道吗?

  1. 每个节点要么是黑的,要么是红的
  2. 根节点是黑的
  3. 叶节点是黑的
  4. 如果一个节点是红的,他的两个儿子节点都是黑的
  5. 对于任一节点而言,其到叶节点树尾端NIL指针的每一条路径都包含相同数目的黑节点。这其实就是黑高啦!
  6. 新插入的节点必须是红色噢!
0tVeC4.png
0tVeC4.png

2.3 插入操作

首先,先看这个图吧,这就是全部的插入操作后,平衡的方法啦!其实我还是喜欢用笔画 hhh

0tZCJe.png
0tZCJe.png

红黑树的概念理解起来较为复杂,我们以一个简单的示例,看看如何构造一棵红黑树。

现有数组int[] a = {1, 10, 9, 2, 3, 8, 7, 4, 5, 6};我们要将其变为一棵红黑树。

首先插入1,此时树是空的,1就是根结点,根结点是黑色的:

首先插入 1,此时树是空的,1 就是根结点,根结点是黑色的:

img
img

插入 1

然后插入元素 10,此时依然符合规则,结果如下:

img
img

插入 10

当插入元素 9 时,这时是需要调整的第一种情况,结果如下:

img
img

插入 9

红黑树规则 4 中强调不能有两个相邻的红色结点,所以此时我们需要对其进行调整。调整的原则有多个相关因素,这里的情况是,父结点 10 是其祖父结点 1(父结点的父结点)的右孩子,当前结点 9 是其父结点 10 的左孩子,且没有叔叔结点(父结点的兄弟结点),此时需要进行两次旋转,第一次,以父结点 10 右旋:

img
img

右旋

然后将父结点**(此时是 9)**染为黑色,祖父结点 1 染为红色,如下所示:

img
img

染色

然后以祖父结点 1 左旋:

img
img

左旋

下一步,插入元素 2,结果如下:

img
img

插入 2

此时情况与上一步类似,区别在于父结点 1 是祖父结点 9 的左孩子,当前结点 2 是父结点的右孩子,且叔叔结点 10 是红色的。这时需要先将叔叔结点 10 染为黑色,再进行下一步操作,具体做法是将父结点 1 和叔叔结点 10 染为黑色,祖父结点 9 染为红色,如下所示:

img
img

染色

由于结点 9 是根节点,必须为黑色,将它染为黑色即可:

img
img

染色

下一步,插入元素 3,如下所示:

img
img

插入 3

这和我们之前插入元素 10 的情况一模一样,需要将父结点 2 染为黑色,祖父结点 1 染为红色,如下所示:

img
img

染色

然后左旋:

img
img

左旋

下一步,插入元素 8,结果如下:

img
img

插入 8

此时和插入元素 2 有些类似,区别在于父结点 3 是右孩子,当前结点 8 也是右孩子,这时也需要先将叔叔结点 1 染为黑色,具体操作是先将 13 染为黑色,再将祖父结点 2 染为红色,如下所示:

img
img

染色

此时树已经平衡了,不需要再进行其他操作了,现在插入元素 7,如下所示:

img
img

插入 7

这时和之前插入元素 9 时一模一样了,先将 78 右旋,如下所示:

img
img

右旋

然后将 7 染为黑色,3 染为红色,再进行左旋,结果如下:

img
img

左旋

下一步要插入的元素是 4,结果如下:

img
img

插入 4

这里和插入元素 2 是类似的,先将 38 染为黑色,7 染为红色,如下所示:

img
img

染色

但此时 27 相邻且颜色均为红色,我们需要对它们继续进行调整。这时情况变为了父结点 2 为红色,叔叔结点 10 为黑色,且 2 为左孩子,7 为右孩子,这时需要以 2 左旋。这时左旋与之前不同的地方在于结点 7 旋转完成后将有三个孩子,结果类似于下图:

img
img

错误示意图

这种情况处理起来也很简单,只需要把 7 原来的左孩子 3,变成 2 的右孩子即可,结果如下:

img
img

调整

然后再把 2 的父结点 7 染为黑色,祖父结点 9 染为红色。结果如下所示:

img
img

染色

此时又需要右旋了,我们要以 9 右旋,右旋完成后 7 又有三个孩子,这种情况和上述是对称的,我们把 7 原有的右孩子 8,变成 9 的左孩子即可,如下所示:

img
img

右旋

下一个要插入的元素是 5,插入后如下所示:

img
img

插入 5

有了上述一些操作,处理 5 变得十分简单,将 3 染为红色,4 染为黑色,然后左旋,结果如下所示:

img
img

左旋

最后插入元素 6,如下所示:

img
img

插入 6

又是叔叔结点 3 为红色的情况,这种情况我们处理过多次了,首先将 35 染为黑色,4 染为红色,结果如下:

img
img

染色

此时问题向上传递到了元素 4,我们看 2479 的颜色和位置关系,这种情况我们也处理过,先将 29 染为黑色,7 染为红色,结果如下:

img
img

染色

最后 7 是根结点,染为黑色即可,最终结果如下所示:

img
img

2.4 删除操作

删除的规则如下:

0tmMKs.png
0tmMKs.png

要从一棵红黑树中删除一个元素,主要分为三种情况。

情况 1:待删除元素没有孩子

没有孩子指的是没有值不为 NIL 的孩子。这种情况下,如果删除的元素是红色的,可以直接删除,如果删除的元素是黑色的,就需要进行调整了。

例如我们从下图中删除元素 1:

img
img

红黑树

删除元素 1 后,2 的左孩子为 NIL,这条支路上的黑色结点数就比其他支路少了,所以需要进行调整。

这时,我们的关注点从叔叔结点转到兄弟结点,也就是结点 4,此时 4 是红色的,就把它染为黑色,把父结点 2 染为红色,如下所示:

img
img

染色

然后以 2 左旋,结果如下:

img
img

左旋

此时兄弟结点为 3,且它没有红色的孩子,这时只需要把它染为红色,父结点 2 染为黑色即可。结果如下所示:

img
img

调整完毕

情况 2:待删除元素有一个孩子

这应该是删除操作中最简单的一种情况了,根据红黑树的定义,我们可以推测,如果一个元素仅有一个孩子,那么这个元素一定是黑色的,而且其孩子是红色的。

假设我们有一个红色节点,它是树中的某一个节点,且仅有一个孩子,那么根据红色节点不能相邻的条件,它的孩子一定是黑色的,如下所示:

img
img

红色节点仅一个孩子

但这个子树的黑高却不再平衡了(注意每个节点的叶节点都是一个 NIL 节点),因此红色节点不可能只有一个孩子。

而若是一个黑色节点仅有一个孩子,如果其孩子是黑色的,同样会打破黑高的平衡,所以其孩子只能是红色的,如下所示:

img
img

黑色节点仅一个孩子

只有这一种情况符合红黑树的定义,这时要删除这个元素,只需要使用其孩子代替它,仅代替值而不代替颜色即可,上图的情况删除完后变为:

img
img

删除完毕

可以看到,树的黑高并没有发生变化,因此也不需要进行调整。

情况 3:待删除元素有两个孩子

我们在讨论二叉排序树时说过,如果删除一个有两个孩子的元素,可以使用它的前驱或者后继结点代替它。因为它的前驱或者后继结点最多只会有一个孩子,所以这种情况可以转为情况 1 或情况 2 处理。

删除元素最复杂的是情况 1,这主要由其兄弟结点以及兄弟结点的孩子颜色共同决定。这里简要做下总结。

我们以 N 代表当前待删除节点,以 P 代表父结点,以 S 代表兄弟结点,以 SL 代表兄弟结点的左孩子,SR 代表兄弟结点的右孩子,如下所示:

img
img

图样

根据红黑树定义,这种情况下 S 要么有红色的子结点,要么只有 NIL 结点,以下对 S 有黑色结点的情况均表示 NIL

主要有以下几种:

  1. S 是红色,P 一定是黑色,S 也不会有红色的孩子,如下:
img
img

红色兄弟结点

此时把 PS 颜色变换,再左旋,如下:

img
img

左旋

这样变换后,N 支路上的黑色结点并没有增加,所以依然少一个,

  1. P,S 以及 S 的全部孩子都是黑色

无论 S 有几个孩子,或者没有孩子,只要不是红色都是这种情况,此时情况如下:

img
img

全黑色

我们把 S 染为红色,这样一来,NS 两个支路都少了一个黑色结点,所以可以把问题向父结点转移,通过递归解决。染色后如下:

img
img

染色

  1. P 为红(S 一定为黑),S 的孩子都为黑

这种情况最为简单,只需要把 P 和 S 颜色交换即可。这样 N 支路多了一个黑色元素,而 S 支路没有减少,所以达到了平衡。

img
img

交换前

img
img

交换后

  1. P 任意色,S 为黑,N 是 P 的左孩子,S 的右孩子 SR 为红,S 的左孩子任意

如下所示

img
img

任意色

此时将 S 改为 P 的颜色,SRP 改为黑色,然后左旋,结果如下:

img
img

左旋

可以发现,此时 N 支路多了一个黑色结点,而其余支路均没有收到影响,所以调整完毕。

  1. P 任意色,S 为黑,N 是 P 的左孩子,S 的左孩子 SL 为红,S 的右孩子 SR 为黑,如下所示:

    img
    img

    SR 黑色

此时变换 SSL 的颜色,然后右旋,结果如下:

img
img

右旋

这时,所有分支的黑色结点数均没有改变,但情况 5 转为了情况 4,再进行一次操作即可。

还有一些情况与上述是对称的,我们进行相应的转换即可。

红黑树的操作比较复杂,插入元素可能需要多次变色与旋转,删除也是。这些操作的目的都是为了保证红黑树的结构不被破坏。这些复杂的插入与删除操作希望大家可以亲手尝试一下,以加深理解。

三、结语

红黑树其实一开始看起来有点懵逼懵逼的,但是,其实你看完了全文,然后手动模拟一下插入删除操作,发现也不是想象中的很难啦!

附上笔者学习红黑树做的草稿hhh 如果还是看不明白,推荐一个视频:红黑树原理源码讲解(java),全B站讲解最细致版本,看完月薪最少涨5k!

0tnAy9.png
0tnAy9.png
0tn1QH.png
0tn1QH.png

如果文章对您有一点帮助的话,希望您能点一下赞,您的点赞,是我前进的动力

本文参考链接:

本文使用 mdnice 排版