第100页 树

算法分析评估里面的N是代表输入数据的规模
对于大量数据的输入，链表的线性访问时间太慢，不宜使用。树这种数据结构的运行时间平均为O(log N)。树的一种自然的定义方式是递归方法。

具有相同父亲的节点为兄弟（sibling）.一个树的深度等于它的最深树叶的深度，该深度总是等于这棵树的高度。
树节点的定义：将灭个节点的所有儿子都放在树节点的链表中。


树的遍历和应用：
树有很多应用。最流行的用法之一就是UNIX,VAX/VMS和DOS在内常用操作系统的目录结构。严格来说UNIX文件系统不是树，是类树（treelike）。


二叉树：
二叉树(binary tree)是一棵树，其中每个节点都不能有多于两个的儿子。二叉树的一个性质是平均二叉树的深度要比N小得多，这个性质很重要。分析表明，这个平均深度为O(
\begin{equation}\sqrt{N}\end{equation}
)，而对于特殊类型的二叉树，即二叉查找树（binary search tree）,其平均深度为O(log N)。最坏情况深度达到N - 1。
二叉树有许多与搜索无关的重要应用。主要用途之一就是在编译器设计领域。

表达式树：
表达式树（expression tree）的树叶是操作数（operand，比如常量或变量，而其它的节点为操作符（operator））。


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

因为二叉查找树的平均深度为O(log N)，所以一般递归建树，不用担心栈空间被耗尽。

二叉查找树声明：
#ifndef _TREE_H

struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;

SearchTree MakeEmpty(SearchTree T);
Position Find(ElementType X, SearchTree T);
Position FindMin(SearchTree T);
Position FindMax(SearchTree T);
SearchTree Insert(ElementType X, SearchTree T);
SearchTree Delete(ElementType X, SearchTree T);
ElementType Retrieve(Position P);

#endif

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


建立一棵空树：
SearchTree MakeEmpty(SearchTree T)
{
    if(T != NULL)
    {
          MakeEmpty(T->Left);
          MakeEmpty(T->Right);
          free(T);
    }

    return NULL;
}


Find操作：
Position Find(ElementType X, SearchTree T)
{
     if(T == NULL)  return NULL;
     if(X < T -> Element)    return Find(X, T -> Left);
     else if(X > T->Element) return Find(X, T -> Right);
     else
       return T;
       
}


FindMin的递归实现：
Position FindMin(SearchTree T)
{
    if(T == NULL)    return NULL;
    else if(T -> Left == NULL )  return T;
    else
        return FindMin(T -> Left);
}

FinMax的非递归实现：
Position FindMax(SearchTree T)
{
    if(T != NULL)
      while(T -> Right != NULL)
      {
          T = T -> Right;
      }
      
     return T;
}


插入元素到二叉查找树：
SearchTree Insert(ElementType X, SearchTree T)
{
     if(T == NULL)   
     {
         T = malloc(sizeof(struct TreeNode));
          if(T == NUU)   Error("Out of space");
          else
          {
              T -> Element = X;
              T -> Left = T -> Right = NULL;
          }
     }
     else if(X < T -> Element)
     {
          T -> Left = Insert(X, T);
     }
     else if(X > T -> Element)
     {
           T -> Right = Insert(X, T);
     }
     
     return T;
}

二叉查找树的删除：
正如许多数据结构那样，最困难得是删除。如果删除次数不多，则通常使用的策略是懒惰删除（lazy Deletion）。当一个元素要被删除时，它仍然留在树中，而是只是做了个被删除的记号。

SearchTree Delete(ElementType X, SearchTree)
{
    Position TmpCell;
    
    if(T == NULL)
        Error("Element not Found");
    else if(X < T -> Element)
         T -> Left = Delete(X, T -> Left);
     else if(X > T -> Element)
        T -> Right = Delete(X, T -> Right);
     else if(T -> Left && T -> Right)  //Two Children
     {
           TmpCell = FindMin(T -> Right);
           T -> Element = TmpCell -> Element;
           T -> Right = Delete(T -> Element, T -> Right);
     }
     else   //One or Zero Children
     {
         TmpCell = T;
         if(T -> Left == NULL)
                 T = T -> Right;
         else if(T-> Right == NULL)
                 T = T -> Left;
         free(TmpCell);
     }
      
    return T;
}
一棵树的所有节点的深度的和称为内部路径长。


AVL树：
AVL树是带有平衡条件的二叉查找树。

B树：
一种常用的查找树（不是二叉树），叫B树。
阶为M的B树是一棵具有下列结构特性的树：
a.树的根或者是一片树叶，或者其儿子数在2和M之间。
b.根除外，所有非树叶节点的儿子树在[M/2]（向上取整）和M之间。
c.所有的树叶都在相同的深度上。


所有的数据都在树叶上。

B树实际用于数据库系统中，在那里的树被存储在物理磁盘上，而不是内存中


总结：
分析树是编译器设计的核心数据结构。分析树不是二叉树，而是表达式树相对简单的扩充。查找树的非递归实现多少要快一些。查找树的问题在于，其性能严重的依赖输入，而输入时随机的。如果情况不是这样，则运行时间会显著增加，查找树会成为昂贵的链表。