Introduction to Algorithms：红黑树（笔记）

发表于

红黑树是一种可以自动平衡的二叉查找树。它在二叉查找树的基础上为每个节点添加了额外的属性：红色或黑色的颜色。在进行插入、删除操作后，它会进行自动平衡操作。从而确保该树的树根到叶子的所有路径长度相差保持在2位以下。

条件

红黑树需要满足以下条件：

  1. 所有节点为黑或白色；
  2. 根节点为黑；
  3. 所有叶子（Nil）为黑色；
  4. 如果一个节点为红色，那么它的子节点都为黑色；
  5. 对所有的节点而言，该节点到它的叶子的所有简单路径所包含的黑色节点是相同的。

操作

旋转操作

旋转操作如下：

1
2
3
4
5
6
     |                        |
    [y]    Right-Rotate      [x]
   /   \   ~~~~~~~~~~~>     /   \
 [x]    c  <~~~~~~~~~~~~   a    [y]
 / \        Left-Rotate          / \
a   b                           b   c

1.右旋转 Right-Rotate(T, y)

1
2
3
4
5
6
7
8
9
10
11
12
13
x = y.left
y.left = x.right
if x.right != nil
	x.right.p = y
x.p = y.p
if y.p == nil
	T.root = x
else y == y.p.left
	y.p.left = x
else
	y.p.right = x
x.right = y
y.p = x

2.左旋转 Left-Rotate(T, x)

1
2
3
4
5
6
7
8
9
10
11
12
13
y = x.right
x.right = y.left
if y.left != nil
	y.left.p = x
y.p = x.p
if x.p == nil
	T.root = y
else if x.p.left == x
	x.p.left = y
else
	x.p.right = y
y.left = x
x.p = y