AVL樹是最老的帶有平衡條件的二叉查詢樹，高度嚴格控制為 s(h) = s(h-1)+s(h-2)+1。因此符合斐波那契數(shù)列，因此容易推出它的高度上界為 1.44log(N+2)-1.328。 ADT沒有給出刪除操作的調整操作，刪除操作的代碼量稍大，可以采用惰性操作。時刻保持更新的高度信息可以使樹最多失衡2的高度差，并立即被調整。其中可能會涉及四種調整操作的情況：
  1. 向左兒子的左子樹插入，向右單旋轉
  2. 向右兒子的右子樹插入，向左單旋轉
  3. 向左兒子的右子樹插入，雙旋轉.1
  4. 向右兒子的左子樹插入，雙旋轉.2

  容易證明，1和2情況是鏡像對稱的；3和4同理，但編碼時要仔細區(qū)分。



#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