1. 簡介

平衡二叉樹（Balanced Binary Tree）具有以下性質(zhì)：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。平衡二叉樹的常用實現(xiàn)方法有紅黑樹、AVL、替罪羊樹、Treap、伸展樹等。 其中最為經(jīng)典當屬AVL樹，我們

總計而言就是：平衡二叉樹是一種二叉排序樹，其中每一個結點的左子樹和右子樹的高度差至多等于1。

2. 性值

AVL樹具有下列性質(zhì)的二叉樹（注意，空樹也屬于一種平衡二叉樹）：

l  它必須是一顆二叉查找樹

l  它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。

l  若將二叉樹節(jié)點的平衡因子BF定義為該節(jié)點的左子樹的深度減去它的右子樹的深度，則平衡二叉樹上所有節(jié)點的平衡因子只可能為-1,0,1.

l  只要二叉樹上有一個節(jié)點的平衡因子的絕對值大于1，那么這顆平衡二叉樹就失去了平衡。

3.實現(xiàn):

AVL樹的構建我們需要明白一個核心的操作，整個實現(xiàn)過程是通過在一棵平衡二叉樹中依次插入元素(按照二叉排序樹的方式)，若出現(xiàn)不平衡，則要根據(jù)新插入的結點與最低不平衡結點的位置關系進行相應的調(diào)整。各個調(diào)整的方法分為LL型、RR型、LR型和RL型4種類型，其余的操作與一般的樹進行插入和修改數(shù)據(jù)無異，這里由于篇幅關系不做過多綴數(shù)，以其中一種LR型調(diào)整為例說明，其余各種也都是舉一反三思考：

由于在A的左孩子(L)的右子樹(R)上插入新結點，使原來平衡二叉樹變得不平衡，此時A的平衡因子由1變?yōu)?。圖5是LR型的最簡單形式。顯然，按照大小關系，結點C應作為新的根結點，其余兩個節(jié)點分別作為左右孩子節(jié)點才能平衡。

①將B的左孩子C提升為新的根結點

②將原來的根結點A降為C的右孩子

③各子樹按大小關系連接(BL和AR不變，CL和CR分別調(diào)整為B的右子樹和A的左子樹)。

4. 代碼演示：

代碼僅作參考，具體實現(xiàn)請根據(jù)實際情況修改：

#include<stdio.h>
#include<stdlib.h>
 
//結點設計 
typedef struct Node {
    int key;
    struct Node *left;
    struct Node *right;
    int height;
} BTNode;
 
int height(struct Node *N) {
    if (N == NULL)
        return 0;
    return N->height;
}
 
int max(int a, int b) {
    return (a > b) ? a : b;
}
 
BTNode* newNode(int key) {
    struct Node* node = (BTNode*)malloc(sizeof(struct Node));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;
    return(node);
}
 
//ll型調(diào)整 
BTNode* ll_rotate(BTNode* y) {
    BTNode *x = y->left;
    y->left = x->right;
    x->right = y;
 
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
 
    return x;
}
 
//rr型調(diào)整 
BTNode* rr_rotate(BTNode* y) {
    BTNode *x = y->right;
    y->right = x->left;
    x->left = y;
 
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
 
    return x;
}
 
//判斷平衡
int getBalance(BTNode* N) {
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}
 
//插入結點&數(shù)據(jù)
BTNode* insert(BTNode* node, int key) {
    if (node == NULL)
        return newNode(key);
 
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else
        return node;
 
    node->height = 1 + max(height(node->left), height(node->right));
 
    int balance = getBalance(node);
 
    if (balance > 1 && key < node->left->key) //LL型
        return ll_rotate(node);
 
    if (balance < -1 && key > node->right->key)     //RR型
        return rr_rotate(node);
 
    if (balance > 1 && key > node->left->key) {   //LR型
        node->left = rr_rotate(node->left);
        return ll_rotate(node);
    }
 
    if (balance < -1 && key < node->right->key) {   //RL型
        node->right = ll_rotate(node->right);
        return rr_rotate(node);
    }
 
    return node;
}
 
//遍歷
void preOrder(struct Node *root) {
    if (root != NULL) {
        printf("%d ", root->key);
        preOrder(root->left);
        preOrder(root->right);
    }
}
 
int main() {
    BTNode *root = NULL;
 
    root = insert(root, 2);
    root = insert(root, 1);
    root = insert(root, 0);
    root = insert(root, 3);
    root = insert(root, 4);
    root = insert(root, 4);
    root = insert(root, 5);
    root = insert(root, 6);
    root = insert(root, 9);
    root = insert(root, 8);
    root = insert(root, 7);
 
    printf("前序遍歷：");
    preOrder(root);
    return 0;
}