树

基础知识

对于大量的输入数据，链表的线性访问时间太慢，不宜使用。而“树”大部分操作的运行时间平均为 $O(log N)$ 。

一课树是 $N$ 个节点 $N-1$ 条边的集合，其中的一个节点叫做根。

路径

从节点 $n_1$ 到 $n_k$ 的路径（path）定义为节点 $n_1, n_2, ..., n_k$ 的一个序列，使得对于 $1 \le i < k$ ,节点 $n_i$ 是 $n_{i+1}$ 的父亲。这个路径的长（length）为该路径上的边的条数，即 $k-1$ 。从每一个节点到它自己都有一条长为 $0$ 的路径。从根到每个节点有且仅有一条路径。

深度

对于任意节点 $n_i$ ， $n_i$ 的深度（depth）为从根到 $n_i$ 的唯一路径的长。因此，根的深度为 $0$ 。

高度

$n_i$ 的高（height）是从 $n_i$ 到一片树叶的最长路径的长。因此，所有树叶的高度都是 $0$ 。

祖先（ancestor）和后裔（descendant）

如果存在从 $n_1$ 到 $n_2$ 的一条路径，那么 $n_1$ 是 $n_2$ 的一位祖先而 $n_2$ 是 $n_1$ 的一个后裔。如果 $n_1 \ne n_2$ ，那么 $n_1$ 是 $n_2$ 的一位真祖先（proper ancestor）而 $n_2$ 是 $n_1$ 的一个真后裔（proper descendant）。

树的实现

将每个节点的所有儿子都放在树节点的链表中。FirstChild 是指向第一个儿子的指针，NextSibling 指向下一个兄弟节点。

typedef struct TreeNode *PtrToNode;

struct TreeNode
{
    ElementType Element;
    PtrToNode FirstChild;
    PtrToNode NextSibling;
}

树的遍历

先序遍历（preorder traversal）

在先序遍历中，对节点的处理工作是在它的诸儿子节点被处理之前进行的。例如：打印目录树形结构图，先打印父节点，再递归打印子节点。

后序遍历（postorder traversal）

在后序遍历中，在一个节点处的工作是在它的诸儿子节点被计算后进行的。例如：计算目录所占磁盘空间，在得到父节点占用空间前，需要先递归计算子节点所占用的磁盘空间，最后才能逐级向上得到根节点的磁盘总占用空间。

中序遍历（inorder traversal）

用于二叉树。遍历顺序：左子树，节点，右子树。

二叉树（binary tree）

在二叉树中，每个节点最多只有两个儿子。

二叉树的平均深度为 $O(\sqrt{N})$ ，而对于特殊类型的二叉树，如二叉查找树（binary search tree）,其平均深度是 $O(log N)$ 。

二叉树实现

因为一棵二叉树最多有两个儿子，所以我们可以用指针直接指向它们。树节点的声明在结构上类似于双链表的声明。在声明中，一个节点就是由Key信息加上两个指向其他节点的指针（Left 和　Right）组成的结构。

typedef struct TreeNode *PtrToNode;
typedef struct PtrToNode Tree;

struct TreeNode
{
    ElementType Element;
    Tree Left;
    Tree Right;
}

二叉树有许多与搜索无关的重要应用。二叉树的主要用处之一是在编译器的设计领域。如二元表达式树。

查找树ADT——二叉查找树

二叉树的一个重要的应用是它们在查找中的使用。使二叉树成为二叉查找树的性质是，对于树中的每个节点 $X$ ，它的左子树所有关键字的值小于 $X$ ，而它右子树中所有关键字值大于 $X$ 的关键字值。

操作集合：

MakeEmpty
Find
FindMin 和 FindMax
Insert
Delete

AVL 树

AVL（Adelson-Velskii 和 Landis）树是带有平衡条件的二叉查找树。这个平衡条件必须要容易保持，而且它必须保证树的深度是 $O(log N)$ 。最简单的想法是要求左右子树具有相同的高度。另一种平衡条件是要求每个节点都必须要有相同高度的左子树和右子树。虽然这种平衡条件保证了树的深度小，但是它太严格，难以使用，需要放宽条件。

一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树。

单旋转

双旋转

伸展树（splay tree）

伸展树保证从空树开始任意连续 $M$ 次对树的操作最多花费 $O(M log N)$ 的时间。

B-树

虽然迄今为止我们所看到的查找树都是二叉树，但是还有一种常用的查找树不是二叉树。这种树叫做B-树（B-tree）。

阶为 $M$ 的B-树是一棵具有下列结构特性的树：

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

B-树实际用于数据库系统，在那里树被存储在物理的磁盘上而不是主存中。一般来说，对磁盘的访问要比任何的主存操作慢几个数量级。如果我们使用M阶B-树，那么磁盘访问的次数是 $O(log_{M}N)$