AVL树是最老的带有平衡条件的二叉查询树，高度严格控制为 s(h) = s(h-1)+s(h-2)+1。因此符合斐波那契数列，因此容易推出它的高度上界为 1.44log(N+2)-1.328。 ADT没有给出删除操作的调整操作，删除操作的代码量稍大，可以采用惰性操作。时刻保持更新的高度信息可以使树最多失衡2的高度差，并立即被调整。其中可能会涉及四种调整操作的情况：
  1. 向左儿子的左子树插入，向右单旋转
  2. 向右儿子的右子树插入，向左单旋转
  3. 向左儿子的右子树插入，双旋转.1
  4. 向右儿子的左子树插入，双旋转.2

  容易证明，1和2情况是镜像对称的；3和4同理，但编码时要仔细区分。



#ifndef // _AvlTree_H

struct Avlnod;
typedef struct Avlnod *Position;
typedef struct Avlnod *AvlTree;

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

struct AvlNode{
 ElementType ele;
 AvlTree left;
 AvlTree right;
 int height;
}:

AvlTree Insert( ElementType x, AvlTree t ){
 if( null == t ){
  t = ( AvlTree )malloc( sizeof( struct AvlNode ) );
  if( null == t ){
   printf(" error ");
  }
  else{
   t->ele = x; t->height = 0;
   t->left = null; t->right = null;
  }
 }
 else{
  if( x < t->ele ){
   t = Insert( x ,t->left );
   if( 2 == getHeight( t->left ) - getHeight( t->right )  ){
    if( x < t->left->ele ){
     t = SingleRoRight( t );
    }
    else{
     t = DoubleRoRight( t );
    }
   }
  }
  else
   if( x > t->ele ){
    t = Insert( x ,t->right );
    if( 2 == getHeight( t->right ) - getHeight( t->left )  ){
     if( x > t->right->ele ){
      t = SingleRouLeft( t );
     }
     else{
      t = DoubleRouLeft( t );
     }
    }
   }
 }
 t->height = max( getHeight( t->left ) ,getHeight( t->right ) )+1;
 return t;
}

AvlTree SingleRouRight( AvlTree root2 ){
 Position root1;
 root1 = root2->left;
 root2->left = root1->right;
 root1->right = root2;
 root2->height = max( getHeight( root2->left ) ,getHeight( root2->right ) )+1;
 root1->height = max( getHeight( root1->left ) ,getHeight( root1->right ) )+1;
 return root1;
}

AvlTree DoubleRouRight( AvlTree root3 ){
 Position rootTmp,root;
 rootTmp = root3->left;
 root3->left = SingleRouLeft( rootTmp );   // 左旋左子树
 root = SingleRouRight( root3 );  // 右旋整体
 return root;
}

AvlTree SingleRouLeft( AvlTree root1 ){
 Position root2;
 root2 = root1->right;
 root1->right = root2->left;
 root2->left = root1;
 root1->height = max( getHeight( root1->left ) ,getHeight( root1->right ) )+1;
 root2->height = max( getHeight( root2->left ) ,getHeight( root2->right ) )+1;
 return root2;
}

AvlTree DoubleRouLeft( AvlTree root3 ){
 Position rootTmp,root;
 rootTmp = root3->right;
 root3->right = SingleRouRight( rootTmp );   // 右旋右子树
 root = SingleRouLeft( root3 );  // 左旋整体
 return root;
}

#endif  // _AvlTree_H