算法4 左倾红黑树

现代计算机和网络允许我们查找海量的信息,前提是拥有高效检索这些信息的能力。符号表(或字典)则是用于检索信息的经典查找算法或数据结构,红黑树正是其中的代表。

在学习红黑树之前,我们需要对有序符号表进行进一步的了解。

二叉查找树(BST)

一棵二叉查找树是一棵二叉树,每个节点都含有一个可比较的键,且每个节点的键都大于其左子树中的任意节点的键而小于其右子树的任意节点的键。

Api如下:

部分代码如下:

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
public class BST<K extends Comparable<K>, V> {

private Node root;

public boolean isEmpty() {
return root == null;
}

public int size() {
return size(root);
}

private int size(Node x) {
return x == null ? 0 : x.n;
}

private class Node {
private K key;
private V value;
private Node left, right;
private int n; // 树的大小(节点计数器)

private Node(K key, V value, int n) {
this.key = key;
this.value = value;
this.n = n;
}
}
}

完整代码:https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/BST.java.html

查找

1
2
3
4
5
6
7
8
9
10
11
public V get(K key) {
return get(root, key);
}

private V get(Node x, K key) {
if (x == null) return null; // 如果树是空的,查找未命中。
int cmp = key.compareTo(x.key);
if (cmp < 0) return get(x.left, key); // 查找的键较小则选择左子树
else if (cmp > 0) return get(x.right, key); // 查找的键较大则选择右子树
else return x.value; // 查找命中
}

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
public void put(K key, V value) {
root = put(root, key, value);
}

private Node put(Node x, K key, V value) {
if (x == null) return new Node(key, value, 1); // 如果树是空的,创建并返回新节点。
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = put(x.left, key, value); // 递归左子树
else if (cmp > 0) x.right = put(x.right, key, value); // 递归右子树
else x.value = value; // 键已存在,替换值
x.n = size(x.left) + size(x.right) + 1; // 更新节点计数器
return x;
}

最大键和最小键

  • 如果根节点的左链接为空,那么最小的键就是根节点

  • 否则左子树最左下的节点的键就是最小键

  • 最大键的方法是类似的,只是变为查找右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public K min() {
if (root == null) return null;
return min(root).key;
}

private Node min(Node x) {
return x.left == null ? x : min(x.left);
}

public K max() {
if (root == null) return null;
return max(root).key;
}

private Node max(Node x) {
return x.right == null ? x : max(x.right);
}

向上取整和向下取整

  • 向上取整(ceiling):大于等于Key的最小键
  • 向下取整(floor):小于等于key的最小键

1
2
3
4
5
6
7
8
9
10
11
12
13
public K floor(K key) {
Node x = floor(root, key);
return x == null ? null : x.key;
}

private Node floor(Node x, K key) {
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp == 0) return x; // 命中,直接返回
if (cmp < 0) return floor(x.left, key); // 从左子树中查找
Node t = floor(x.right, key); // 如果左子树没有,可能在右子树中,从右子树中查找
return t == null ? x : t; // 未找到,返回最终结果
}

向上取整的逻辑类似,将“左”变为“右”,同时将小于变为大于即可。

排名和选择

排名(rank):返回小于key的数量

选择(select):返回第k个键(找出排名为k的键, 从0开始)

排名从0开始计算,所以select(3)表示选择第4个键。

1
2
3
4
5
6
7
8
9
10
11
12
public K select(int k) {
Node x = select(root, k);
return x == null ? null : x.key;
}

private Node select(Node x, int k) {
if (x == null) return null;
int t = size(x.left);
if (t > k) return select(x.left, k); // 左子树的节点数大于k,所以在左子树中查找。
else if (t < k) return select(x.right, k - t - 1); // 左子树节点数小于k,在右子树中查找。(排名k要减去左子树的节点数量和当前节点1)
else return x;
}

排名和选择类似:

  • 如果key正好等于root,直接返回左子树的节点数即可。
  • 如果key大于root,遍历右子树时加上左子树的数量+1 (root自身)
1
2
3
4
5
6
7
8
9
10
11
public int rank(K key) {
return rank(root, key);
}

private int rank(Node x, K key) {
if (x == null) return 0;
int cmp = key.compareTo(x.key);
if (cmp < 0) return rank(x.left, key); // key较小,递归左子树
else if (cmp > 0) return size(x.left) + 1 + rank(x.right, key); // key较大,递归右子树,并加上左子树的节点数+1
else return size(x.left); // key相等,返回左子树大小
}

删除最大键和删除最小键

删除最小键:

1
2
3
4
5
6
7
8
9
10
11
public void deleteMin() {
if (root == null) return;
root = deleteMin(root);
}

private Node deleteMin(Node x) {
if (x.left == null) return x.right; // 左子树为空,表示x是最小键,直接返回右链接即可。x不再被引用,将被回收
x.left = deleteMin(x.left); // 递归左子树
x.n = size(x.left) + size(x.right) + 1; // 更新节点计数器
return x;
}

删除最大键的逻辑完全类似

删除操作

删除操作相对复杂:删除之后我们要处理两棵子树,但是被删除节点的父节点只有一条空出来的链接。关键是需要在删除节点x后用它的后继节点填补它的位置。

后继节点:大于x的左子树,小于x的右子树,即右子树中的最小节点。

  • 将指向即将被删除的结点的链接保存为 t
  • x 指向它的后继结点 min(t.right)
  • x 的右链接(原本指向一棵所有结点都大于 x.key 的二叉查找树)指向 deleteMin(t. right),也就是在删除后所有结点仍然都大于 x.key 的子二叉查找树;
  • x 的左链接(本为空)设为 t.left(其下所有的键都小于被删除的结点和它的后继结点)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 public void deleteKey(K key) {
root = deleteKey(root, key);
}

private Node deleteKey(Node x, K key) {
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = deleteKey(x.left, key); // 递归左子树
else if (cmp > 0) x.right = deleteKey(x.right, key); // 递归右子树
else { // 命中
// 左右被删除节点x的左右子树其一为空则很好处理,直接返回另一棵子树即可。
if (x.right == null) return x.left;
if (x.left == null) return x.right;
// 否则需要寻找后继节点,后继节点即右子树中的最小节点。
Node t = x;
x = min(x.right);
x.left = t.left;
}
x.n = size(x.left) + size(x.right) + 1;
return x;
}

范围查找

我先首先需要一个遍历二叉查找树的基本方法——中序遍历。

1
2
3
4
5
6
private void print(Node x) {
if (x == null) return;
print(x.left);
StdOut.println(x.key);
print(x.right;)
}

然后将它运用到范围查找:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public Iterable<K> keys() {
return keys(min(), max());
}

public Iterable<K> keys(K lo, K hi) {
Queue<K> queue = new Queue<>();
keys(queue, root, lo, hi);
return queue;
}

private void keys(Queue<K> queue, Node x, K lo, K hi) {
if (x == null) return;
int locmp = lo.compareTo(x.key);
int hicmp = hi.compareTo(x.key);
if (locmp < 0) keys(queue, x.left, lo, hi);
if (locmp <= 0 && hicmp >= 0) queue.enqueue(x.key);
if (hicmp > 0) keys(queue, x.right, lo, hi);
}

BST的分析

在最好的情况下,一棵含有N个节点的树是完全平衡的,每条空链接和根节点的距离都为lgN。

在最坏的情况下,搜索路径上可能有N个节点。这将导致BST的性能降低到线性级。

为了放置出现最坏的情况,我们需要一种能够自平衡的二叉查找树,称为平衡查找树,其中经典的数据结构算法为红黑树。但在学习红黑树之前,我们需要学习一种完全平衡的数据结构 2-3查找树,它和“左倾”红黑树是等同的,先学习2-3查找树有利于我们理解红黑树。

2-3 查找树

2-3查找树是一棵完美平衡的二叉查找树,学习2-3查找树时我们不需要实现具体代码,只需要了解其操作原理即可。

为了保证查找树的平衡性,我们需要一些灵活性:允许树种的一个节点保存多个键:

将一棵标准的二叉树中的节点称为2-节点(一个键和两条链接)。现在我们引入3-节点,它含有两个键和3条链接。

查找

插入

2-3查找树的插入操作相对复杂,需要考虑多种情况。

① 2-节点中插入新键

要在 2-3 树中插入一个新结点,我们可以和二叉查找树 一样先进行一次未命中的查找,然后把新结点挂在树的底部,但这样的话树无法保持完美平衡性。

我们使用 2-3 树的主要原因就在于它能够在插入后继续保持平衡

image-20210223181150248

② 向一棵只含有一个3-节点中插入新键

先将新键插入到3-节点中使他成为一个4-节点,然后再将他分解为三个2-节点组成的树。这也表明了一棵完美平衡的2-3树是如何生长的。

③ 向一个父结点为 2- 结点的 3- 结点中插入新键

类似情况2的操作,先将新键插入到3-节点中使他成为一个4-节点。然后将中间键移动到父节点中。

 ④ 向一个父结点为 3- 结点的 3- 结点中插入新键

它和上面是一样的,只是需要将4-父节点一直往上分解即可。

如果遇到根节点为变为4-节点,那么只需要分解根节点即可,操作和情况2相同,此时树的高度增加1。

汇总

将一个 4- 结点分解为一棵 2-3 树可能有 6 种情况:

image-20210223182923614

需要处理的情况太多,需要多种类型的节点,实现这些操作不仅需要大量的代码,而且他们所产生的额外开销可能会使算法比标准的二叉查找树更慢。

平衡一棵树的初衷是为了消除最坏情况(线性),同时希望这种保障所需的代码能越少越好。而左倾红黑树只需要一点点代价就能用一种统一的方式完成所有变换。

左倾红黑树

"左倾"红黑树(类似2-3查找树)是经典红黑树(类似2-3-4查找树)的一种变体,它和红黑树拥有相同的时间复杂度,但是更加容易实现。它规定红色结点只能存在于左节点。这大大的简化了红黑树的插入和删除逻辑。

左倾红黑树的基本思想是用标准的二叉查找树(只有2-节点)和一些额外的信息(颜色)来表示2-3查找树。

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

红链接将两个2-节点连接起来构成一个3-节点,黑链接则表示二叉查找树中的普通链接。

如果将一棵左倾红黑树中的红链接画平,那么所有的空连接到根节点的距离是相同的。如果将红链接相连的节点合并,得到的就是一棵2-3树。

颜色表示

方便起见,因为每个结点都只会有一条指向自己的链接(从它的父结点指向它),我们将 链接的颜色保存在表示结点的 Node 数据类型的布尔变量 color 中。如果指向它的链接是红色的, 那么该变量为 true,黑色则为 false。

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

private class Node {
private Key key;
private Value val;
private Node left, right;
private boolean color; // true 表示红色, false表示黑色
private int size;

public Node(Key key, Value val, boolean color, int size) {
this.key = key;
this.val = val;
this.color = color;
this.size = size;
}
}

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

旋转操作

某些操作中可能会出现两条连续的红链接或者红色右链接,我们需要通过旋转操作修复这些情况。

左旋转

右旋转

颜色转换

某些情况下回出现节点的左右链接均为红色的情况,这相当于2-3树中出现了4-节点,我们需要做的是分解4-节点。

只需要将红链接颜色变为黑色,再将当前节点链接变为红色即可。

image-20210224002409143
1
2
3
4
5
6
7
8
9
10
// flip the colors of a node and its two children
private void flipColors(Node h) {
// h must have opposite color of its two children
// assert (h != null) && (h.left != null) && (h.right != null);
// assert (!isRed(h) && isRed(h.left) && isRed(h.right))
// || (isRed(h) && !isRed(h.left) && !isRed(h.right));
h.color = !h.color;
h.left.color = !h.left.color;
h.right.color = !h.right.color;
}

插入

向单个2-节点中插入新建

向3-节点中插入新键

这里存在三种情况:

  • 新键最大:只需要颜色转换即可,相当于2-3树中分解4-节点。
  • 新键最小:出现两条连续的红链接,将红链接右旋转后变为第一种情况。
  • 新键介于两者之间:将红链左旋转后变为第二种情况。

颜色转换可能会使根节点变为红色,相当于2-3树中的根节点为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
23
public void put(Key key, Value val) {
if (key == null) throw new IllegalArgumentException();
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, RED, 1);

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;

// 在插入新节点后,判断三种情况,进行左旋转、有旋转、颜色变换。
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.size = size(h.left) + size(h.right) + 1;

return h;
}

红黑树的构造轨迹:

删除

红黑树put方法已经算是算法4这本书中最复杂的算法之一了,但是删除比这要更加复杂。

如果我们删除的是一个红节点则非常简单,并且不会破坏红黑树的平衡性,但是如果删除的是一个黑节点则不行。删除操作的关键在于避免删除黑节点,只需要在查找键的同时对红黑树进行变换,将黑节点转换成红节点删除,在递归回去的过程中再执行类似put方法的旋转变换让红黑树保持平衡。

删除最小键

  • 如果当前结点的左子结点不是 2- 结点,完成;
  • 如果当前结点的左子结点是 2- 结点而它的亲兄弟结点不是 2- 结点,将左子结点的兄弟结点 中的一个键移动到左子结点中;
  • 如果当前结点的左子结点和它的亲兄弟结点都 是 2- 结点,将左子结点、父结点中的最小键 和左子结点最近的兄弟结点合并为一个 4- 结 点,使父结点由 3- 结点变为 2- 结点或者由 4- 结点变为 3- 结点。
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
public void deleteMin() {
if (isEmpty()) throw new NoSuchElementException("BST underflow");
// 根节点,转换为4-节点。(需要通过后续的filpcolor操作变换)
if (!isRed(root.left) && !isRed(root.right)) root.color = RED;
root = deleteMin(root);
if (!isEmpty()) root.color = BLACK;
}

private Node deleteMin(Node h) {
if (h.left == null) return null;
// 如果当前节点不是2-节点(表示当前肯定是3个2-节点组成的子树),有两种情况。
// 1. 兄弟节点为2-节点,将他们合并为4-节点,即moveRedLeft中的filpColors()
// 2. 兄弟节点为3-节点,从兄弟节点中移动一个键到左子节点。
if (!isRed(h.left) && !isRed(h.left.left)) h = moveRedLeft(h);
h.left = deleteMin(h.left);
return balance(h);
}

private Node moveRedLeft(Node h) {
flipColors(h);
if (isRed(h.right.left)) {
h.right = rotateRight(h.right);
h = rotateLeft(h);
flipColors(h);
}
return h;
}

// 和put方法相同的变换操作
private Node balance(Node h) {
// assert (h != null);
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.size = size(h.left) + size(h.right) + 1;
return h;
}

moveRedLeft从兄弟节点移动一个键到左子节点图解:

删除最大键

删除最大键查找时的变换操作和删除最小键不同,因为左倾二叉树的所有红链接都是在左侧的。我们需要做的是在遍历过程中通过右旋转将红色链接移动到右边。

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
public void deleteMax() {
if (isEmpty()) throw new NoSuchElementException("BST underflow");
if (!isRed(root.left) && !isRed(root.right)) root.color = RED;
root = deleteMax(root);
if (!isEmpty()) root.color = BLACK;
}

private Node deleteMax(Node h) {
// 如果左链接是红色,移动到右边。
if (isRed(h.left)) h = rotateRight(h);
if (h.right == null) return null;

// 如果当前节点是2-节点,有两种情况。
// 1. 兄弟节点是2-节点,则合并为4-节点。
// 2. 兄弟节点是3-节点,从兄弟节点中移动一个键到左子节点。
if (!isRed(h.right) && !isRed(h.right.left)) h = moveRedRight(h);
h.right = deleteMax(h.right);
return balance(h);
}

private Node moveRedRight(Node h) {
flipColors(h);
if (isRed(h.left.left)) {
h = rotateRight(h);
flipColors(h);
}
return h;
}

moveRedRight从兄弟节点移动一个键到右子树图解:

删除任意节点

将删除最小键和删除最大键的操作结合起来,往左侧查找时使用删除最小键的逻辑,往右侧查找时使用删除最大键的逻辑。

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
public void delete(Key key) { 
if (key == null) throw new IllegalArgumentException("argument to delete() is null");
if (!contains(key)) return;
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) {
// 左侧查找,套用删除最小键的逻辑。
if (!isRed(h.left) && !isRed(h.left.left)) h = moveRedLeft(h);
h.left = delete(h.left, key);
} else {
// 右侧查找,套用删除最大键的逻辑。
if (isRed(h.left)) h = rotateRight(h);
if (key.compareTo(h.key) == 0 && (h.right == null)) return null;
if (!isRed(h.right) && !isRed(h.right.left)) h = moveRedRight(h);

// 如果命中,寻找后继节点进行替换。
if (key.compareTo(h.key) == 0) {
Node x = min(h.right);
h.key = x.key;
h.val = x.val;
// 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);
}

左倾红黑树分析

无论键的插入顺序如何,红黑树都几乎是完美平衡的,这从它和 2-3 树的一一对应关系以及 2-3 树的重要性质可以得到。一棵大小为 N 的红黑树的高度不会超过 2lgN。

这很容易证明,因为红黑树是完美黑色平衡的,并且不会出现连续的红链接,而黑色路径的长度最多为lgN。最坏的情况下左边路径的节点是红黑相间,所以红黑树的高度不会超过2lgN。

左倾红黑树完整代码见:https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/RedBlackBST.java.html

B树 (B-tree 了解即可)

通常我们需要存储非常大的数据量,例如存储在硬盘上我们需要处理连续的数据存储块或整个文件。外部储存不同于内存,需要花费很长的时间取寻找第一页的数据,只要找到了第一页数据,那么就可以流畅的读取后续其他页的数据。

但是在页内读取数据是非常快速的(一次io操作会读取一个扇区到内存,称为一页,通常是4k),我们需要用最少的时间去查找对应文件的第一页的数据。为此使用树对所有文件建立索引是有必要的。

普通的二叉树无法满足这个要求,因为硬盘中的数据量过大,树的高度无法控制。因此使用B树,B树允许一个节点中存储很多个键(内部节点),例如文件系统的一个节点能存储的键的数量就对应硬盘中的扇区(4k),对应一次io操作。500W条数据用B+树可以控制在三层以内,即查找任意一个数据最多只需要3次io。

B树类似于2-3树,每一个节点内部只能有2或3个子节点,或者说2-3树本质上就是一棵3阶的B树。B树可以预先定义每个节点中存储的键的数量M(M阶),例如下图是M=6的B树,每个节点允许包含M-1个键。

B树的性质和2-3树一致,当一个节点存储满了以后会进行分裂,然后树的高度增加1。

查找

插入

当节点的键存储满后,将中间键移动到父节点中,如果父节点存储满了,则进行分裂操作。

分析

对于节点数量为N的M阶B树,每次查找或插入操作的时间复杂度为 之间,所有内部节点(除根节点)拥有M/2 到 M-1条链接。

假设M为1024,N = 620亿, 那么 ,所以基本上很难出现高度大于4层的B树。

而对于文件系统,我们只需要将第一页的数据(B树的根节点)存储在内存中即可对数据进行高效的访问,基本上只需要几次io操作即可找到相对应的数据地址。

应用

B树还存在很多变体:B+ tree,B*tree,B#tree,...,他们通常应用在文件系统和数据库中:

  • Windows:NTFS
  • Mac:HFS,HFS+
  • Linux:ReiserFS,XFS,Ext3FS,JFS...
  • Databases: ORACLE,DB2,SQL...