平衡搜索树

Posted on

MIT《算法导论》课程第10课《平衡搜索树》学习笔记.

我们希望搜索树的数据结构有$n$个元素，树高为$O(\log n)$。

红黑树

一种BST，每个结点都有称为“色域”的额外信息。

红黑树的特性

  1. 每个结点或红或黑
  2. 根结点和叶子结点都是黑色
  3. 每个红色结点的双亲结点是黑色
  4. 从结点x到x的子孙结点的所有简单路径，具有相同的黑色结点数，称为“黑高度”。

有n个键的红黑树的高度h满足：

$$
h \le 2 \log(n + 1) = O(\log n)
$$

证明如下。

将红色结点合并入其双亲结点。

此时所有的叶子结点有相同的深度h’，即为黑深度（Black height），因为从根结点到每个叶子结点经过同样多的黑色结点，而现在只剩下了黑色结点。

叶子结点的数目=n+1（由归纳法）

在2-3-4树中，

$$
2^{h’} \le 叶子结点的数目 \le 4^{h’}
$$

于是：

$$
2^{h’} \le n + 1 \
h’ \le \log(n + 1)
$$

而

$$
h’ \ge \frac{1}{2}h（由于从跟结点到叶子结点的简单路径中，黑色结点至少占一半）
$$

因此

$$
h \le 2\log(n+1)
$$

红黑树的查询在$O(\log(n))$时间内完成。

红黑树的增删

1
2
3
4
Update(Insert & Delete) -> modify the tree
	BST的操作
	改变结点的颜色
	restructuring of links via rotation
1
2
3
4
5
RB_Insert(x):
	Tree_Insert(x)
	为x选择颜色为红
		问题：父节点可能是红色->破坏了性质3
		Solution: 将问题造成的破坏上移，重新着色，然后用旋转弥补
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
RB_Insert_Fixup(T, x):
	Tree_Insert(T, x)
	while x.parent.color == RED:
		if x.parent == x.parent.parent.left:
			y = x.parent.parent.right
			# case 1
			if y.color == RED:
				x.parent.color = BLACK
				y.color = BLACK
				x.parent.parent.color = RED
				x = x.parent.parent
			# case 2
			elif x == x.parent.right:
				x = x.parent
				Left_Rotate(T, x)
			# case 3
			else:
				x.parent.color = BLACK
				x.parent.parent.color = RED
				Right_Rotate(T, x.parent.parent)
		else: 
			# 左右对称
	T.root.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
29
RB_Delete_Fixup(T, x):
	while x !=  T.root and x.color == BLACK:
		if x == x.parent.left:
			w = x.parent.right
			# case 1
			if w.color == RED:
				w.color = BLACK
				x.parent.color = RED
				Left_Rotate(T, x.parent)
				w = x.parent.right
			# case 2
			if w.left.color == BLACK and w.right.color == BLACK:
				w.color = RED
				x = x.parent
			# case 3
			else:
				if w.right.color == BLACK:
					w.left.color = BLACK
					w.color = RED
					Right_Rotate(T, w)
					w = x.parent.right
				w.color = x.parent.color
				x.parent.color = BLACK
				w.right.color = BLACK
				Left_Rotate(T, x.parent)
				x = T.root
		else:
			# 左右对称
	x.color = BLACK