红黑树详解

1.相关博客


2.2-3 树

①定义

  • 虽然它不是一种二叉树,但是它满足二分搜索树的基本性质。每次操作节点时,都按照二分搜索树的策略查找它的位置。

Alt text
Alt text

  • 它有两种节点,一种节点可以存放一个元素(与普通的二分搜索树的节点一样,有左右两个孩子,左孩子的值小于该节点的值,右孩子的值大于该节点的值),另一种节点可以存放两个元素(有三个孩子,三个孩子分别在第一个元素的左侧、两个元素的中间和第二个元素的右侧。且这个节点左孩子的值小于左侧元素的值,中间孩子的值在两个元素之间,右孩子的值大于右侧元素的值),所以存放两个元素的节点也满足二分搜索树的基本性质。
  • 2-3 树的每个节点有 2 个或者 3 个孩子,通常将存放一个元素且有两个孩子的节点叫做 2 节点,将存放两个元素且有三个孩子的节点叫做 3 节点。

Alt text

  • 下图为一颗 2-3 树:

Alt text

②性质—绝对平衡性

  • 2-3 树是一颗绝对平衡的树(与 2-3 树本身插入元素时的构建方法相关)
    • 绝对平衡:从根节点到任意一个叶子节点所经过的节点数量一定是相同的(即对于任意一个节点来说,左右子树的高度一定是相同的,可以将 2-3 树类比为满二叉树)
  • 2-3 树如何维持绝对的平衡:添加节点将永远不会添加到一个空的位置,只会和最后找到的叶子节点做融合,若最后找到的叶子节点是 2 节点,则添加进 2 节点,形成一个 3 节点,否则添加进 3 节点,暂时形成一个 4 节点,然后对 4 节点做一个变形处理,形成由三个 2 节点组成的子树。

Alt text
Alt text

  • 若暂时形成的 4 节点是根节点,则变形处理即可。
  • 若暂时形成的 4 节点是叶子节点,则在变形处理后,将子树的根节点继续向其父亲节点(即变形处理前 4 节点的父亲节点,简称 A)融合。如果 A 为 2 节点,则融合后 A 变成一个 3 节点,子树中剩下的两个节点变为 A 的左孩子和中孩子(或者中孩子和右孩子)。如果 A 为 3 节点,则暂时形成一个 4 节点,然后对 4 节点做一个变形处理,再形成由三个 2 节点组成的子树,将子树的根节点继续向其父亲节点融合……直到融合到根节点或者 2 节点。

Alt text
Alt text

③模拟添加节点的过程

  • 下面我们通过向 2-3 树中添加节点,来看看 2-3 树是如何维持绝对平衡的。
  • 添加第一个节点:作为根节点,形成一个 2 节点。

Alt text

  • 添加第二个节点:和最后找到的叶子节点(42)做融合,形成一个 3 节点。

Alt text

  • 添加第三个节点:和最后找到的叶子节点(37 | 42)做融合,暂时形成一个 4 节点,然后将 4 节点变形成由三个 2 节点组成的平衡的树。

Alt text
Alt text

  • 添加第四个节点:和最后找到的叶子节点(12)做融合,形成一个 3 节点。

Alt text

  • 添加第五个节点:和最后找到的叶子节点(12 | 18)做融合,暂时形成一个 4 节点,然后将 4 节点变形成由三个 2 节点组成的子树,将子树的根节点(12)继续向上融合,融合后形成一个 3 节点。

Alt text
Alt text
Alt text

  • 添加第六个节点:和最后找到的叶子节点(6)做融合,形成一个 3 节点。

Alt text

  • 添加第七个节点:和最后找到的叶子节点(6 | 11)做融合,暂时形成一个 4 节点,然后将 4 节点变形成由三个 2 节点组成的子树,将子树的根节点(6)继续向上融合,融合后又形成一个 4 节点,继续将 4 节点变形成由三个 2 节点组成的子树,此时已经融合到根节点,表示添加成功。

Alt text
Alt text
Alt text
Alt text

④红黑树和 2-3 树的等价性

  • 红黑树本质上与 2-3 树是等价的
    • 2-3 树是包含两种节点(2 节点和 3 节点)的树结构,而红黑树是包含一种节点(每个节点只能存储一个元素)的树结构。虽然红黑树与 2-3 树的数据结构不同,但是它们实现了相同的逻辑。
  • 红黑树是一种自平衡的二分搜索树,在红黑树中,对每一个节点都附着了一个颜色 — 红色或者黑色。
    • 黑色节点:普通节点,表示在原来的 2-3 树中的 2 节点。
    • 红色节点:和其父亲节点(黑色节点)一起表示在原来的 2-3 树中的 3 节点
    • 左倾红黑树:所有的红色节点都是向左倾斜的。左倾红节点来表示 2-3 树中的 3 节点(2-3 树的 3 节点的左边元素在红黑树中通过红色节点(简称 A)表示,3 节点的右边元素在红黑树中通过黑色节点(简称 B)表示,并且 A 是 B 的左孩子,表示 A 与 B 在原来的 2-3 树中是并列关系,一起存放在一个 3 节点中)。
    • 右倾红黑树:所有的红色节点都是向右倾斜的。右倾红节点来表示 2-3 树中的 3 节点(2-3 树的 3 节点的左边元素在红黑树中通过黑色节点(简称 A)表示,3 节点的右边元素在红黑树中通过红色节点(简称 B)表示,并且 B 是 A 的右孩子,表示 A 与 B 在原来的 2-3 树中是并列关系,一起存放在一个 3 节点中)。

Alt text
Alt text

ps:左倾红黑树是红黑树相对标准的一种实现方式,但并不是唯一的实现方式,这篇博客的后续内容都以左倾红黑树为例进行分析。

  • 与 2-3 树等价的红黑树:2-3 树中有三个 3 节点 —> 红黑树中有三个红色节点,每一个 3 节点产生一个红色节点。
  • 对于任何一颗 2-3 树,我们都可以使用以上规则将之转化成一颗红黑树。

Alt text
Alt text


3.红黑树

①概念

  • 红黑树(Red Black Tree)是一种自平衡的二分搜索树,它在每个结点上增加一个存储位来表示结点的颜色,可以是 Red 或 Black。红黑树通过对任意一条从根到叶子的路径上的各个结点着色方式的限制,确保没有一条路径会比其他路径长出两倍,因而是接近平衡的。
  • 下图为一颗红黑树:

Alt text

②基本性质

  • 红黑树必须满足如下条件:
  • ①(定义)每个节点或者是红色的,或者是黑色的。
  • ②根节点是黑色的
    • 在 2-3 树中,根节点或者是 2 节点,或者是 3 节点,而 2 节点和 3 节点在与之等价的红黑树(左倾红黑树)中表示为下图的两种情况。
    • 由下图可见, 2-3 树中的 2 节点和 3 节点对应到与之等价的红黑树中,根节点都是黑色的。

Alt text

  • ③(定义)每一个叶子节点(这里的叶子节点指的是最后的空节点)是黑色的
    • 相当于定义空节点本身是黑色的, 一颗空树本身也是一颗红黑树,它的根节点和叶子节点都是空节点(空节点是黑色节点),同时满足 ②、③ 条性质。
  • ④如果一个节点是红色的,那么它的孩子节点都是黑色的。
    • 在红黑树中,只有表示原来的 2-3 树中的 3 节点时,才会出现红色节点。此时红色节点的两个孩子节点是原来的 2-3 树中 3 节点的左孩子和中间的孩子,不管两个孩子是 2 节点还是 3 节点,其对应到红黑树中,根结点都是黑色的(具体见 性质②)。
    • 黑色节点的右孩子一定是黑色的节点(对于左倾红黑树来说,这是我们的定义),它的左孩子可能是红色的节点,也可能是黑色的节点。如果是红色的,表示这两个节点是原来的 2-3 树中的一个 3 节点。如果是黑色的,表示这两个节点是原来的 2-3 树中的两个节点。
  • ⑤(核心)从任意一个节点到其每个叶子节点(空节点),经过的黑色节点数量是一样的。
    • 2-3 树是一颗绝对平衡的树,从 2-3 树的任意一个节点出发到其每个叶子节点,经过的节点数量是一样的。
    • 因为 2-3 树的 2 节点或 3 节点转换成红黑树中的节点表示时,都会有一个黑色的节点,所以从红黑树的任意一个节点出发,每经过一个黑色节点,等于一定经过了原来的 2-3 树中的某个节点。
    • 红黑树是保持 “黑平衡” 的二叉树(黑平衡是指从根节点到任意一个叶子节点,经过的黑色节点数量是一样的)。从严格意义上讲,红黑树不是平衡二叉树,平衡二叉树的定义为左右子树的高度差不能超过 1,红黑树并不符合。

③数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class RBTree {

private static final boolean RED = true;
private static final boolean BLACK = false;

private class TreeNode {
public int key;
public int value;
public TreeNode left;
public TreeNode right;
public boolean color;

TreeNode(int key, int value) {
this.key = key;
this.value = value;
this.left = null;
this.right = null;
// 默认的节点颜色为红色
this.color = RED;
}
}
}
  • 为什么默认的节点颜色为红色?
    • 在 2-3 树中添加一个节点,永远是和最后找到的叶子节点做融合,融合后或者形成一个 3 节点,或者形成一个临时的 4 节点。在红黑树中,红色节点代表它和它的父亲节点(黑色节点)在原来的 2-3 树中是在一起的,等价于 2-3 树中的一个 3 节点。所以在红黑树中,总是将新添加的节点的颜色设置为红色,等价于在 2-3 树中永远将新节点融合进已有的节点中。
    • 在红黑树中添加红色节点后,可能会破坏红黑树的基本性质,此时需要再做一些调整工作(具体见下文)。

④保持根节点为黑色

红黑树中添加新元素之保持根节点为黑色

  • 添加根节点:添加第一个红色节点,作为红黑树的根节点。由红黑树的基本性质②(根节点是黑色的)可知,需要将根节点变成黑色。
    • 结论:若插入的红色节点是红黑树的根结点,应该将红色节点变为黑色节点。

Alt text
Alt text

  • 添加普通节点:在原来的 2-3 树中添加元素 4 时,元素 4 应该添加到元素 2 和元素 5 组成的 3 节点中,形成一个临时的 4 节点(2 | 4 | 5)。然后将临时的 4 节点变形成由三个 2 节点组成的子树,让子树的根节点(即节点 4) 向上融合(与元素 6 和元素 8 所在的 3 节点进行融合),再形成一个临时的 4 节点(4 | 6 | 8),然后再将它变形成由三个 2 节点组成的子树,此时这颗子树的根节点是整棵 2-3 树的根节点,不再向上融合。由于元素 4 和元素 6 在原来的 2-3 树中是向上融合的,所以在与之等价的红黑树中,它们所在的节点是红色的。由于节点 6 是最后的根节点,所以在与之等价的红黑树中,元素 6 所在的节点是黑色的。
    • 结论:对于临时的 4 节点,在 2-3 树的添加过程中每次都要向上融合一个元素,这个元素所在的节点在红黑树的表示中应该是红色的节点。直到它融合到了根节点,再也不能向上走时,变为黑色的节点。

Alt text

  • 代码实践:保持根节点为黑色
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* 功能描述: 向红黑树中添加新的节点(key, value)
*
* @param: [key, value]
* @return: void
* @auther: wjy
* @date: 2020/3/15 17:55
*/
public void insert(int key, int value) {
// 见⑧添加新元素
node = insert(node, key, value);
// 保持根节点为黑色
node.color = BLACK;
}

⑤左旋转

  • 向 2-3 树的 2 节点中添加一个新元素的第一种情况 —> 对应到红黑树中表示:如下图所示。

Alt text

  • 在上图的红黑树中,添加的新元素(红色节点)在黑色节点的左侧:直接添加(对应 2-3 树中的一个 3 节点)
  • 向 2-3 树的 2 节点中添加一个新元素的第二种情况 —> 对应到红黑树中表示:如下图所示。

Alt text

  • 在上图的红黑树中,添加的新元素(红色节点)在黑色节点的右侧:先添加(此时红黑树不满足我们定义的左倾红黑树的性质) 、再调整(进行一次左旋转)。

Alt text

  • 左旋转的过程(注意:旋转前后的红黑树都要满足二分搜索树的性质)
    1. 让 x 的左子树 T2 变成 node 的右子树
    2. 让 node 变成 x 的左子树
    3. 维护节点的颜色
      • x 的颜色等于 node 的颜色(可能是红色,也可能是黑色)。因为在左旋转之前的树中,node 是根节点,现在 x 变成了根节点,根节点的颜色应该保持一致。
      • node 的颜色应该设置为红色。在原来的 2-3 树中,新加入的节点 42 与 37 形成了一个新的 3 节点。通过左旋转之后,并没有改变 3 节点中的两个元素,只是置换了两个元素的位置(在红黑树中)。所以为了表示它们在旋转前后都是原来的 2-3 树中的同一个 3 节点,node 节点要设置为红色。

Alt text
Alt text
Alt text
Alt text
Alt text

  • 注意:
  1. 左旋转只是一个子过程,在左旋转的过程中并不维持红黑树的性质,我们只需要通过旋转操作让两个元素对应是原来的 2-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
/**
* 功能描述: 对传入的node节点进行左旋转
* 返回旋转之后新的子树的根节点
*
* node x
* / \ 左旋转(node) / \
* T1 x ---------> node T3
* / \ / \
* T2 T3 T1 T2
*
* @param: [node]
* @return: tree.redblacktree.RBTree.TreeNode
* @auther: wjy
* @date: 2020/3/15 23:53
*/
private TreeNode leftRotate(TreeNode node) {
// 记录node节点的右孩子x
TreeNode x = node.right;
// 左旋转
node.right = x.left;
x.left = node;
// 维持节点的颜色
x.color = node.color;
node.color = RED;
// 返回旋转后子树的新的根节点,在添加元素的操作中会对根节点的颜色做进一步的处理。
return x;
}

⑥颜色翻转

  • 向 2-3 树的 3 节点中添加一个新元素的第一种情况 —> 对应到红黑树中表示:如下图所示。

Alt text
Alt text

  • 在上图的红黑树中添加一个新元素 66,应该添加到 42 的右孩子。—> 对应到 2-3 树中表示:原来的 2-3 树中有一个 3 节点(37 | 42),添加一个新元素 66,形成一个临时的 4 节点(37 | 42 | 66)。
  • 然后将临时的 4 节点变形成由 3 个 2 节点组成的子树。 —> 对应到红黑树中表示:三个节点都应该是黑色的节点,我们需要将两个红色节点的颜色翻转成黑色。

Alt text

  • 最后由 3 个 2 节点组成的子树的根节点要继续向上与其父亲节点进行融合。—> 对应到红黑树中表示:需要将根节点的颜色翻转成红色。

Alt text

  • 代码实践:颜色翻转

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* 功能描述: 颜色翻转
* 调用前需要保证以node为根的子树满足翻转条件
*
* @param: [node]
* @return: void
* @auther: wjy
* @date: 2020/3/15 11:16
*/
private void flipColors(TreeNode node) {
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}

⑦右旋转

  • 向 2-3 树的 3 节点中添加一个新元素的第二种情况 —> 对应到红黑树中表示:如下图所示。

Alt text
Alt text

  • 在上图的红黑树中添加一个新元素 12,应该添加到 37 的左孩子。—> 对应到 2-3 树中表示:原来的 2-3 树中有一个 3 节点(37 | 42),添加一个新元素 12,形成一个临时的 4 节点(12 | 37 | 42)。
  • 然后将临时的 4 节点变形成由 3 个 2 节点组成的子树 —> 对应到红黑树中表示:需要先对节点 42 进行一次右旋转,右旋转之后,红黑树的结构满足进行颜色翻转的条件,此时再对红黑树进行一次颜色翻转,具体见 ⑥颜色翻转
  • 右旋转的过程(注意:旋转前后的红黑树都要满足二分搜索树的性质)
    1. 让 x 的右子树 T1 变成 node 的左子树
    2. 让 node 变成 x 的右子树
    3. 维护节点的颜色
      • x 的颜色等于 node 的颜色(可能是红色,也可能是黑色),因为在右旋转之前的树中,node 是根节点,现在 x 变成了根节点,根节点的颜色应该保持一致。
      • node 的颜色应该设置为红色。因为在右旋转之后,三个节点对应到原来的 2-3 树中还是临时的 4 节点,所以 node 节点是红色表示它和它的父亲节点在原来的 2-3 树中是融合在一起的。

Alt text
Alt text
Alt text
Alt text
Alt text
Alt text

  • 代码实践:右旋转

Alt text

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
/**
* 功能描述: 对传入的node节点进行右旋转
* 返回旋转之后新的子树的根节点
*
* y x
* / \ / \
* x T4 向右旋转(y) z y
* / \ - - - - - - - -> / \ / \
* z T3 T1 T2 T3 T4
* / \
* T1 T2
*
* @param: [node]
* @return: tree.redblacktree.RBTree.TreeNode
* @auther: wjy
* @date: 2020/3/15 11:29
*/
private TreeNode rightRotate(TreeNode node) {
// 记录node节点的左孩子x
TreeNode x = node.left;
// 右旋转
node.left = x.right;
x.right = node;
// 维持节点的颜色
x.color = node.color;
node.color = RED;
return x;
}

  • 向 2-3 树的 3 节点中添加一个新元素的第三种情况 —> 对应到红黑树中表示:如下图所示。

Alt text
Alt text

  • 在上图的红黑树中添加一个新元素 40,应该添加到 37 的右孩子。—> 对应到 2-3 树中表示:原来的 2-3 树中有一个 3 节点(37 | 42),添加一个新元素 12,形成一个临时的 4 节点(37 | 40 | 42)。
  • 然后将临时的 4 节点变形成由 3 个 2 节点组成的子树 —> 对应到红黑树中表示:需要先对节点 37 进行一次左旋转,左旋转之后,红黑树的结构满足进行右旋转的条件,此时再对红黑树进行一次右旋转,具体见 ⑦右旋转

Alt text
Alt text
Alt text
Alt text
Alt text

⑧添加新元素

  • 下图总结了在红黑树中添加新元素的所有情况:

Alt text

  • 添加新元素后维护红黑树性质的方法:使用二分搜索树的策略将新元素添加进红黑树后,按照上图顺序依次判断该子树是否需要左旋转、右旋转和颜色翻转,然后将维护后的新的根节点返回给递归调用的上一层,在上一层继续维护红黑树的性质。
  • 代码实践:添加新元素
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
/**
* 功能描述: 向以node为根的红黑树中插入新的节点(key, value)
* 返回插入新节点后红黑树的根
*
* @param: [node, key, value]
* @return: tree.redblacktree.RBTree.TreeNode
* @auther: wjy
* @date: 2020/3/15 17:50
*/
private TreeNode insert(TreeNode node, int key, int value) {
// 搜索插入位置
if (node == null) {
count++;
// 默认插入红色节点
return new TreeNode(key, value);
}
if (key == node.key) {
node.value = value;
} else if (key < node.key) {
node.left = insert(node.left, key, value);
} else {
node.right = insert(node.right, key, value);
}

// 红黑树性质的维护
// 是否需要左旋转
if (isRed(node.right) && !isRed(node.left)) {
node = leftRotate(node);
}
// 是否需要右旋转
if (isRed(node.left) && isRed(node.left.left)) {
node = rightRotate(node);
}
// 是否需要翻转
if (isRed(node.left) && isRed(node.right)) {
flipColors(node);
}

return node;
}

⑨删除新元素

⑩代码实现 + 测试

  • 查找方法与二分搜索树(红黑树是一种自平衡的二分搜索树)的查找方法一致
  • 前序、中序、后序和层序遍历方法与树的遍历方法一致
  • 红黑树的全部操作如下:
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
package tree.redblacktree;

import java.util.LinkedList;
import java.util.Queue;

/**
* @author: wjy
* @date: 2020/3/15
* @description: 红黑树
*/
public class RBTree {

private static final boolean RED = true;
private static final boolean BLACK = false;

private class TreeNode {
public int key;
public int value;
public TreeNode left;
public TreeNode right;
public boolean color;

TreeNode(int key, int value) {
this.key = key;
this.value = value;
this.left = null;
this.right = null;
// 默认的节点颜色为红色
this.color = RED;
}
}

private TreeNode node;
private int count;

public RBTree() {
this.node = null;
this.count = 0;
}

/**
* 功能描述: 判断节点的颜色
*
* @param: [node]
* @return: boolean
* @auther: wjy
* @date: 2020/3/15 12:23
*/
private boolean isRed(TreeNode node) {
if (node == null) {
return BLACK;
}
return node.color;
}

/**
* 功能描述: 查看以node为根的红黑树中是否包含键值为key的节点
*
* @param: [node, key]
* @return: boolean
* @auther: wjy
* @date: 2020/3/15 17:58
*/
private boolean contain(TreeNode node, int key) {
if (node == null) {
return false;
}
if (key == node.key) {
return true;
} else if (key < node.key) {
return contain(node.left, key);
} else {
return contain(node.right, key);
}
}

/**
* 功能描述: 对传入的node节点进行左旋转
* 返回旋转之后新的子树的根节点
*
* node x
* / \ 左旋转(node) / \
* T1 x ---------> node T3
* / \ / \
* T2 T3 T1 T2
*
* @param: [node]
* @return: tree.redblacktree.RBTree.TreeNode
* @auther: wjy
* @date: 2020/3/15 23:53
*/
private TreeNode leftRotate(TreeNode node) {
// 记录node节点的右孩子x
TreeNode x = node.right;
// 左旋转
node.right = x.left;
x.left = node;
// 维持节点的颜色
x.color = node.color;
node.color = RED;
// 返回旋转后子树的新的根节点,在添加元素的操作中会对根节点的颜色做进一步的处理。
return x;
}

/**
* 功能描述: 对传入的node节点进行右旋转
* 返回旋转之后新的子树的根节点
*
* y x
* / \ / \
* x T4 向右旋转(y) z y
* / \ - - - - - - - -> / \ / \
* z T3 T1 T2 T3 T4
* / \
* T1 T2
*
* @param: [node]
* @return: tree.redblacktree.RBTree.TreeNode
* @auther: wjy
* @date: 2020/3/15 11:29
*/
private TreeNode rightRotate(TreeNode node) {
// 记录node节点的左孩子x
TreeNode x = node.left;
// 右旋转
node.left = x.right;
x.right = node;
// 维持节点的颜色
x.color = node.color;
node.color = RED;
return x;
}

/**
* 功能描述: 颜色翻转
* 调用前需要保证以node为根的子树满足翻转条件
*
* @param: [node]
* @return: void
* @auther: wjy
* @date: 2020/3/15 11:16
*/
private void flipColors(TreeNode node) {
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}

/**
* 功能描述: 向以node为根的红黑树中插入新的节点(key, value)
* 返回插入新节点后红黑树的根
*
* @param: [node, key, value]
* @return: tree.redblacktree.RBTree.TreeNode
* @auther: wjy
* @date: 2020/3/15 17:50
*/
private TreeNode insert(TreeNode node, int key, int value) {
// 搜索插入位置
if (node == null) {
count++;
// 默认插入红色节点
return new TreeNode(key, value);
}
if (key == node.key) {
node.value = value;
} else if (key < node.key) {
node.left = insert(node.left, key, value);
} else {
node.right = insert(node.right, key, value);
}

// 红黑树性质的维护
// 是否需要左旋转
if (isRed(node.right) && !isRed(node.left)) {
node = leftRotate(node);
}
// 是否需要右旋转
if (isRed(node.left) && isRed(node.left.left)) {
node = rightRotate(node);
}
// 是否需要翻转
if (isRed(node.left) && isRed(node.right)) {
flipColors(node);
}

return node;
}

/**
* 功能描述: 对以node为根的红黑树进行层序遍历
*
* @param: [node]
* @return: void
* @auther: wjy
* @date: 2020/3/15 18:12
*/
private void levelOrder(TreeNode node) {
Queue<TreeNode> queue = new LinkedList<>();
queue.add(node);
while (!queue.isEmpty()) {
TreeNode treeNode = queue.poll();
System.out.print(treeNode.key + "(" + treeNode.color + ") ");
if (treeNode.left != null) {
queue.add(treeNode.left);
}
if (treeNode.right != null) {
queue.add(treeNode.right);
}
}
}

/**
* 功能描述: 对以node为根的红黑树进行前序遍历
*
* @param: [node]
* @return: void
* @auther: wjy
* @date: 2020/3/15 1:29
*/
private void preOrder(TreeNode node) {
if (node == null) {
return;
}
System.out.print(node.key + " ");
preOrder(node.left);
preOrder(node.right);
}

/**
* 功能描述: 对以node为根的红黑树进行中序遍历
*
* @param: [node]
* @return: void
* @auther: wjy
* @date: 2020/3/15 17:58
*/
private void inOrder(TreeNode node) {
if (node == null) {
return;
}
inOrder(node.left);
System.out.print(node.key + " ");
inOrder(node.right);
}

/**
* 功能描述: 对以node为根的红黑树进行后序遍历
*
* @param: [node]
* @return: void
* @auther: wjy
* @date: 2020/3/15 1:30
*/
private void postOrder(TreeNode node) {
if (node == null) {
return;
}
postOrder(node.left);
postOrder(node.right);
System.out.print(node.key + " ");
}

public int size() {
return count;
}

public boolean isEmpty() {
return count == 0;
}

/**
* 功能描述: 判断是否包含key
*
* @param: [key]
* @return: boolean
* @auther: wjy
* @date: 2020/3/15 17:55
*/
public boolean contain(int key) {
return contain(node, key);
}

/**
* 功能描述: 向红黑树中添加新的节点(key, value)
*
* @param: [key, value]
* @return: void
* @auther: wjy
* @date: 2020/3/15 17:55
*/
public void insert(int key, int value) {
node = insert(node, key, value);
// 保持根节点为黑色
node.color = BLACK;
}

/**
* 功能描述: 红黑树的层序遍历
*
* @param: []
* @return: void
* @auther: wjy
* @date: 2020/3/15 17:45
*/
public void levelOrder() {
levelOrder(node);
}

/**
* 功能描述: 红黑树的前序遍历
*
* @param: []
* @return: void
* @auther: wjy
* @date: 2020/3/15 18:05
*/
public void preOrder() {
preOrder(node);
}

/**
* 功能描述: 红黑树的中序遍历
*
* @param: []
* @return: void
* @auther: wjy
* @date: 2020/3/15 18:05
*/
public void inOrder() {
inOrder(node);
}

/**
* 功能描述: 红黑树的后序遍历
*
* @param: []
* @return: void
* @auther: wjy
* @date: 2020/3/15 18:05
*/
public void postOrder() {
postOrder(node);
}
}
  • 测试红黑树的代码:
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
package tree.redblacktree;

/**
* @author: wjy
* @date: 2020/3/15
* @description: 测试红黑树
*/
public class Test {
public static void main(String[] args) {
int[] arr = new int[]{42, 37, 12, 18, 6, 11};
RBTree rbTree = new RBTree();
System.out.println("红黑树是否为空: " + rbTree.isEmpty());
for (int i = 0; i < 6; i++) {
rbTree.insert(arr[i], i);
}
System.out.println("红黑树的节点个数: " + rbTree.size());
System.out.println("红黑树的层序遍历: ");
rbTree.levelOrder();
System.out.println("\n红黑树的前序遍历: ");
rbTree.preOrder();
System.out.println("\n红黑树的中序遍历: ");
rbTree.inOrder();
System.out.println("\n红黑树的后序遍历: ");
rbTree.postOrder();
}
}

Alt text

  • 通过前序、中序、后序和层序遍历的结果可以推算出红黑树的结构:

Alt text

  • 也可以推算出与其等价的 2-3 树的结构:

Alt text


4.常见面试问题

①红黑树的数据结构是怎么定义的?

  • 具体见 3.红黑树—③数据结构

②红黑树有哪些性质?

  • 具体见 3.红黑树—②基本性质

③红黑树的各种操作的时间复杂度是多少?

  • 最大高度: 2lognlogn 个红色节点 + logn 个黑色节点,此时该条路径上每一个黑色节点的左孩子都是红色节点。)
  • 增删改查的时间复杂度:O(logn)

④红黑树相比于 BST 和 AVL 树有什么优点?

  • BST:最大高度不定,可能会退化为链表。
    • 优点:内部实现简单,没有复杂的维持平衡的操作。对于完全随机的数据,并不会退化为链表。
    • 缺点:极端情况会退化为链表(数据按顺序进入二分搜索树时)或者高度不平衡(数据近乎有序时)
  • AVL 树:采用了平衡二叉树的策略,最大高度为 logn,且不会退化为链表,对于查询操作(get、set、contain 等方法)性能较高。
  • 红黑树:并不完全满足平衡二叉树的定义,最大高度为 2logn,它可以保持自平衡而不会退化为链表,对于插入和删除操作(insert、delete 等方法)性能较高。
  • AVL 树和红黑树的对比:
    • 它们都是在二分搜索树的基础上添加了一些其他的性质,来保证自己不会退化为链表。
    • 红黑树的增删操作快于 AVL 树,查找操作慢于 AVL 树(因为 AVL 树的最大高度是 logn,红黑树的最大高度是 2logn,它们是常数级别的差异),所以 AVL 树适用于查询较多的情况,而红黑树适用于插入和删除较多的情况。
    • 红黑树的统计性能更优,虽然其时间复杂度与 AVL 树是同一个级别的,但是综合增删改查所有的操作,红黑树在平均情况下更好一些。
    • 总结:红黑树相对于 AVL 树来说,牺牲了部分平衡性以换取插入 / 删除操作时少量的旋转操作,整体性能要优于 AVL 树。

⑤红黑树的应用?

  • 由于红黑树的统计性能(综合增删改查所有的操作)更优,所以很多语言内部的容器类中的有序映射都是基于红黑树实现的。例如:Java 中的 TreeMap、TreeSet、JDK 1.8 后的 HashMap 和 C++ 的 STL 中的 map 和 set。
  • Java集合框架总结+源码分析

附录

0%