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 )
{
 
ifnull == t ){
  t 
= ( AvlTree )malloc( sizeofstruct AvlNode ) );
  
ifnull == 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 );
   
if2 == 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 );
    
if2 == 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