红黑树

与数组相比,链表提升了插入元素的效率。因为数组在插入元素时,需要移动后续元素的位置;而链表只需要改变后继元素的 prev 属性。然而在查询元素时,链表需要遍历所有元素,并不高效。借助于红黑树,既能提升查询的效率,又能保证插入的效率。

为什么说红黑树有助于提升查询和插入的效率呢?因为红黑树本质上是一棵完美平衡的二叉查找树,可以通过节点的有序性保证查找和插入操作的便捷,其作时间复杂度就是树的高度 O(lgN),自然比链表的 O(N) 高效很多。红黑树有如下两个特征:有序性、平衡性。我们讲一棵红黑树是有序的,通常指的是树中的节点会遵照 key 键自小到大或自大到小的顺序。有序性是实现二叉树完美平衡的先决条件。完美平衡指的是树从根节点到每个底部节点的高度大致相当,这样才能保证查询操作的时间复杂度为 O(lgN)。设想当二叉树出现了单边有值的极端情况时,其查询效率就和链表一样同为 O(N)。因此,实际上是完美平衡的二叉树便于查询节点,而红黑树是完美平衡二叉树的一种实现方式。

犹如红黑树是完美平衡树的一种实现方式,红黑树自身也有多种实现方式。本文所介绍的红黑树(即算法红宝书中的红黑树)是基于 2-3 树实现的。在插入元素方面,2-3 树所具有的优点为:当向 2- 节点插入新节点时,通过将 2- 节点转变成 3- 节点,可以迅速接纳新的节点;当向 3- 节点插入新节点时,通过将 3- 节点转变成 4- 节点,再将 4- 节点转变成 3 个 2- 节点构成的子树,也可以迅速接纳新的节点。在实现上,若使用不同的数据类型表示 2- 节点或 3- 节点及其附属信息,接着实现不同类型节点的转换,这样势必会使程序相当复杂,且容易遇上性能问题。红黑树就应运而生了。

红宝书中的红黑树有如下性质:

  • 红链接均为左链接
  • 没有任何一个节点同时和两条红链接相连
  • 该树是完美黑色平衡的,即任意空链接到根节点的路径上的黑链接数量相同

第一条性质指的是红黑树中构成 3- 节点的方式总是唯一的。当红链接为右链接时,需要通过左旋操作将其转变为标准的左链接 3- 节点。第二条性质包含以下两种情况:父子节点不能同时为红链接(无论子节点是左链接还是右链接);父节点下的两个子节点不能同时为红链接。当父子节点同时为红链接时,可通过旋转操作将其转变为 3 个 2- 节点的子树,这样就能同时消除父子节点的红链接。当父节点下的两个子节点同时为红链接时,可通过颜色转换操作将两个子节点变为黑链接。从 2-3 树的角度直观地看第二条性质,也是指红黑树中的每一个节点不能同时从属于两个 3- 节点。因此,第二条性质和第三条性质一样,表明红黑树是和 2-3 树一一对应的。

需要说明的是:2- 节点是包含 2 个子节点的节点,在红黑树中就是普通节点;3- 节点由两个节点构成,其下包含 3 个子节点,在红黑树中就是左子节点为红链接;4- 节点由三个节点构成,其下包含 4 个子节点,在红黑树中就是左右两侧子节点均为红链接。当分析红黑树的直观视图时,我们只需要考虑 2- 节点和 3- 节点。在插入和删除元素时,我们才需要考虑 4- 节点。红黑树的直观视图就是二叉树。特别的,当将 3- 节点拉平后,红黑树的直观视图就会变成 2-3 树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private static final boolean RED = true;
private static final boolean BLACK = false;

private class Node {
Key key;
Value value;
Node left, right;// 左右子树
int N;// 节点总数
boolean color;// 标识红链接或黑链接

Node(Key key, Value value, int N, boolean color){
this.key = key;
this.value = value;
this.N = N;
this.color = color;
}
}

private boolean isRed(Node x){
if (x == null) return false;
return x.color == RED;
}

在分析红黑树时,我们需要致力于解决如下这样一个命题:怎样在插入和删除节点时保证树的平衡性?

左旋、右旋、颜色转换

红黑树抽象了三种抽象操作:左旋转、右旋转和颜色转换。这三种抽象操作都是局部变换。简单地说,左旋转用于将红链接从右链接转变成左链接,即红链接均为左链接的标准红黑树;右旋转用于将父节点和左子节点均为红链接的子树转变成 3 个 2- 节点的子树;颜色转换将两个子节点同时为红链接的子树转变成 3 个 2- 节点的子树,同时子树的根节点转变为红链接,颜色转换操作可以向上递归,以实现整颗红黑树中不能有两个子节点同时为红链接。

左旋

1
2
3
4
5
6
7
8
9
10
Node rotateLeft(Node h){
Node x = h.right;// 取出原红链接节点 x
h.right = x.left;// 将中间部分 x.left 置于左节点 h 下
x.left = h;// 因 x 将作为子树的根节点,将左节点 h 置为红链接节点 x 的左子节点
x.color = h.color;// 不改变子树根节点的颜色
h.color = RED;// 将子树中的红链接节点置为 h,即左移
x.N = h.N;// 调整节点数目
h.N = 1 + size(h.left) + size(h.right);
return x;// 返回子树的根节点
}

上文已指出,左旋的目的就是将作为右链接的红链接转变为标准的左链接。

右旋

1
2
3
4
5
6
7
8
9
10
Node rotateRight(Node h){
Node x = h.left;// 取出原红链接节点 x
h.left = x.right;// 将中间部分 x.left 置于右节点 h 下
x.right = h;// 因 x 将作为子树的根节点,右节点 h 置为红链接节点 x 的右子节点
x.color = h.color;// 不改变子树根节点的颜色
h.color = RED;// 将子树中的红链接节点置为 h,即右移
x.N = h.N;// 调整节点数目
h.N = 1 + size(h.left) + size(h.right);
return x;// 返回子树的根节点
}

右旋的目的需要结合使用场景,即当在父节点和左子节点同时为红链接时,通过右旋和颜色转换可以将子树转变为包含 3 个 2- 节点的子树。试想一下,当父节点和左侧子节点都为红链接时,即上图中 less than E 子树的根节点也是红链接,右旋操作就可以使旋转后的根节点 E 与其两侧子节点构成 4- 节点(即两侧子节点同时为红链接)。这时再通过颜色转换就可以把这两个子节点均置为黑链接,以避免单个节点同时和两条红链接相连。图示参见节点插入部分。

颜色转换

1
2
3
4
5
void flipColors(Node h){
h.color = RED;// 根节点置为红链接
h.left.color = BLACK;// 左右子节点置为黑链接
h.right.color = BLACK;
}

上文已经指出,在父节点和左侧子节点同时为红链接的情形下,通过右旋操作可以使祖父节点拥有两个红链接子节点,再通过颜色转换可以将这两个节点都转换成黑链接。因为左旋、右旋和颜色转换都基于红链接,将子树的根节点置为红链接有助于向上递归调整树的平衡性(即使得左旋、右旋、颜色转换操作能作用于自根节点始的整棵树)。

节点插入

节点插入需要针对以下情况:

  • 当插入对象为 2- 节点时,向左插入就是在根节点左侧直接添加一个红链接,使父子节点构成一个 3- 节点;向右插入就是在根节点右侧先添加一个红链接,然后通过左旋反转父子节点的位置。
  • 当插入对象为 3- 节点时,向左插入就使得父子节点同时为红链接,因此就需要通过右旋和颜色转换将其转变为包含 3 个 2- 节点的子树;中间插入就使得父子节点既同时是红链接,子节点又是非法的右链接,因此先需通过左旋将子树变更为向左插入一样的形态,然后再沿用向左插入的调整策略;向右插入可以通过颜色转换将两个子节点变为黑链接。完成以上操作后,向上递归调整自根节点始的整棵树。

插入算法的实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
private Node root;

public void put(Key key, Value val){
root = put(root, key, val);
root.color = BLACK;// 根节点始终为黑链接
}

private Node put(Node h, Key key, Value val){
if (h == null) return new Node(key, val, 1, RED);// 创建根节点或底部节点

// 向下递归插入节点
int cmp = key.CompareTo(h.key);
if (cmp < 0) h.left = put(h.left, key, val);
else if (cmp > 0) h.right = put(h.right, key, val);
else h.val = val;

// 向上递归调整树的平衡性
// [左旋],[右旋,颜色转换]是连贯一体的操作,可能有,也可能没有

// 红链接为右链接,左旋,针对 2- 节点或 3-节点中插入情况
// 可能会引起向上递归执行左旋操作
if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
// 父子节点均为红链接,右旋
if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
// 两侧子节点均为红链接,颜色转换
if (isRed(h.left) && isRed(h.right)) h = flipColors(h);

// 调整节点数目
h.Number = Size(h.left) + Size(h.right) + 1;
return h;// 返回根节点,便于向上递归
}

节点删除

可想而知,当待删除的节点在 3- 节点中,如果 3- 节点在底部,那么这个节点就可以直接删除;如果 3- 节点不在底部,就可以用该节点的前驱或后继节点替换这个节点,然后再删除这个节点。当删除的节点在 2- 节点中,删除操作将破坏树的平衡性,这时就需要从父节点或兄弟节点中借一个节点构成 3- 节点或 4- 节点,然后再执行删除操作。在删除节点的过程中,程序会自顶向下构建 3- 节点或 4- 节点;删除结点后,再自底向上拆解 4- 节点。

需要指出的是,上文中左旋、右旋操作所具有的一般性为:即便子节点不是红链接,左旋、右旋在反转父子节点时,还能创建红链接。因此,构建 3- 节点需要借助于左旋、右旋操作;构建 4- 节点借助于反向颜色转换操作。

反向颜色转换

反向颜色转换是上文 flipColors 方法的反向操作,即将左右子节点均置为红链接,这会使得单侧父子节点构成一个 3- 节点(可视为将父节点借给子节点),同时父节点和两侧子节点又会构成一个 4- 节点。

1
2
3
4
5
void moveFlipColors(Node h){
h.color = Black;
h.left.color = Red;
h.right.color = Red;
}

左移

左移操作适用于子树中的最小键,即左侧节点。对比上文,左移操作包含如下两个步骤:

  1. 通过反向颜色转换 moveFlipColors 操作构建 4- 节点。
  2. 若右侧为 3- 节点,将 3- 节点中的最小键左移到左节点下,使左节点变为 3- 节点。这时需要通过颜色转换 flipColors 拿掉 4- 节点。
1
2
3
4
5
6
7
8
9
private Node moveRedLeft(Node h){
moveFlipColors(h);// 从父节点中借一个
if (isRed(h.right.left)){// 兄弟节点不是 2- 节点,从兄弟节点中借一个
h.right = rotateRight(h.right);
h = rotateLeft(h);
flipColors(h);// 从兄弟节点借了一个后,把从父节点中借来的还回去
}
return h;
}

右移

右移操作适用于子树中的最大键,即右侧节点。同样包含两个步骤:

  1. 通过反向颜色转换 moveFlipColors 操作构建 4- 节点。
  2. 若左侧为 2- 节点,将该 2- 节点的父节点右移,使右节点变为 3- 节点。这时需要通过颜色转换 flipColors 拿掉 4- 节点。
1
2
3
4
5
6
7
8
private Node moveRedRight(Node h){
moveFlipColors(h);// 从父节点中借一个
if (!isRed(h.left.left)){// 兄弟节点是 2- 节点,从兄弟节点中借一个
h = rotateRight(h);
flipColors(h);// 从兄弟节点借了一个后,把从父节点中借来的还回去
}
return h;
}

再平衡

无论在删除左侧节点还是在删除右侧节点时,都可能会在右侧创建新的红链接,所以我们需要通过左旋操作移除该红链接。且删除操作会破坏红黑树的性质,使红黑树下拥有不合法的作为右链接的红链接,或者父节点和左子节点同时为红链接,或者两侧子节点同时为红链接,这时就需要借助节点插入时的左旋、右旋、颜色转换操作逐级向上调整了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private Node balance(Node h){
// 删除左节点可能会创建 4- 节点,右链接为红链接
// 删除右节点可能会使用左旋创建居于右侧的红链接
// 两种情况均通过 rotateLeft 还原
if (isRed(h.right)) h = rotateLeft(h);

// 和节点插入时相同,通过[左旋]、[右旋,颜色转换]调整树的平衡性
if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
if (isRed(h.left) && isRed(h.right)) flipColors(h);

h.N = size(h.left) + size(h.right) + 1;
return h;
}

删除最小键

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void deleteMin(){
// 当 flipColors, moveFlipColors 由同一个函数实现时,需要将根节点置红,以便进行反向颜色转换
if(!isRed(root.left) && !isRed(root.right)){
root.color = Red;
}
root = deleteMin(root);
if ( !isEmpty() ) root.color = Black;// 根节点颜色复原
}

private Node deleteMin(Node h){
// h 就是为最小键,置为 null 移除
if(h.left == null) return null;

// 向下递归构建 3- 节点和 4- 节点,并删除节点

// 左子节点为 2- 节点,通过左移操作向右子节点或父节点中借一个
if(!isRed(h.left) && !isRed(h.left.left))
h = moveRedLeft(h);
h.left = deleteMin(h.left);

// 向上递归移除临时的 4- 节点,调整树的平衡性
return balance(h);
}

删除最大键

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public void deleteMax(){
if(!isRed(root.left) && isRed(root.right)){
root.color = Red;
}
root = deleteMax(root);
if ( !isEmpty() ) root.color = Black;
}

private Node deleteMax(Node h){
// 左子节点为红链接时,通过右旋将其给到右侧,以构建 3- 节点
if(isRed(h.left)){
h = rotateRight(h);
}

// h 就是为最大键,置为 null 移除
if(h.right == null){
return null;
}

// 向下递归构建 3- 节点和 4- 节点,并删除节点

// 右子节点为 2- 节点,通过右移操作向左子节点或父节点中借一个
if(!isRed(h.right) && !isRed(h.right.left)){
h = moveRedRight(h);
}
h.right = deleteMax(h.right);

// 向上递归移除临时的 4- 节点,调整树的平衡性
return balance(h);
}

删除节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public void delete(Key key){
if(!isRed(root.left)&& !isRed(root.right)){
root.color = Red;
}
root = delete(root, key);
if ( !isEmpty() ) root.color = Black;
}

private Node delete(Node h, Key key){
if (key.compareTo(h.key) < 0){
// 向下递归构建 3- 节点和 4- 节点,并删除节点

// 左子节点为 2- 节点,通过左移操作向右子节点或父节点中借一个
if (!isRed(h.left) && !isRed(h.left.left))
h = moveRedLeft(h);

// 递归删除
h.left = delete(h.left, key);
} else {
// 左子节点为红链接时,通过右旋将其给到右侧,以构建 3- 节点
if (isRed(h.left))
h = rotateRight(h);

// 无后继节点,意味待删除节点为底部节点,置为 null 删除
// 怎么保证 h 是 3- 节点?
if (key.compareTo(h.key) == 0 && (h.right == null))
return null;

// 向下递归构建 3- 节点和 4- 节点,并删除节点

// 右子节点为 2- 节点,通过右移操作向左子节点或父节点中借一个
if (!isRed(h.right) && !isRed(h.right.left))
h = moveRedRight(h);

// 使用后继节点替换
if (key.compareTo(h.key) == 0){
h.val = get(h.right, min(h.right).key);
h.key = min(h.right).key;
h.right = deleteMin(h.right);
}

// 递归删除
else h.right = delete(h.right, key);
}

return balance(h);
}

小记

这篇文章是我在理解 HashMap 过程中的一阵整理。回头想想,仍觉得自己对红黑树的理解不是很透彻。留在网上暂作为一种记录,以便于渐进式修改。

参考

浅谈算法和数据结构: 九 平衡查找树之红黑树
一篇文章搞懂红黑树的原理及实现