11.5.红黑树

发表于 更新于 分类于 ， 阅读次数： 本文字数： 437 阅读时长 ≈ 2 分钟

\(11.5\)红黑树(未完结)

1.红黑树的引入与相关概念

  前面介绍的\(B\)-树很符合我们对运行时间的的需要，但是它很难用代码实现。因此，我们设想创造一种树，它利用\(BST\)实现，但结构上与\(B\)-树等价。

  在\(2-3\)树中，叶子只有一个节点的情况和\(BST\)是完全一样的。而对于两个节点的情况，我们考虑将链接分成两种类型：红色(\(red\))的和黑色(\(black\))的。对于一个叶子三个节点的情况，我们可以用如下的形式表示：

  这么处理的好处是：我们可以不修改原有的\(BST\)来实现\(2-3\)树。给定任意一个\(2-3\)树，我们都可以立即生成一个对应的\(BST\)。例如下面的\(2-3\)树到红黑树的转换：

2.左斜红黑树的性质

  为了模拟\(2-3\)树，红黑树必须具有以下性质：

  1. 红色链接左斜。
  2. 没有一个节点与两个红色链接相连。
  3. 红黑树具有完美的“黑色平衡”：从根节点到空节点间的每个路径都具有相同数量的褐色链接。

  如果将红色链接画成水平的，那么可以得到下面的图示，这和\(2-3\)树几乎一致：

2.红黑树的旋转操作

  红黑树的左旋操作如下： 

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;
}

  红黑树的右旋操作如下： 

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;
}