二叉树

基本性质:

每个节点都不能有多于两个的儿子,平均二叉树的深度比 N 小的多,二叉查找树深度的平均值是 O(log N)。

二叉查找树

基本性质:

  • 对于树中每个节点 X,他在左子树所有关键字值小于 X 的关键字值,而它右子树中所有关键字值大于 X 的关键字值(左小右大)。

  • 一棵树的所有的结点的深度的和称为内部路径长,令 D(N) 是具有 N 个节点的某棵树 T 的内部路径长,有递归关系如下: D(N) = D(i) + D(N-i-1) + N - 1, D(N) 平均值为 O(N log N)。

例程

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
SearchTree Delete(int X, SearchTree T)
{
Position TmpCell;
if(T == NULL)
printf("Element not found");
else if ( X < T->Element) //向左
T->Left = Delete(X, T->Left);
else if ( X > T->Element)
T->Right = Delete(X, T->Left);
else if (T->Left && T->Right) //找到元素准备删除,双孩
{
TmpCell = FindMin( T->Right);
T->Element = TmpCell ->Element;
T->Right = Delete(T->Element, T->Right);
}
else //一个孩子或 0 个孩子
{
TmpCell = T;
if(T->Left == NULL)
T = T->Right;
else if(T->Right == NULL)
T = T->Left;
free(TmpCell);
}
return T;
}

AVL 树

基本性质:

  • 一棵 AVL 树是其每个节点的左子树和右子树的高度最多差 1 的二叉查找树。(空树高度定义为 -1)
  • 一个 AVL 树的高度最多为1.44log(N + 2) - 1.328
  • 最少节点数 S(h) = S(h-1) + S(h-2) + 1

不平衡的情况(必须重新平衡的结点叫做 a ):

  • 对 a 的左儿子的左子树进行一次插入
  • 对 a 的左儿子的右子树进行一次插入
  • 对 a 的右儿子的左子树进行一次插入
  • 对 a 的右儿子的右子树进行一次插入

单旋转修复情形1

1
2
3
4
5
6
7
8
9
10
11
12
Position SingleRotateWithLeft(Position K2) {
Position K1;
K1 = K2->Left;
K2->Left = K1->Right;
K1->Right = K2;
K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1;
K1->Height = Max(Height(K1->Left), K2->Height) + 1;
return K1; //新的根
}

左-右双旋转修复情形2

1
2
3
4
5
6
7
8
Position DoubleRotateWithLeft(Position K3) {
//旋转 K1 和 K2 之间
K3->Left = SingleRotateWithLeft(K3->Left);
//旋转 K3 和 K2 之间
return SingleRotateWithLeft(K3);
}

右-左双旋转修复情形3

1
2
3
4
5
6
7
8
Position DoubleRotateWithRight(Position K3) {
//旋转 K1 和 K2 之间
K3->Right = SingleRotateWithLeft(K3->Left);
//旋转 K3 和 K2 之间
return SingleRotateWithLeft(K3);
}

单旋转修复情形4

1
2
3
4
5
6
7
8
9
10
11
12
13
Position SingleRotateWithRight(Position K1) {
Position K2;
K2 = K1->Right;
K1->Right = K2->Left;
K2->Left = K1;
K1->Height = Max(Height(K1->Left), Height(K1->Right)) + 1;
K2->Height = Max(K1->Height, Height(K2->Right)) + 1;
return K2;
}

向 AVL 树插入节点

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
30
31
32
33
34
35
36
37
38
39
40
41
AvlTree Insert(int X, AvlTree T) {
if (T == NULL) {
//如果树为空,创建并返回只有一个结点的树
T = malloc(sizeof(AvlNode));
if (T == NULL) {
printf("Out of space!!!");
exit(1);
} else {
T->data = X;
T->Height = 0;
T->Left = T->Right = NULL;
}
} else if (X < T->data) {
T->Left = Insert(X, T->Left);
if (Height(T->Left) - Height(T->Right) == 2) {
if (X < T->Left->data)
T = SingleRotateWithLeft(T);
else
T = DoubleRotateWithLeft(T);
}
} else if (X > T->data) {
T->Right = Insert(X, T->Right);
if (Height(T->Right) - Height(T->Left) == 2) {
if (X < T->Right->data)
T = SingleRotateWithRight(T);
else
T = DoubleRotateWithRight(T);
}
}
T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
return T;
}
int Max(int a, int b) {
//return (a >= b ? a : b);
if (a > b)
return a;
else
return b;
}

AVL 树节点的删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
AvlTree Delete(int X, AvlTree T) {
Position tmpnode;
if (T == NULL) {
printf("the tree have not any treenode\n");
exit(-1);
} else if (X < T->data)
T->Left = Delete(X, T->Left);
else if (X > T->data)
T->Right = Delete(X, T->Right);
else if (T->Left && T->Right) {
tmpnode = FindMin(T->Right);
T->data = tmpnode->data;
T->Right = Delete(T->data, T->Right);
} else {
tmpnode = T;
if (T->Left == NULL)
T = T->Right;
else if (T->Right == NULL)
T = T->Left;
free(tmpnode);
}
return T;
}

伸展树

基本性质

  • 它保证从空树开始任意连续 M 次对树的操作最多花费 O(MlogN) 时间。
  • 当一个节点被访问后,他就要经过一系列 AVL 树的旋转被放到根上。注意:如果一个节点很深,那么在其路径上就存在许多的结点也相对较深,通过重新构造可以使访问这些节点进一步访问的时间变少。

展开

从底部向上沿着访问路径旋转。令 X 是在访问路径上的一个(非根)节点,我们将在这个路径上实施旋转操作。如果 X 的父亲点是树根,那么只要旋转 X 和树根。这就是沿着访问路径上的最后的旋转。

B-树

基本性质

  • 树的根或者是一片树叶,或者其儿子数在 2 和 M 之间。
  • 除根外,所有非树叶节点的儿子数在 [M/2] 和 M 之间。
  • 所有的树叶都在相同深度上。

B-树实际用于数据库系统,在那里树被储存在物理磁盘而非主存中。对磁盘的访问和主存操作慢几个数量级。

总结

  • 表达式树是更一般结构即所谓分析树的一个小例子,分析树是编译器设计中的核心数据结构。
  • 分析树不是二叉树,而是表达式树相对简单的扩充。
  • 查找树性能严重依赖于输入,而输入是随机的。