11.5.红黑树

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