平衡二叉樹（AVL樹）

由于二叉查找樹有時候查找的復(fù)雜度達到O(n)，起不到使用二叉查找樹來進行數(shù)據(jù)查詢優(yōu)化的目的。于是需要對樹的結(jié)構(gòu)進行調(diào)整，使樹的高度在每次插入元素仍能保持O(logn)的級別，于是產(chǎn)生了平衡二叉樹
AVL樹仍然是一棵二叉查找樹，只是在其基礎(chǔ)上增加了“平衡”的要求。所謂平衡是指，對AVL樹的任意結(jié)點來說，其左子樹與右子樹的高度之差的絕對值不超過1，其中左子樹與右子樹的高度之差稱為該結(jié)點的平衡因子
只要能隨時保證每個結(jié)點平衡因子的絕對值不超過1，AVL的高度就始終能保持O(logn)級別。由于需要對每個結(jié)點都得到平衡因子，因此需要在樹的結(jié)構(gòu)中加入一個變量height，用來記錄以當(dāng)前結(jié)點為根結(jié)點的子樹的高度：

struct node {
    int v, height;  //v為結(jié)點權(quán)值，height為當(dāng)前子樹高度 
    node *left, *right;     //左右孩子結(jié)點地址 
}; 

新建結(jié)點

//生成一個新結(jié)點，v為結(jié)點權(quán)值
node* newNode(int v) {
    node* Node = new node;  //申請一個node型變量的地址空間
    Node->v = v;    //結(jié)點權(quán)值為v
    Node->height = 1;   //結(jié)點高度初始為1
    Node->lchild = Node->rchild = NULL; //初始狀態(tài)下沒有左右孩子
    return Node;        //返回新建結(jié)點的地址 
} 

獲取樹的高度height

//獲取以root為根結(jié)點的子樹的當(dāng)前height
int getHeight(node* root) {
    if(root == NULL) return 0;
    return root->height;
} 

計算平衡因子

//計算結(jié)點root的平衡因子
int getBalanceFactor(node* root) {
    //左子樹高度減右子樹高度
    return getHeight(root->lchild) - getHeight(root->rchild); 
}

因為沒有辦法通過當(dāng)前結(jié)點的子樹的平衡因子計算得到該結(jié)點的平衡因子，而需要借助子樹的高度間接求得。顯然，結(jié)點root所在子樹的height等于其左子樹的height與右子樹的height的較大值加1。

void updateHeight(node* root) {
    //max(左孩子的height，右孩子的height) + 1
    root->height = max(getHeight(root->lchild), getHeight(root->rchild)) + 1; 
} 

平衡二叉樹的基本操作
主要是AVL樹的查找、插入和建立

1. 查找操作
   由于AVL樹本身是一棵BST樹，因此其查找操作的做法與BST樹相同。

//search函數(shù)查找AVL樹中數(shù)據(jù)域為x的結(jié)點
void search(node* root, int x) {
    if(root == NULL) {
        printf("search failed\n");
        return ;
    }
    if(x == root->data) {
        printf("%d\n", root->data);
    } else if(x > root->data) {
        search(root->lchild, x);    //往左子樹搜索x 
    } else {
        search(root->rchild, x);    //往右子樹搜索 
    } 
} 

2. 插入操作

左旋

//左旋（Left Rotation)
void L(node* &root) {
    node* temp = root->rchild;      //root指向結(jié)點A，temp指向結(jié)點B
    root->rchild = temp->lchild;    //讓B的左子樹成為A的右子樹
    temp->lchild = root;            //讓A成為B的左子樹
    updataHeight(root);             //更新結(jié)點A的高度
    updataHeight(temp);             //更新結(jié)點B的高度
    root = temp;                    //將根結(jié)點設(shè)為結(jié)點B 
} 

右旋

//右旋（Right Rotation）
void R(node* &root) {
    node* temp = root->lchild;      //root指向結(jié)點B，temp指向結(jié)點A 
    root->lchild = temp->rchild;    //讓A的右子樹成為B的左子樹 
    temp->rchild = root;            //讓B成為A的右子樹 
    updataHeight(root);             //更新結(jié)點A的高度 
    updataHeight(temp);             //更新結(jié)點B的高度 
    root = temp;                    //將根結(jié)點設(shè)為結(jié)點A 
} 

左旋和右旋的對稱本質(zhì)——它們互為逆操作
只要把最靠近插入結(jié)點的失衡結(jié)點調(diào)整到正常，路徑上的所有結(jié)點就都會平衡
假設(shè)最靠近插入結(jié)點的失衡結(jié)點是A，顯然它的平衡因子只可能是2或者-2。很容易發(fā)現(xiàn)這兩種情況完全對稱，因此主要討論結(jié)點A的平衡因子是2的情形。

A的平衡因子是2的情形
由于結(jié)點A的平衡因子是2，因此左子樹的高度比右子樹大2，于是以結(jié)點A為根結(jié)點的子樹一定是兩種形態(tài)LL型與LR型之一（注意：LL和LR只表示樹型，不是左右旋的意思）。結(jié)點A、B、C的權(quán)值滿足A > B > C?？梢园l(fā)現(xiàn)，當(dāng)結(jié)點A的左孩子的平衡因子是1時為LL型，是-1型時為LR型。
先考慮LL型，可以把C為根結(jié)點的子樹看作一個整體，然后以結(jié)點A作為root進行右旋，便可以達到平衡。
然后考慮LR型，可以先忽略結(jié)點A，以結(jié)點C為root進行左旋，就可以把轉(zhuǎn)化為LL型，然后按上面LL型的做法進行一次右旋即可。

A的平衡因子是-2的情形
由于結(jié)點A的平衡因子為-2，因此右子樹的高度比左子樹大2，于是以結(jié)點A為根結(jié)點的子樹一定是兩種形態(tài)RR型與RL型之一，由于和上面討論的LL型和LR型對稱，此處結(jié)點A、B、C的權(quán)值滿足A < B < C?？梢园l(fā)現(xiàn)，**當(dāng)結(jié)點A的右孩子的平衡因子是-1時為RR型，是1時的RL型。
對RR型來說，可以把以C為根結(jié)點的子樹看作一個整體，然后以結(jié)點A作為root進行左旋，便可以達到平衡。
對RL型來說，可以先忽略結(jié)點A，以結(jié)點C為root進行右旋，就可以把情況轉(zhuǎn)化為RR型，然后按上面RR型的做法進行一次左旋即可。

匯總：

樹型                        判定條件                                            調(diào)整方法
LL                BF(root) = 2, BF(root->lchild) = 1                         對root進行右旋
LR                BF(root) = 2, BF(root->lchild) = -1            先對root->lchild進行左旋，再對root進行右旋
RR                BF(root) = -2, BF(root->rchild) = -1                       對root進行右旋
RL                BF(root) = -2, BF(root->rchild) = 1            先對root->rchild進行右旋，再對root進行左旋

首先，AVL樹的插入代碼是在二叉查找樹的插入代碼的基礎(chǔ)上增加平衡操作的，因此，不考慮平衡操作，代碼是下面這樣的。

//插入權(quán)值為v的結(jié)點
void insert(node* &root, int v) {
   if(root == NULL) {  //到達空結(jié)點 
       root = newNode(v);
       return ;    
   }
   if(v < root->v) {
       insert(root->lchild, v);
   } else {
       insert(root->rchild, v);
   }
} 

在這個基礎(chǔ)上，由于需要從插入的結(jié)點開始從下往上判斷結(jié)點是否平衡，因此需要在每個insert函數(shù)之后更新當(dāng)前子樹的高度，并在這之后根據(jù)樹型是LL型、LR型、RR型、RL型之一來進行平衡操作

//插入權(quán)值為v的結(jié)點
void insert(node* &root, int v) {
    if(root == NULL) {  //到達空結(jié)點 
        root = newNode(v);
        return ;    
    }
    if(v < root->v) {
        insert(root->lchild, v);
        updataHeight(root);     //更新樹高
        if(getBalanceFactor(root) == 2) {
            if(getBalanceFactor(root->lchild) == 1) {   //LL型 
                R(root);
            } else if(getBalanceFactor(root->lchild) == -1) {   //LR型 
                L(root->lchild);    //算法筆記上是這樣，不過筆者疑惑應(yīng)該是左旋右孩子才對 
                R(root);
            }
        } 
    } else {
        insert(root->rchild, v);
        updataHeight(root);     //更新樹高
        if(getBalanceFactor(root) == -2) {
            if(getBalanceFactor(root->rchild) == -1) {  //RR型 
                L(root);
            } else if(getBalanceFactor(root->rchild) == 1) {
                R(root->rchild);    //算法筆記上是這樣，不過筆者疑惑應(yīng)該是右旋左孩子才對 
                L(root); 
            } 
        } 
    }
}

3. AVL樹的建立

//AVL樹的建立
node* Create(int data[], int n) {
    node* root = NULL;  //新建空結(jié)點root
    for(int i = 0; i < n; i++) {
        insert(root, data[i]);  //將data[0]~data[n - 1]插入AVL樹中 
    } 
    return root;    //返回根結(jié)點 
}