常见基本数据结构——树，⼆叉树，⼆叉查树，AVL树
常见数据结构——树
处理⼤量的数据时，链表的线性时间太慢了，不宜使⽤。在树的数据结构中，其⼤部分的运⾏时间平均为O(logN)。并且通过对树结构的修改，我们能够保证它的最坏情形下上述的时间界。
树的定义有很多种⽅式。定义树的⾃然的⽅式是递归的⽅式。⼀棵树是⼀些节点的集合，这个集合可以是空集，若⾮空集，则⼀棵树是由根节点r以及0个或多个⾮空⼦树T1,T2,T3,......,Tk组成，这些⼦树中每⼀棵的根都有来⾃根r的⼀条有向的边所连接。
从递归的定义中，我们发现⼀棵树是N个节点和N-1条边组成的，每⼀个节点都有⼀条边连接⽗节点，但是根节点除外。
具有相同⽗亲的节点为兄弟，类似的⽅法可以定义祖⽗和孙⼦的关系。二叉树中序遍历非递归算法
从节点n1到nk的路径定义为节点n1，n2，...，nk的⼀个序列，并且ni是ni+1的⽗亲。这个路径的长是路径上的边数，即k-1。每个节点到⾃⼰有⼀条长为0的路径。⼀棵树从根到叶⼦节点恰好存在⼀条路径。
对于任意的节点ni，ni的深度为从根到ni的唯⼀路径长。ni的⾼是从ni到⼀⽚叶⼦的最长路径的长。因此，
所有的树叶的⾼度都是0，⼀棵树的⾼等于它的根节点的⾼。⼀棵树的深度总是等于它最深叶⼦的深度；该深度等于这棵树的⾼度。
树的实现
实现树的⼀种⽅法可以是在每⼀个节点除数据外还要有⼀些指针，使得该节点的每⼀个⼉⼦都有⼀个指针指向它。但是由于每个节点的⼉⼦树可以变化很⼤⽽且事先不知道，故在各个节点建⽴⼦节点的链接是不可⾏的，这样将会浪费⼤量的空间。
实际的做法很简单：将每个节点的所有⼉⼦都放在树节点的链表中。下⾯是典型的声明：
typedef struct TreeNode *PtrToNode
struct TreeNode{
  ElementType Element;
  PtrToNode FirstChild;
  PtrToNode NextSibling
}
下⾯是⼉⼦兄弟表⽰法的图⽰：
树的遍历及应⽤
⼀个常见的使⽤是操作系统中的⽬录结构。unix中的⽬录就是含有它的所有⼉⼦的⼀个⽂件，下⾯是⼀个打印⽬录的例⼦，输出的格式是：深度为di的⽂件的名字将被di次跳格tab后缩进：
static void
ListDir(DictoryOrFile D, int Depth){
  if(D is a legitimate entry){
    PrintName(D, Depth);
  if(D is a directory)
    for each childm C, of D
      ListDir(C, Depth + 1);
  }
}
void
ListDirectory(DirectoryOrFile D){
  ListDie(D, 0);
}
上述的遍历策略叫做先序遍历。在先序遍历中，对节点的处理⼯作是在他的诸⼦节点被处理之前进⾏的。
另⼀种遍历树的⽅法是后序遍历。在后序遍历中，每⼀个节点处理的⼯作是在他的诸⼦⼉⼦节点计算之后进⾏的。
记录⼀个⽬录⼤⼩的例程
static void SizeDirectory(Directory D){
  int TotalSize=0;
  if(D is a legitimate entry){
    for each child, C of D:
      TotalSize +=SizeDirectory(C);
  }
  return TotalSize;
}
⼆叉树
⼆叉树是⼀种树，他的每个节点都不能有多于两个的⼉⼦。⼆叉树的⼀个性质是平均⼆叉树的深度要⽐N⼩的多，分析表明平均的深度为
O(sqrt(N))，⽽对于特殊的⼆叉树⽽⾔，其深度的平均值是O(logN)的。
对于⼆叉树的实现，最多有两个⼉⼦，我们可以⽤指针直接指向它们。在声明中，⼀个节点就是由Key(关键字)信息加上两个指向其他节点的指针组成的结构。
typedef struct TreeNode *PtrToNode;
typedef struct PtrToNode Tree;
struct TreeNode{
  ElementType Element;
  Tree Left;
  Tree Right;
};
⼆叉树上就是图，在画⼆叉树的时候，我们⼀般不会画出NULL指针，因为具有N个节点的每⼀棵⼆叉树都将需要N+1个NULL指针。⼆叉树有许多与搜索⽆关的重要应⽤。⼆叉树的重要⽤处之⼀是在编译器的设计原则领域。
表达式树
下⾯是⼀个表达式树的例⼦：
表达式树的树叶是操作数，⽐如常数或者变量，⽽其他的节点为操作符。由于这⾥所有操作都是⼆元的，因此这棵特定的树正好是⼆叉树。有的节点也有可能只有⼀个⼉⼦，如具有⼀⽬的减运算符的情形。在上⾯的树中，左⼦树的值是a+(b*c)，右⼦树的值是((d*e)+f)*g，整棵树的表⽰(a+(b*c))+(((d*e)+f)*g)。
对于上⾯的⼆叉树，我们可以通过递归产⽣⼀个带括号的左表⽰式，然后打印出在根处的运算符，最后在递归的产⽣⼀个带括号的右表达式进⽽得到⼀个中缀表达式。这样⼀般的⽅法称为中缀表达式，由于其产⽣的表达式类型，这种遍历很容易记住。
我们也可以通过后序遍历的⽅式，得到表达式的后缀表达式。
构造⼀颗表达式树
下⾯我们给出⼀种算法，来把表达式的后缀表⽰转化为表达式树。对于将中缀表达式转换为后缀表达式的算法，我们可以通过栈进⾏实现。对于构建表达式树的算法：我们⼀次⼀个符号的读⼊表达式，如果符号是操作数，那么我们就建⽴⼀个单节点数并将⼀个指向它的指针推⼊栈，如果符号是操作符，那么我们就从栈中弹出指向两棵树T1和T2的那两个指针并形成⼀颗新的数，该树的根就是操作符，它的左，右⼉⼦分别指向T2和T1。然后将指向这棵树的指针压⼊栈中。
查树ADT——⼆叉查树
⼆叉树的⼀个重要的应⽤就是查。假设树中的每个节点被指定⼀个关键字值。在我们的例⼦中，虽然任意复杂的关键字都是可以的，但是为了简单起见，假设它们都是整数。我们还将假设，所有字是互异的，后⾯再处理重复的情况。
使得⼆叉树成为⼆叉查树的性质是：对于树中的每个节点X，它的左⼦树中所有关键字值都⼩于X的关键字值，⽽它的右⼦树中所有关键字值⼤于X的关键字值。
⼆叉查树的平均深度是O(logN)。
⼆叉查树的声明和MakeEmpty
struct TreeNode
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;
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
find操作⼀般是需要返回具有关键字节点的指针，如果节点不存在则返回NULL。如果T为NULL，那么我们就返回NULL。否则，如果存储在T中的关键字是X，则返回T。否则，我们递归的调⽤遍历左⼦树或者右⼦树，这取决于当前节点和X之间的关系。
下⾯的代码是通过递归进⾏实现的，我们发现函数中的两次递归都是尾递归，很明显可以通过goto进⾏实现。但是在这⾥进⾏尾递归也是合理的，降低速度换的代码的简明性，并且使⽤得栈空间也是O(logN)。
Position
Find(ElementType X, SearchTree T){
  if(T == NULL)
    return NULL;
  if(X < T->Element){
    Find(X, T->Left);
  }else if(X > T->Element){
    Find(X, T->Right);
  }else{
    return T;
  }
}
FindMin 和 FindMax
这些例程分别是返回树中最⼩值和最⼤值的位置。返回这些元素的准确值似乎更合理，但是这将与Find操作不相容。FindMin操作只需要从根节点开始不断向左进⾏，终⽌点就是最⼩值。FindMax操作则是相反即可。
下⾯分别使⽤递归和⾮递归编写实现：
递归实现FindMin：
Position
FindMin(SearchTree T){
  if(T == NULL)
    return NULL;
  else if(T->Left == NULL)
    return T;
  else
    return FindMin(T->Left);
}
FindMax的⾮递归操作
Position
FindMax(SearchTree T){
  if(T != NULL)
    while(T->Right != NULL)
      T = T->Right;
  return T；
}
Insert进⾏操作在例程上⾯是简单的，为了将X插⼊树中，我们可以像⽤Find那样沿着树进⾏查。如果到X，则什么也不做(或做⼀些更新)。否则，将X插⼊到遍历路径上⾯的最后⼀点。
重复元的插⼊可以通过在节点记录中保留⼀个附加于以指⽰发⽣的频率处理，不过这将会使得树整体空间增加，但是却⽐将重复信息放到树中要好(它将使树的深度增加)。当然，如果关键字只是⼀个更⼤结构的⼀部分，那么这种⽅法⾏不通。此时我们可以把具有相同关键字的所有结构保留在⼀个辅助数据结构中，如表或者另⼀颗查树中。
下⾯是插⼊例程代码：
SearchTree
Insert(ElementType X, SearchTree T){
  if(T == NULL){
    T = malloc(sizeof(struct TreeNode));
    T->Element = X;
    T->Left = T->Right = NULL;
  }else if(X < T->Element){
    T->Left = Insert(X, T->Left);
  }else if(X > T->Element){
    T->Right = Insert(X, T->Right);
  }
  return T;
}
Delete操作
就像许多数据结构⼀样，最困难的操作删除。⼀旦发现要删除节点，我们需要考虑⼏种可能的情况。
如果节点是⼀⽚树叶，那么它可以被⽴即删除。如果节点有⼀个⼉⼦，则该节点可以在其⽗节点调整指针绕过该节点后删除(为了清楚起见，下⾯给出⽰意图)
复杂的情况是处理具有两个⼉⼦的节点。⼀般的删除策略是⽤其右⼦树的最⼩数据代替该节点的数据并且递归删除那个节点。因为右⼦树的最⼩节点不可能有左⼉⼦，所以第⼆次删除要更容易。下⾯是删除的⽰意图：
上⾯所⽰的程序完成的效率不⾼，因为它沿着该树进⾏了两趟搜索来查和删除右⼦树最⼩的节点。可以写⼀个DeleteMin函数来进⾏改变效率。
如果删除次数不多，则通常使⽤的策略是懒惰删除，但⼀个元素要被删除时，它会仍然留在树中，⽽是只做⼀个被删除的记号。这种做法特别是在有重复关键字时很流⾏，因为此时记录出现的频数的域可以减1。如果树中实际节点数和被删除节点数相同，那么树的深度预计只上升⼀个⼩的常数。因此，存在⼀个与懒惰删除相关的⾮常⼩的时间损耗。再有，如果被删除的关键字要重新插⼊，就可以避免分配空间的消耗。
平均情形分析
直观上，除MakeEmpty外，我们期望前⼀节所有操作都花费O(logN)时间，因为我们⽤常数时间在树中降低了⼀层，这样⼀来，对树的操作⼤致减少⼀半左右。因此，除了MakeEmpty外，所有操作都是O(d)，其中d是包含说访问的关键字的节点深度。
SeachTree Delete(ElementType X, SearchTree T){
  Position TmpCell;
  if(T == NULL)
    Error();
  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){
    TmpCell = FindMin(T->Right);
    T->Element = TmpCell->Element;
    T->Right = Delete(T->Element, T->Right);
  }else{
    TmpCell = T;
    if(T->Left == NULL)
      T = T->Right;
    else if(T->Right == NULL)
      T = T->Left;
    free(TmpCell);
  }
  return T;
}
下⾯要证明，假设所有的树出现的机会均等，则树的所有节点的平均深度为O(logN)。
⼀棵树的所有节点的深度的和称为内部路径长。我们现在将要计算⼆叉查树平均内部路径长，其中的平均是对向⼆叉查树中所有可能的插⼊序列进⾏的。
令D(N)是具有N个节点的某棵树T的内部路径长，D(1)=0。⼀棵N节点树是由⼀棵i节点左⼦树和⼀棵(N-i-1)节点右⼦树以及深度为0的⼀个根节点组成的，其中0<=i<N，D(i)为根的左⼦树的内部路径长。但是在原树中，所有这些节点都要加深⼀度。同样的结论对于右⼦树也是成⽴的。因此我们得到递归关系：
D(N) = D(i) + D(N - i - 1) + N - 1
如果所有的⼦树的⼤⼩都是等可能出现，这对于⼆叉查树是成⽴的(因为⼦树的⼤⼩只依赖于第⼀个插⼊树中的元素的相对的秩)，但是对于⼆叉树不成⽴。那么，D(i)和D(N-i-1)的平均值都是：
通过求解这个递归关系，得到平均值为D(N)=O(NlogN)。因此任意节点的期望深度为O(logN)。
但是，上来就断⾔这个结果并不意味着上⼀节讨论的所有操作的平均运⾏时间是O(logN)并不完全正确。原因就在于删除操作，我们并不清楚是否所有的⼆叉查树都是等可能的出现的。
特别的，上⾯描述的删除算法有助于左⼦树⽐右⼦树深，因为我们总是⽤右⼦树的⼀个节点来代替删除的节点。已经证明，我们在交替插⼊和删除⼤量次数之后，树的期望深度将会变成O(sqrt(N))，树会变得明显的不平衡。
在删除的操作中，我们可以通过随机选取右⼦树的最⼩元素或左⼦树的最⼤元素来代替被删除的元素以消除这种不平衡。这样能够明显的消除树的偏向并使树保持平衡。
在没有删除或是使⽤懒惰删除的情况下，可以证明所有的⼆叉查树都是等可能的，所以可以断⾔：上述的操作都是O(logN)的时间复杂度。
另外⽐较新的⽅法是放弃平衡条件，允许树有任意的深度，但是每次操作时候使⽤⼀个规则进⾏调整，使得后⾯的操作效率更⾼。
AVL树
AVL树是带有平衡条件的⼆叉查树。这个平衡条件必须容易保持，⽽且能够保证树的深度是O(logN)。最简单的想法是要求左右⼦树具有相同的⾼度。
另⼀种平衡条件是要求每个节点都必须要有相同⾼度的左右⼦树。这个平衡条件虽然保证树的深度⼩，但是太过于严格，难以使⽤。
AVL树是其每个节点的左⼦树和右⼦树的⾼度最多差1的⼆叉查树。(空树的⾼度定义为-1)。⼀颗AVL树的⾼度最多是1.44log(N+2)-
1.328，但是实际上⾼度只是⽐logN稍微多⼀点点。
在⾼度为h的AVL树中，最少节点数S(h)由S(h)=S(h-1)+S(h-2)+1给出。对于h=0，S(h)=1;h=1,S(h)=2。函数S(h)与斐波那契密切相关，由此推出上⾯的AVL树的⾼度的界。
当进⾏插⼊时，我们需要更新通向根节点路径上⾯的那些节点的所有平衡信息，插⼊操作的困难在于，插⼊⼀个节点可能会破坏AVL树的特性。发⽣这种情况，就需要对树进⾏恢复以后才算完成插⼊操作。事实上，可以通过对树进⾏旋转来完成。
插⼊节点以后，只有从插⼊点到根节点的路径上的节点的平衡可能改变，因为只有这些节点的⼦树可能发⽣变化。当我们沿路径上⾏到根并且更新节点平衡信息时，我们可以到⼀个节点，它的平衡破坏了AVL条件。我们将指出如何在第⼀个这样的节点重新平衡这个树，并证明，这⼀重新平衡保证整个书满⾜AVL特性。
如果把重新平衡的节点叫做a。由于任意节点最多有两个⼉⼦，因此⾼度不平衡时，a点的两棵⼦树的⾼度差2，易知，不平衡出现在下⾯的四种情况中：
1.对a的左⼉⼦的左⼦树进⾏⼀次插⼊
2.对a的左⼉⼦的右⼦树进⾏⼀次插⼊
3.对a的右⼉⼦的左⼦树进⾏⼀次插⼊
4.对a的右⼉⼦的右⼦树进⾏⼀次插⼊
情况1和4是关于a点的镜像对称，2和3是关于a点的镜像对称。
第⼀种情况是插⼊发⽣在外边，即左-左或右-右的情况，该情况通过对树进⾏⼀次单旋转⽽完成调整。第⼆种情况是发⽣在内部的情形，即左-右或者右-左的情况，该情况会稍微复杂⼀些通过双旋转进⾏调整。
双旋转
对于右左插⼊或者左右插⼊的情况，是⽆法通过单旋转进⾏解决的，需要进⾏双旋转来解决。
现在让我们对上⾯的讨论做个总结。除⼏种情形外，为将关键字X插⼊⼀颗AVL树中，我们递归的将X插⼊到T对应的树中。如果TLR的⾼度不变，那么就插⼊完成。否则，如果在T中出现不平衡，那么我们根据X以及T和TLR中的关键字做适当的单旋转或者双旋转，更新这些⾼度，并解决好与树的其余部分的连接，从⽽完成⼀次插⼊。
另⼀种效率问题设计到⾼度的存储。真正需要存储的是⼦树的⾼度，应该保证它很⼩，我们可以⽤两个⼆进制位来进⾏存储。
struct AvlNode;
typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;
struct AvlNode{
  ElementType Element;
  AvlTree Left;
  AvlTree Right;
  int Height;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。