平衡二叉樹又稱AVL樹

性質(zhì)：

它或者是顆空樹，或者是具有下列性質(zhì)的二叉樹：

• 它的左子樹和右子樹都是平衡二叉樹姑蓝，且左子樹和右子樹的深度之差的絕對值不超過1。
• 若將二叉樹節(jié)點的平衡因子BF定義為該節(jié)點的左子樹的深度減去它的右子樹的深度熬甫，則平衡二叉樹上所有節(jié)點的平衡因子只可能為-1,0,1.
• 只要二叉樹上有一個節(jié)點的平衡因子的絕對值大于1诗舰，那么這顆平衡二叉樹就失去了平衡。

a:平衡二叉樹 b:不平衡二叉樹

為什么需要平衡二叉樹竿奏？

一種極端的情況：二叉搜索樹的結(jié)點為1袄简、2、3泛啸、4绿语、5，也就是：

退化成鏈表

查找一個節(jié)點的時間復(fù)雜度是O（n）平痰。
為了避免這種情況的發(fā)生汞舱，我們希望可以有一種算法伍纫，將我們的不平衡的二叉排序樹轉(zhuǎn)化為平衡二叉排序樹（AVL樹的查找平均復(fù)雜度是O（log(n)））這樣就可以讓我們的二叉排序樹結(jié)構(gòu)最優(yōu)化宗雇。

平衡二叉樹的算法

看到上述例子，我們就慢慢有點感覺了莹规，至少知道了為什么會需要平衡二叉樹赔蒲，接下來我們看一下平衡二叉樹是怎樣將我們不平衡的樹轉(zhuǎn)換為平衡二叉樹。
如何時構(gòu)成的二叉排序樹編程平衡二叉樹呢？先看一個具體的例子

平衡二叉樹過程

• 圖a 一顆空樹也算是平衡二叉樹
• 圖b 只有一個結(jié)點13的樹也算是平衡二叉樹
• 圖c 在圖b的基礎(chǔ)上插入新的結(jié)點24之后舞虱，仍然是平衡二叉樹欢际，只是根結(jié)點的平衡因子從0變到了-1（左子樹的深度為0減去右子樹的深度1等于-1）
• 圖d 在圖c的基礎(chǔ)上再插入一個結(jié)點37，這個時候整棵樹出現(xiàn)了不平衡現(xiàn)象矾兜，根結(jié)點13的平衡因子從-1變成了-2损趋。我們想要讓這課樹平衡，而且要保證該樹二叉排序樹的性質(zhì)椅寺，那么我們只要將根結(jié)點13換為24浑槽，結(jié)點13作為結(jié)點24的左子樹，這棵樹就又會回到平衡狀態(tài)返帕。
• 圖e桐玻。我們把這種對樹做向左逆時針“旋轉(zhuǎn)”的操作稱為單向左旋平衡處理。左旋之后荆萤，我們發(fā)現(xiàn)13镊靴、24、37結(jié)點的平衡因子都變?yōu)?链韭。而且仍然保持著二叉排序樹的特性
• 圖f當(dāng)我們繼續(xù)插入結(jié)點90之后偏竟，二叉樹仍然平衡，只是24敞峭、37兩個結(jié)點的平衡因子變?yōu)榱?1苫耸，再次插入53結(jié)點之后，結(jié)點37的平衡因子BF由-1變?yōu)?2儡陨，這意味著該排序樹中出現(xiàn)了新的不平衡現(xiàn)象褪子，需要進行調(diào)整。但此時由于結(jié)點53插在結(jié)點90的左子樹上骗村，因此不能如上面一樣作簡單的調(diào)整嫌褪。對于以上結(jié)點37為根的子樹來說，既要保持二叉排序樹的特性胚股，又要平衡笼痛，則必須以53結(jié)點作為根結(jié)點，而使37結(jié)點成為它左子樹的根琅拌，90結(jié)點稱為它右子樹的根缨伊。這就好比做了兩次旋轉(zhuǎn)，首先我們讓37进宝、53刻坊、90這棵樹單先向右順時針轉(zhuǎn)變成圖g，再像左逆時針變成圖h党晋，這樣我們的二叉樹就能夠再次回到平衡狀態(tài)谭胚。對于以上旋轉(zhuǎn)操作我們稱為雙向旋轉(zhuǎn)（先右后左）平衡處理

平衡算法總結(jié)

看完了上面的例子徐块，我們總結(jié)一下二叉排序樹的不平衡情況以及如何將其轉(zhuǎn)化為平衡情況。
一般情況下灾而，假設(shè)由于在二叉排序樹上插入結(jié)點而失去平衡的最小子樹根結(jié)點的指針為a（即a是離插入結(jié)點最近胡控，且平衡因子絕對值不超過1的祖先結(jié)點），則失去平衡后進行調(diào)整的規(guī)律可以歸納為一下4種情況：
1旁趟、單向右旋平衡處理：由于在a的左子樹根結(jié)點的左子樹上插入結(jié)點昼激，a的平衡因子由1增加到2，致使以a為根結(jié)點的子樹失去平衡锡搜，則需要進行一次右向順時針旋轉(zhuǎn)操作癣猾。簡稱LL型旋轉(zhuǎn)

左左型

右右型

左右型

右左型

總結(jié)圖

image

左旋右旋

 #include "stdio.h"
 #include "stdlib.h"
 #include "io.h"
 #include "math.h"
 #include "time.h"
 
 
 #define OK 1
 #define ERROR 0
 #define TRUE 1
 #define FALSE 0
 #define MAXSIZE 100 /* 存儲空間初始分配量 */
 
 typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */
 
 
/* 二叉樹的二叉鏈表結(jié)點結(jié)構(gòu)定義 */
 
 typedef  struct BiTNode /* 結(jié)點結(jié)構(gòu) */
 {
     int data;   /* 結(jié)點數(shù)據(jù) */
     int bf; /*  結(jié)點的平衡因子 */
     struct BiTNode *lchild, *rchild;    /* 左右孩子指針 */
 } BiTNode, *BiTree;
 
 
 
 
 /* 對以p為根的二叉排序樹作右旋處理行疏， */
 /* 處理之后p指向新的樹根結(jié)點匆光，即旋轉(zhuǎn)處理之前的左子樹的根結(jié)點 */
 
 void R_Rotate(BiTree *P)
 {
    BiTree L;
    L = (*P)->lchild; /*  L指向P的左子樹根結(jié)點 */
    (*P)->lchild = L->rchild; /*  L的右子樹掛接為P的左子樹 */
    L->rchild = (*P);
    *P = L; /*  P指向新的根結(jié)點 */
 }
 
 
 
 /* 對以P為根的二叉排序樹作左旋處理， */
 
 /* 處理之后P指向新的樹根結(jié)點酿联，即旋轉(zhuǎn)處理之前的右子樹的根結(jié)點0  */
 
 void L_Rotate(BiTree *P)
 {
     BiTree R;
     R = (*P)->rchild; /*  R指向P的右子樹根結(jié)點 */
     (*P)->rchild = R->lchild; /* R的左子樹掛接為P的右子樹 */
     R->lchild = (*P);
     *P = R; /*  P指向新的根結(jié)點 */
 }
 
 
 #define LH + 1 /*  左高 */
 #define EH 0  /*  等高 */
 #define RH - 1 /*  右高 */
 
 
/*  對以指針T所指結(jié)點為根的二叉樹作左平衡旋轉(zhuǎn)處理 */
 
 /*  本算法結(jié)束時终息，指針T指向新的根結(jié)點 */
 void LeftBalance(BiTree *T)
 {
     BiTree L, Lr;
     L = (*T)->lchild; /*  L指向T的左子樹根結(jié)點 */
     switch (L->bf)
    { /*  檢查T的左子樹的平衡度，并作相應(yīng)平衡處理 */
          case LH: /*  新結(jié)點插入在T的左孩子的左子樹上贞让，要作單右旋處理 */
              (*T)->bf = L->bf = EH;
              R_Rotate(T);
           break;
          case RH: /*  新結(jié)點插入在T的左孩子的右子樹上周崭，要作雙旋處理 */
             Lr = L->rchild; /*  Lr指向T的左孩子的右子樹根 */
            switch (Lr->bf)
             { /*  修改T及其左孩子的平衡因子 */
                case LH: (*T)->bf = RH;
                        L->bf = EH;
                         break;
                case EH: (*T)->bf = L->bf = EH;
                         break;
                case RH: (*T)->bf = EH;
                         L->bf = LH;
                          break;
            }
             Lr->bf = EH;
             L_Rotate(&(*T)->lchild); /*  對T的左子樹作左旋平衡處理 */
             R_Rotate(T); /*  對T作右旋平衡處理 */
     }
 }
 
/*  對以指針T所指結(jié)點為根的二叉樹作右平衡旋轉(zhuǎn)處理， */
 /*  本算法結(jié)束時喳张，指針T指向新的根結(jié)點 */
 void RightBalance(BiTree *T)
 {
     BiTree R, Rl;
     R = (*T)->rchild; /*  R指向T的右子樹根結(jié)點 */
     switch (R->bf)
     { /*  檢查T的右子樹的平衡度续镇，并作相應(yīng)平衡處理 */
      case RH: /*  新結(jié)點插入在T的右孩子的右子樹上，要作單左旋處理 */
               (*T)->bf = R->bf = EH;
              L_Rotate(T);
               break;
      case LH: /*  新結(jié)點插入在T的右孩子的左子樹上蹲姐，要作雙旋處理 */
              Rl = R->lchild; /*  Rl指向T的右孩子的左子樹根 */
              switch (Rl->bf)
              { /*  修改T及其右孩子的平衡因子 */
                case RH: (*T)->bf = LH;
                         R->bf = EH;
                         break;
                case EH: (*T)->bf = R->bf = EH;
                         break;
                 case LH: (*T)->bf = EH;
                          R->bf = RH;
                          break;
               }
               Rl->bf = EH;
               R_Rotate(&(*T)->rchild); /*  對T的右子樹作右旋平衡處理 */
               L_Rotate(T); /*  對T作左旋平衡處理 */
     }
 }
 
/*  若在平衡的二叉排序樹T中不存在和e有相同關(guān)鍵字的結(jié)點磨取，則插入一個 */
 /*  數(shù)據(jù)元素為e的新結(jié)點人柿，并返回1柴墩，否則返回0忙厌。若因插入而使二叉排序樹 */
 /*  失去平衡，則作平衡旋轉(zhuǎn)處理江咳，布爾變量taller反映T長高與否逢净。 */
 
 Status InsertAVL(BiTree *T, int e, Status *taller)
{
    if (!*T)
    { /*  插入新結(jié)點，樹“長高”歼指，置taller為TRUE */
         *T = (BiTree)malloc(sizeof(BiTNode));
         (*T)->data = e; (*T)->lchild = (*T)->rchild = NULL; (*T)->bf = EH;
          *taller = TRUE;
    }
    else
     {
        if (e == (*T)->data)
         { /*  樹中已存在和e有相同關(guān)鍵字的結(jié)點則不再插入 */
             *taller = FALSE; return FALSE;
         }
        if (e < (*T)->data)
         { /*  應(yīng)繼續(xù)在T的左子樹中進行搜索 */
             if (!InsertAVL(&(*T)->lchild, e, taller)) /*  未插入 */
                 return FALSE;
             if (*taller) /*   已插入到T的左子樹中且左子樹“長高” */
                switch ((*T)->bf) /*  檢查T的平衡度 */
                {
                    case LH: /*  原本左子樹比右子樹高爹土，需要作左平衡處理 */
                            LeftBalance(T); *taller = FALSE; break;
                    case EH: /*  原本左、右子樹等高踩身，現(xiàn)因左子樹增高而使樹增高 */
                            (*T)->bf = LH; *taller = TRUE; break;
                    case RH: /*  原本右子樹比左子樹高胀茵，現(xiàn)左、右子樹等高 */
                            (*T)->bf = EH; *taller = FALSE; break;
                }
         }
         else
        { /*  應(yīng)繼續(xù)在T的右子樹中進行搜索 */
            if (!InsertAVL(&(*T)->rchild, e, taller)) /*  未插入 */
                return FALSE;
             if (*taller) /*  已插入到T的右子樹且右子樹“長高” */
                 switch ((*T)->bf) /*  檢查T的平衡度 */
               {
                    case LH: /*  原本左子樹比右子樹高挟阻，現(xiàn)左琼娘、右子樹等高 */
                            (*T)->bf = EH; *taller = FALSE;  break;
                    case EH: /*  原本左、右子樹等高附鸽，現(xiàn)因右子樹增高而使樹增高  */
                             (*T)->bf = RH; *taller = TRUE; break;
                     case RH: /*  原本右子樹比左子樹高脱拼，需要作右平衡處理 */
                         RightBalance(T); *taller = FALSE; break;
               }
        }
    }
    return TRUE;
 }
 
 
int main(void)
 
{
     int i;
 
     int a[10] = { 3, 2, 1, 4, 5, 6, 7, 10, 9, 8 };
     BiTree T = NULL;
     Status taller;
     for (i = 0; i < 10; i++)
     {
         InsertAVL(&T, a[i], &taller);
     }
     printf("本樣例建議斷點跟蹤查看平衡二叉樹結(jié)構(gòu)");
     return 0;
 }