1. 概述
在jdk1.8中,HashMap和ConcurrentHashMap中都采用了红黑树这一数据结构。即当链表达到一定的长度后,就把链表转化成红黑树。这其中主要利用了红黑树的良好性质,不管你节点怎样,他始终保持查找时间复杂度为O(logn)。这样的性质相对于链表在长度很长的时候有很大的优势。O(logn)<O(lgn)
2. 红黑树的定义
- 每个结点要么是红的,要么是黑的。
- 根结点是黑的。
- 每个叶结点(叶结点即指树尾端NIL指针或NULL结点)是黑的。
- 如果一个结点是红的,那么它的俩个儿子都是黑的。
-
对于任一结点而言,其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。
一棵典型的红黑树如下:
红黑树
3. 红黑树的插入
在这里,默认你熟悉二叉查找树的结构,以及他的插入和删除操作。红黑树本质上是一棵二叉查找树。
对红黑树的插入,我们先按二叉查找树去插入,然后对对树做调整,使其满足红黑树的五条定义。(这是因为你插入会破坏其中的规则)
二叉查找树的插入伪代码如下:
RB-INSERT(T, z)
1 y ← nil[T]
2 x ← root[T]
3 while x ≠ nil[T]
4 do y ← x
5 if key[z] < key[x]
6 then x ← left[x]
7 else x ← right[x]
8 p[z] ← y
9 if y = nil[T]
10 then root[T] ← z
11 else if key[z] < key[y]
12 then left[y] ← z
13 else right[y] ← z
14 left[z] ← nil[T]
15 right[z] ← nil[T]
16 color[z] ← RED
17 RB-INSERT-FIXUP(T, z)
可以看出,RB-INSERT(T, z)前面的第1-13行代码基本就是二叉查找树的插入代码,然后第14-16行代码把z的左孩子、右孩子都赋为叶结点nil,再把z结点着为红色,最后为保证红黑性质在插入操作后依然保持,调用一个辅助程序RB-INSERT-FIXUP来对结点进行重新着色,并旋转。
换言之
- 如果插入的是根结点,因为原树是空树,此情况只会违反性质2,所以直接把此结点涂为黑色。
- 如果插入的结点的父结点是黑色,由于此不会违反性质2和性质4,红黑树没有被破坏,所以此时也是什么也不做。
但当遇到下述3种情况时:
- 插入修复情况1:如果当前结点的父结点是红色且祖父结点的另一个子结点(叔叔结点)是红色
- 插入修复情况2:当前结点的父结点是红色,叔叔结点是黑色,当前结点是其父结点的右子
- 插入修复情况3:当前结点的父结点是红色,叔叔结点是黑色,当前结点是其父结点的左子
3.1 插入修复情况1:当前结点的父结点是红色且祖父结点的另一个子结点(叔叔结点)是红色。
插入的伪代码如下:
1 while color[p[z]] = RED
2 do if p[z] = left[p[p[z]]]
3 then y ← right[p[p[z]]]
4 if color[y] = RED
5 then color[p[z]] ← BLACK ▹ Case 1
6 color[y] ← BLACK ▹ Case 1
7 color[p[p[z]]] ← RED ▹ Case 1
8 z ← p[p[z]] ▹ Case 1
如下面两个调整前的图和调整之后的图做对比。其中4为新添加的点。它的父节点为红色,叔叔节点为红色。那么调整就是把4的叔叔节点变为黑色(8节点),4的祖父节点变为红色,把当前结点指向祖父结点,从新的当前结点重新开始算法(7节点变为N)。
3.1.1 调整前的树
3.1.2 调整后的红黑树
3.2 插入修复情况2:当前结点的父结点是红色,叔叔结点是黑色,当前结点是其父结点的右子
9 else if z = right[p[z]]
10 then z ← p[z] ▹ Case 2
11 LEFT-ROTATE(T, z) ▹ Case 2
调整之前的图如3.1.2,经过调整后得到如下的图。过程是当前结点的父结点做为新的当前结点,以新当前结点为支点左旋.
3.2.2 调整之后的树
3.3 插入修复情况3:当前结点的父结点是红色,叔叔结点是黑色,当前结点是其父结点的左子
12 color[p[z]] ← BLACK ▹ Case 3
13 color[p[p[z]]] ← RED ▹ Case 3
14 RIGHT-ROTATE(T, p[p[z]]) ▹ Case 3
调整过程是把父结点变为黑色,祖父结点变为红色,在祖父结点为支点右旋。最后,把根结点涂为黑色,整棵红黑树便重新恢复了平衡。调整之前的图如3.2.2,经过调整后得到下图。
3.3.2调整后的图
3. 红黑树的删除
在这里默认你熟悉二叉查找树的删除操作。
下面我们用一个分析技巧:我们从被删结点后来顶替它的那个结点开始调整,并认为它有额外的一重黑色。这里额外一重黑色是什么意思呢,我们不是把红黑树的结点加上除红与黑的另一种颜色,这里只是一种假设,我们认为我们当前指向它,因此空有额外一种黑色,可以认为它的黑色是从它的父结点被删除后继承给它的,它现在可以容纳两种颜色,如果它原来是红色,那么现在是红+黑,如果原来是黑色,那么它现在的颜色是黑+黑。有了这重额外的黑色,原红黑树性质5就能保持不变。现在只要恢复其它性质就可以了,做法还是尽量向根移动和穷举所有可能性。"--saturnman。
如果是以下情况,恢复比较简单:
- 当前结点是红+黑色
解法,直接把当前结点染成黑色,结束此时红黑树性质全部恢复。 - 当前结点是黑+黑且是根结点, 解法:什么都不做,结束。
下面4中特殊情况
- 删除修复情况1:当前结点是黑+黑且兄弟结点为红色(此时父结点和兄弟结点的子结点分为黑)
- 删除修复情况2:当前结点是黑加黑且兄弟是黑色且兄弟结点的两个子结点全为黑色
- 删除修复情况3:当前结点颜色是黑+黑,兄弟结点是黑色,兄弟的左子是红色,右子是黑色
- 删除修复情况4:当前结点颜色是黑-黑色,它的兄弟结点是黑色,但是兄弟结点的右子是红色,兄弟结点左子的颜色任意
4.1 删除修复情况1:当前结点是黑+黑且兄弟结点为红色(此时父结点和兄弟结点的子结点分为黑)。
解法:把父结点染成红色,把兄弟结点染成黑色,之后重新进入算法(我们只讨论当前结点是其父结点左孩子时的情况)。此变换后原红黑树性质5不变,而把问题转化为兄弟结点为黑色的情况(注:变化前,原本就未违反性质5,只是为了把问题转化为兄弟结点为黑色的情况)。
变化后
4.2 删除修复情况2:当前结点是黑加黑且兄弟是黑色且兄弟结点的两个子结点全为黑色。
解法:把当前结点和兄弟结点中抽取一重黑色追加到父结点上,把父结点当成新的当前结点,重新进入算法。(此变换后性质5不变)。伪代码如下。
//调用RB-DELETE-FIXUP(T, x) 的9-11行代码
9 if color[left[w]] = BLACK and color[right[w]] = BLACK
10 then color[w] ← RED ▹ Case 2
11 x p[x] ▹ Case 2
4.3 删除修复情况3:当前结点颜色是黑+黑,兄弟结点是黑色,兄弟的左子是红色,右子是黑色。
解法:把兄弟结点染红,兄弟左子结点染黑,之后再在兄弟结点为支点解右旋,之后重新进入算法。此是把当前的情况转化为情况4,而性质5得以保持。伪代码如下
//调用RB-DELETE-FIXUP(T, x) 的第12-16行代码
12 else if color[right[w]] = BLACK
13 then color[left[w]] ← BLACK ▹ Case 3
14 color[w] ← RED ▹ Case 3
15 RIGHT-ROTATE(T, w) ▹ Case 3
16 w ← right[p[x]] ▹ Case 3
4.4 删除修复情况4:当前结点颜色是黑-黑色,它的兄弟结点是黑色,但是兄弟结点的右子是红色,兄弟结点左子的颜色任意。
解法:把兄弟结点染成当前结点父结点的颜色,把当前结点父结点染成黑色,兄弟结点右子染成黑色,之后以当前结点的父结点为支点进行左旋,此时算法结束,红黑树所有性质调整正确。代码如下
//调用RB-DELETE-FIXUP(T, x) 的第17-21行代码
17 color[w] ← color[p[x]] ▹ Case 4
18 color[p[x]] ← BLACK ▹ Case 4
19 color[right[w]] ← BLACK ▹ Case 4
20 LEFT-ROTATE(T, p[x]) ▹ Case 4
21 x ← root[T] ▹ Case 4
以上就是红黑树的结构和性质,对于面试和源码的理解很有帮助。
参考文章:
教你透彻了解红黑树
网友评论