AVL树的旋转！
对于AVL树的旋转不是很明白，单旋转还好，双旋转就搞不懂什么规律了！高手们给说下规律吧，或贴个连接什么的！

[解决办法]
学习没有捷径, 靠自己努力. 要说规律的话, 观察左子树高度跟右子树高度差, 让树平衡, 仅此而已.
[解决办法]
增加和删除可能需要通过一次或多次树旋转来重新平衡这个树.
http://bbs.pfan.cn/post-206194-1.html

C/C++ code

 
 typedef struct BSTNode { 
   ElemType  data ; 
   int       bf ;     //结点的平衡因子 
   struct BSTNode *lchild , *rchild ;  //左、右孩子指针 
 }BSTNode , *BSTree ; 
  
 void R_Rotate (BSTree &p)  { 
   //对以*p为根的二叉排序树作右旋转处理，处理之后p指向新的树根结点，即旋转 
   //处理之前的左子树的根结点 
   lc=p->lchild ;      //lc指向的*p的左子树根结点 
   p->lchild=lc->rchild ;  //lc的右子树挂接为*p的左子树 
   lc->rchild=p ; p=lc ;  //p指向新的根结点 
 }// R_Rotate 
 void L_Rotate (BSTree &p)  { 
   //对以*p为根的二叉排序树作左旋处理，处理之后p指向新的树根结点，即旋转 
   //处理之前的右子树的根结点 
   rc=p->rchild ;      //rc指向的*p的右子树根结点 
   p->rchild=rc->lchild ;  //rc左子树挂接为*p的右子树 
   rc->lchild=p ; p=rc ;    //p指向新的根结点 
 }//L_Rotate 
  
 #define LH +1    //左高 
 #define EH 0    //等高 
 #define RH -1    //右高 
 Status InsertAVL (BSTree &T , ElemType e , Boolean &taller )  { 
   //若在平衡二叉排序树T中不存在和e有相同关键字的结点，则插入一个数据元素 
   //为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树失去平衡，则作平衡 
   //旋转处理，布尔变量taller反映T长高与否 
   if (!T)   {//插入新结点，树“长高”，置taller为TRUE 
     T=(BSTree)malloc(sizeof(BSTNode)); T->data=e ; 
     T->lchild=T->rchild=NULL; T->bf=EH ; taller = TRUE ; 
   } 
   else { 
     if (EQ(e.key , T->data.key))      //树中已存在和e有相同关键字的结点 
       { taller=FALSE ; return 0 ; }    //则不插入 
     if (LT(e.key , T->data.key))  {    //继续在*T的左子树中进行搜索 
       if (!InsertAVL(T->lchild , e , taller)) return 0;  //未插入 
       if (taller)          //已插入到*T的左子树中且左子树“长高” 
         switch ( T->bf )  {  //检查*T的平衡度 
           case LH:   //原本左子树比右子树高，需要作左平衡处理 
             LeftBalance(T) ; taller=FALSE ; break ; 
           case EH:    //原本左、右子树等高，现因左子树增高而使树增高 
             T->bf=LH ; taller=TRUE ; break ; 
           case RH:    //原本右子树比左子树高，现左、右子树等高 
             T->bf=EH ; taller=FALSE ; break ; 
         }//switch(T->bf) 
     }//if 
     else {            //继续在*T的左子树中进行搜索 
       if(!InsertAVL(T->rchild , e , taller)) return 0 ;  //未插入 
       if (taller)          //已插入到*T的右子树中且右子树“长高” 
         switch ( T->bf )  {  //检查*T的平衡度 
           case LH:   //原本左子树比右子树高，现左、右子树等高 
             T->bf=EH ; taller=FALSE ; break ; 
           case EH:    //原本左、右子树等高，现因右子树增高而使树增高 
             T->bf=RH ; taller=FALSE ; break ; 
           case RH:    //原本右子树比左子树高，需要作右平衡处理 
             RightBalance(T) ; taller=FALSE ; break ; 
         }//switch(T->bf) 
       }//else 
   }//else 
   return 1;  
 
 }//InsertAVL 
 void LeftBalance (BSTree &T)  { 
   //对以指针T所指结点为根的二叉树作左平衡旋转处理，本算法结束时，指针T指向 
   //新的根结点 
   lc=T->lchild ;      //lc指向*T的左子树根结点 
   switch (lc->bf)    {  //检查*T的左子树的平衡高度，并作相应平衡处理 
     case LH:      //新结点插入在*T的左孩子的左子树上，要作单右旋处理 
       T->bf=lc->bf=EH ; 
       R_Rotate(T); break ; 
     case RH:      //新结点插入在*T的左孩子的右子树上，要作双旋处理 
       rd=lc->rchild ;   //rd指向*T的左孩子的右子树根 
       switch (rd->bf)   {  //修改*T及其左孩子的平衡因子 
         case LH: T->bf=RH ; lc->bf=EH ; break ; 
         case EH: T->bf= lc->bf=EH ; break ; 
         case RH: T->bf=EH ; lc->bf=LH ; break ; 
       }// switch (rd->bf) 
       rd->bf=EH; 
       L_Rotate(T->lchild) ;    //对*T的左子树作左旋转处理 
       R_Rotate(T) ;        //对*T作右旋转处理 
   }// switch (lc->bf) 
 }//LeftBalance 
  
 

[解决办法]
http://www.hnrtu.com/luoyuhong/sjjg/xxjc/7-6.htm
这个讲的比较清楚
[解决办法]
自己画个图，有空我也来编写一个。
[解决办法]
本质就是2次旋转，否则怎么会叫双旋转捏?
就是儿子和父亲旋转，旋转后新的父亲再和祖父旋转