1、平衡二叉樹(shù)
它是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)?！?br />如圖：

2、動(dòng)態(tài)平衡技術(shù)
動(dòng)態(tài)平衡技術(shù)
Adelson-Velskii 和 Landis 提出了一個(gè)動(dòng)態(tài)地保持二叉排序樹(shù)平衡的方法，其基本思想是：
　　在構(gòu)造二叉排序樹(shù)的過(guò)程中，每當(dāng)插入一個(gè)結(jié)點(diǎn)時(shí)，首先檢查是否因插入而破壞了樹(shù)的平衡性，如果是因插入結(jié)點(diǎn)而破壞了樹(shù)的平衡性，則找出其中最小不平衡子樹(shù)，在保持排序樹(shù)特性的前提下，調(diào)整最小不平衡子樹(shù)中各結(jié)點(diǎn)之間的連接關(guān)系，以達(dá)到新的平衡。通常將這樣得到的平衡二叉排序樹(shù)簡(jiǎn)稱(chēng)為 AVL 樹(shù)。
那么什么是 最小不平衡子樹(shù)
　　以離插入結(jié)點(diǎn)最近、且平衡因子絕對(duì)值大于 1 的結(jié)點(diǎn)作根結(jié)點(diǎn)的子樹(shù)。為了簡(jiǎn)化討論，不妨假設(shè)二叉排序樹(shù)的最小不平衡子樹(shù)的根結(jié)點(diǎn)為 A ，則調(diào)整該子樹(shù)的規(guī)律可歸納為下列四種情況：
如圖：當(dāng)插入結(jié)點(diǎn)為53時(shí)，結(jié)點(diǎn)37則為最小不平衡子樹(shù) A
單向
（1） LL 型：（單向右旋）
原因是：在A的左子樹(shù)插入左子樹(shù)，導(dǎo)致A平衡恩子為2，失去平衡。需要向右旋轉(zhuǎn)一次、
　　新結(jié)點(diǎn) X 插在 A 的左孩子的左子樹(shù)里。調(diào)整方法見(jiàn)圖 8.5(a) 。圖中以 B 為軸心，將 A 結(jié)點(diǎn)從 B 的右上方轉(zhuǎn)到 B 的右下側(cè)，使 A 成為 B 的右孩子。


（2）RR 型：（單向向左旋）
同上。則是方向變了右
　　新結(jié)點(diǎn) X 插在 A 的右孩子的右子樹(shù)里。調(diào)整方法見(jiàn)圖 8.5(b) 。圖中以 B 為軸心，將 A 結(jié)點(diǎn)從 B 的左上方轉(zhuǎn)到 B 的左下側(cè)，使 A 成為 B 的左孩子。



雙向：
（3）LR 型：（先左后右）
　　新結(jié)點(diǎn) X 插在 A 的左孩子的右子樹(shù)里。調(diào)整方法見(jiàn)圖 8.5(c) 。分為兩步進(jìn)行：第一步以 X 為軸心，將 B 從 X 的左上方轉(zhuǎn)到 X 的左下側(cè)，使 B 成為 X 的左孩子， X 成為 A 的左孩子。第二步跟 LL 型一樣處理 ( 應(yīng)以 X 為軸心 ) 。 
//此時(shí)大小是 B<X<A 那么應(yīng)該將中間的那個(gè)X做根結(jié)點(diǎn)
（4）RL 型：（先右后左）
　　新結(jié)點(diǎn) X 插在 A 的右孩子的左子樹(shù)里。調(diào)整方法見(jiàn)圖 8.5(d) 。分為兩步進(jìn)行：第一步以 X 為軸心，將 B 從 X 的右上方轉(zhuǎn)到 X 的右下側(cè)，使 B 成為 X 的右孩子， X 成為 A 的右孩子。第二步跟 RR 型一樣處理 ( 應(yīng)以 X 為軸心

【例】
實(shí)際的插入情況，可能比圖 8.5 要復(fù)雜。因?yàn)?A 、 B 結(jié)點(diǎn)可能還會(huì)有子樹(shù)?，F(xiàn)舉一例說(shuō)明，設(shè)一組記錄的關(guān)鍵字按以下次序進(jìn)行插入： 4 、 5 、 7 ， 2 、 1 、 3 、 6 ，其生成及調(diào)整成二叉平衡樹(shù)的過(guò)程示于圖 8.6 。
　　在圖 8.6 中，當(dāng)插入關(guān)鍵字為 3 的結(jié)點(diǎn)后，由于離結(jié)點(diǎn) 3 最近的平衡因子為 2 的祖先是根結(jié)點(diǎn) 5 。所以，第一次旋轉(zhuǎn)應(yīng)以結(jié)點(diǎn) 4 為軸心，把結(jié)點(diǎn) 2 從結(jié)點(diǎn) 4 的左上方轉(zhuǎn)到左下側(cè)，從而結(jié)點(diǎn) 5 的左孩子是結(jié)點(diǎn) 4 ，結(jié)點(diǎn) 4 的左孩子是結(jié)點(diǎn) 2 ，原結(jié)點(diǎn) 4 的左孩子變成了結(jié)點(diǎn) 2 的右孩子。第二步再以結(jié)點(diǎn) 4 為軸心，按 LL 類(lèi)型進(jìn)行轉(zhuǎn)換。這種插入與調(diào)整平衡的方法可以編成算法和程序，這里就不再討論了。

         圖 8.6 二叉平衡樹(shù)插入結(jié)點(diǎn) ( 結(jié)點(diǎn)旁的數(shù)字為其平衡因子 )

代碼實(shí)

/*

    數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版平衡二叉樹(shù)

    P236

    編譯環(huán)境：Dev-C++ 4.9.9.2

    日期：2011年2月15日

*/

 

#include <stdio.h>

#include <malloc.h>

 

#define LH +1   // 左高

#define EH 0    // 等高

#define RH -1   // 右高

#define N 5     // 數(shù)據(jù)元素個(gè)數(shù)

 

typedef char KeyType; // 設(shè)關(guān)鍵字域?yàn)樽址?span lang="EN-US">

 

typedef struct

{

    KeyType key;

    int order;

}ElemType; // 數(shù)據(jù)元素類(lèi)型

 

// 平衡二叉樹(shù)的類(lèi)型

typedef struct BSTNode

{

    ElemType data;

    // bf結(jié)點(diǎn)的平衡因子,只能夠取0，-1，1，它是左子樹(shù)的深度減去

    // 右子樹(shù)的深度得到的

    int bf;

    struct BSTNode *lchild,*rchild; // 左、右孩子指針

}BSTNode,*BSTree;

 

// 構(gòu)造一個(gè)空的動(dòng)態(tài)查找表DT

int InitDSTable(BSTree *DT)

{

    *DT=NULL;

    return 1;

}

 

// 銷(xiāo)毀動(dòng)態(tài)查找表DT

void DestroyDSTable(BSTree *DT)

{

    if(*DT) // 非空樹(shù)

    {

        if((*DT)->lchild) // 有左孩子

            DestroyDSTable(&(*DT)->lchild); // 銷(xiāo)毀左孩子子樹(shù)

        if((*DT)->rchild) // 有右孩子

            DestroyDSTable(&(*DT)->rchild); // 銷(xiāo)毀右孩子子樹(shù)

        free(*DT); // 釋放根結(jié)點(diǎn)

        *DT=NULL; // 空指針賦0

    }

}

 

// 算法9.5(a) 

// 在根指針T所指二叉排序樹(shù)中遞歸地查找某關(guān)鍵字等于key的數(shù)據(jù)元素，

// 若查找成功，則返回指向該數(shù)據(jù)元素結(jié)點(diǎn)的指針,否則返回空指針。
//同二叉排序樹(shù)的查找算法

BSTree SearchBST(BSTree T,KeyType key)

{

    if((!T)|| (key == T->data.key))

        return T; // 查找結(jié)束

    else if(key < T->data.key) // 在左子樹(shù)中繼續(xù)查找

        return SearchBST(T->lchild,key);

    else

        return SearchBST(T->rchild,key); // 在右子樹(shù)中繼續(xù)查找

}

 

// 算法9.9 P236

// 對(duì)以*p為根的二叉排序樹(shù)作右旋處理 ，處理之后p指向新的樹(shù)根結(jié)點(diǎn)，即旋轉(zhuǎn)

// 處理之前的左子樹(shù)的根結(jié)點(diǎn)。

void R_Rotate(BSTree *p)

{

    BSTree lc;

    lc=(*p)->lchild; // lc指向p的左子樹(shù)根結(jié)點(diǎn)

    (*p)->lchild=lc->rchild; // lc的右子樹(shù)掛接為p的左子樹(shù)

    lc->rchild=*p;

    *p=lc; // p指向新的根結(jié)點(diǎn)

}

 

// 算法9.10  P236

// 對(duì)以*p為根的二叉排序樹(shù)作左旋處理 ，處理之后p指向新的樹(shù)根結(jié)點(diǎn)，即旋轉(zhuǎn)

// 處理之前的右子樹(shù)的根結(jié)點(diǎn)。

void L_Rotate(BSTree *p)

{

    BSTree rc;

    rc=(*p)->rchild; // rc指向p的右子樹(shù)根結(jié)點(diǎn)

    (*p)->rchild=rc->lchild; // rc的左子樹(shù)掛接為p的右子樹(shù)

    rc->lchild=*p;

    *p=rc; // p指向新的根結(jié)點(diǎn)

}

 

// 算法9.12 P238

// 對(duì)以指針T所指結(jié)點(diǎn)為根的二叉樹(shù)作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，

// 指針T指向新的根結(jié)點(diǎn)。

void LeftBalance(BSTree *T)

{  

    BSTree lc,rd;

    lc=(*T)->lchild; // lc指向*T的左子樹(shù)根結(jié)點(diǎn)

    switch(lc->bf)

    { // 檢查*T的左子樹(shù)的平衡度，并作相應(yīng)平衡處理

    case LH: // 新結(jié)點(diǎn)插入在*T的左孩子的左子樹(shù)上，要作單右旋處理

        (*T)->bf=lc->bf=EH;

        R_Rotate(T);

        break;

    case RH: // 新結(jié)點(diǎn)插入在*T的左孩子的右子樹(shù)上，要作雙旋處理

        rd=lc->rchild; // rd指向*T的左孩子的右子樹(shù)根

        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;

        }

        rd->bf=EH;

        L_Rotate(&(*T)->lchild); // 對(duì)*T的左子樹(shù)作左旋平衡處理

        R_Rotate(T); // 對(duì)*T作右旋平衡處理

    }

}

 

// 對(duì)以指針T所指結(jié)點(diǎn)為根的二叉樹(shù)作右平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，

// 指針T指向新的根結(jié)點(diǎn)

void RightBalance(BSTree *T)

{

    BSTree rc,rd;

    rc=(*T)->rchild; // rc指向*T的右子樹(shù)根結(jié)點(diǎn)

    switch(rc->bf)

    { // 檢查*T的右子樹(shù)的平衡度，并作相應(yīng)平衡處理

    case RH: // 新結(jié)點(diǎn)插入在*T的右孩子的右子樹(shù)上，要作單左旋處理

        (*T)->bf=rc->bf=EH;

        L_Rotate(T);

        break;

    case LH: // 新結(jié)點(diǎn)插入在*T的右孩子的左子樹(shù)上，要作雙旋處理

        rd=rc->lchild; // rd指向*T的右孩子的左子樹(shù)根

        switch(rd->bf)

        { // 修改*T及其右孩子的平衡因子

        case RH: (*T)->bf=LH;

            rc->bf=EH;

            break;

        case EH: (*T)->bf=rc->bf=EH;

            break;

        case LH: (*T)->bf=EH;

            rc->bf=RH;

        }

        rd->bf=EH;

        R_Rotate(&(*T)->rchild); // 對(duì)*T的右子樹(shù)作右旋平衡處理

        L_Rotate(T); // 對(duì)*T作左旋平衡處理

    }

}

 

// 算法9.11

// 若在平衡的二叉排序樹(shù)T中不存在和e有相同關(guān)鍵字的結(jié)點(diǎn)，則插入一個(gè)

// 數(shù)據(jù)元素為e的新結(jié)點(diǎn)，并返回1，否則返回0。若因插入而使二叉排序樹(shù)

// 失去平衡，則作平衡旋轉(zhuǎn)處理，布爾變量taller反映T長(zhǎng)高與否。

int InsertAVL(BSTree *T,ElemType e,int *taller)

{

    if(!*T)

    { // 插入新結(jié)點(diǎn)，樹(shù)“長(zhǎng)高”，置taller為1

        *T=(BSTree)malloc(sizeof(BSTNode));

        (*T)->data=e;

        (*T)->lchild=(*T)->rchild=NULL;

        (*T)->bf=EH;

        *taller=1;

    }

    else

    {

        if(e.key == (*T)->data.key)

        { // 樹(shù)中已存在和e有相同關(guān)鍵字的結(jié)點(diǎn)則不再插入

            *taller=0;

            return 0;

        }

        if(e.key < (*T)->data.key)

        { // 應(yīng)繼續(xù)在*T的左子樹(shù)中進(jìn)行搜索

            if(!InsertAVL(&(*T)->lchild,e,taller)) // 未插入

                return 0;

            if(*taller)

                //  已插入到*T的左子樹(shù)中且左子樹(shù)“長(zhǎng)高”

                switch((*T)->bf) // 檢查*T的平衡度

                {

                case LH:

                    // 原本左子樹(shù)比右子樹(shù)高，需要作左平衡處理

                    LeftBalance(T);

                    *taller=0;  //標(biāo)志沒(méi)長(zhǎng)高

                    break;

                case EH:

                    // 原本左、右子樹(shù)等高，現(xiàn)因左子樹(shù)增高而使樹(shù)增高

                    (*T)->bf=LH;

                    *taller=1;  //標(biāo)志長(zhǎng)高

                    break;

                case RH:

                    // 原本右子樹(shù)比左子樹(shù)高，現(xiàn)左、右子樹(shù)等高

                    (*T)->bf=EH;

                    *taller=0;  //標(biāo)志沒(méi)長(zhǎng)高

            }

        }

        else

        {

            // 應(yīng)繼續(xù)在*T的右子樹(shù)中進(jìn)行搜索

            if(!InsertAVL(&(*T)->rchild,e,taller)) // 未插入

                return 0;

            if(*taller) // 已插入到T的右子樹(shù)且右子樹(shù)“長(zhǎng)高”

                switch((*T)->bf) // 檢查T的平衡度

            {

           case LH:

               (*T)->bf=EH; // 原本左子樹(shù)比右子樹(shù)高，現(xiàn)左、右子樹(shù)等高

               *taller=0;

               break;

           case EH: // 原本左、右子樹(shù)等高，現(xiàn)因右子樹(shù)增高而使樹(shù)增高

               (*T)->bf=RH;

               *taller=1;

               break;

           case RH: // 原本右子樹(shù)比左子樹(shù)高，需要作右平衡處理

               RightBalance(T);

               *taller=0;

            }

        }

    }

    return 1;

}

 

// 按關(guān)鍵字的順序?qū)?span lang="EN-US">DT的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit()一次

void TraverseDSTable(BSTree DT,void(*Visit)(ElemType))

{

    if(DT)

    {

        TraverseDSTable(DT->lchild,Visit); // 先中序遍歷左子樹(shù)

        Visit(DT->data); // 再訪(fǎng)問(wèn)根結(jié)點(diǎn)

        TraverseDSTable(DT->rchild,Visit); // 最后中序遍歷右子樹(shù)

    }

}

 

 

void print(ElemType c)

{

    printf("(%d,%d)",c.key,c.order);

}

 
測(cè)試

int main()

{

    BSTree dt,p;

    int k;

    int i;

    KeyType j;

    ElemType r[N]={

        {13,1},{24,2},{37,3},{90,4},{53,5}

    }; // (以教科書(shū)P234圖9.12為例)

   

    InitDSTable(&dt);   // 初始化空樹(shù)

    for(i=0;i<N;i++)

        InsertAVL(&dt,r[i],&k); // 建平衡二叉樹(shù)

    TraverseDSTable(dt,print); // 按關(guān)鍵字順序遍歷二叉樹(shù)

    printf("\n請(qǐng)輸入待查找的關(guān)鍵字: ");

    scanf("%d",&j);

    p=SearchBST(dt,j); // 查找給定關(guān)鍵字的記錄

    if(p)

        print(p->data);

    else

        printf("表中不存在此值");

    printf("\n");

    DestroyDSTable(&dt);

   

    system("pause");

    return 0;

}

/*

輸出效果：

 

(13,1)(24,2)(37,3)(53,5)(90,4)

請(qǐng)輸入待查找的關(guān)鍵字: 53

(53,5)

請(qǐng)按任意鍵繼續(xù). . .。（參考）

/////////////////////////待續(xù)。