红黑树

发表于 | 分类于 | 阅读次数:
字数统计: 947 | 阅读时长 ≈ 4

二叉树分完美(Perfect)完全(Complete)完满(Full)，本篇涉及到二叉树的完美平衡。

Brief

理想情况下，我们希望能够保持二分查找树的平衡，但是在动态插入的过程中保证完美平衡代价太高。

为了保证查找树的平衡，现放宽灵活性，允许树中的一个节点保存多个键，由此产生出2-3查找树。但用直白的方法实现大多数操作并不方便，需要的代码和额外开销都是大量的。

本篇涉及的红黑树就是一种用来表达和实现2-3树的数据结构。

红黑树即是二叉查找树，又是2-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
23
24
25
26
private static final boolean RED = true;
private static final boolean BLACK = false;
private class Node {
  Key key;
  Value val;
  Node left, right;
  int N;
  boolean color;
  // 节点初始化
  Node(Key key, Value val, int N, boolean color) {
    this.key = key;
    this.val = val;
    this.N = N;
    this.color = color;
  }
}
private boolean isRed(Node x) {
  if (x == null) {
    return false;
  } else {
    return x.color == RED;
  }
}

每一个节点只有一个父节点指向的链接或者没有父节点(这个节点是根节点)，这里约定空链接为黑色。

节点变换

节点变换使得红黑树在完成插入、删除等操作之后，仍能符合红黑树的一般定义。

左旋

左旋是为了符合定义中的“红链接均为左链接”，考虑一种情况：

图01

此时需要通过左旋变换，将红链接“置左”，变成如下图：

图2

此时这棵子树的父节点从h变成x并返回，代码如下：

1
2
3
4
5
6
7
8
9
10
Node rotateLeft(Node h) {
  Node x = h.right;
  h.right = x.left;
  x.left = h;
  x.color = h.color;
  h.color = RED;
  x.N = h.N;
  h.N = 1 + size(h.left) + size(h.right);
  return x;
}

右旋

右旋是为了符合定义中的“没有任何一个节点同时和两条红链接相连”，考虑一种情况：

图3

此时势必需要进行右旋，然后才能经过其它操作转换这种情形，具体代码比照左旋：

1
2
3
4
5
6
7
8
9
10
Node rotateRight(Node h) {
  Node x = h.left;
  h.left = x.right;
  x.right = h;
  x.color = h.color;
  h.color = RED;
  x.N = h.N;
  h.N = 1 + size(h.left) + size(h.right);
  return x;
}

色转

在右旋后往往会出现下图中出现的情况：

图4

此时将连接在同一个节点上的两个红链接变色，然后将该指向该节点的链接设置为RED。代码如下：

1
2
3
4
5
void flipColors(Node h) {
  h.color = RED;
  h.left.color = BLACK;
  h.right.color = BLACK;
}

实现

这里给出完整插入方法：

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
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;
  }
  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);
  }
  return h;
}

小结

红黑树的原理并不难理解，但是其中的变换比较冗杂，从操作上来说，运行的时间都是对数级别，最坏的情况是最左边的路径交替出现红链接和黑链接，而且红黑树继承了二叉查找树的特质，通过中序遍历，就可以按照键的比较规则有序输出。如果要进行删除操作，会涉及四种删除情形。