樹4. Root of AVL Tree-平衡查找樹AVL樹的實現

　　對於一棵普通的二叉查找樹而言，在進行多次的插入或刪除後，容易讓樹失去平衡，導致樹的深度不是O(logN)，而接近O(N),這樣將大大減少對樹的查找效率。一種解決辦法就是要有一個稱為平衡的附加的結構條件：任何節點的深度均不得過深。有一種最古老的平衡查找樹，即AVL樹。

　　AVL樹是帶有平衡條件的二叉查找樹。平衡條件是每個節點的左子樹和右子樹的高度最多差1的二叉查找樹（空樹的高度定義為-1）。相比於普通的二叉樹，AVL樹的節點需要增加一個變量保存節點高度。AVL樹的節點聲明如下：

typedef struct TreeNode *AvlTree;
typedef struct TreeNode *Position;
struct TreeNode
{
    int Data;
    AvlTree Left;
    AvlTree Right;
    int Height;        //保存節點高度    
};

　　只有一個節點的樹顯然是AVL樹，之後我們向其插入節點。然而在插入過程中可能破壞AVL樹的特性，因此我們需要對樹進行簡單的修正，即AVL樹的旋轉。

　　設a節點在插入下一個節點後會失去平衡，這種插入可能出現四種情況：

　　1. 對a的左兒子的左子樹進行一次插入。（左-左）

　　2. 對a的左兒子的右子樹進行一次插入。（左-右）

　　3. 對a的右兒子的左子樹進行一次插入。（右-左）

　　4. 對a的右兒子的右子樹進行一次插入。（右-右）

　　情形1和4，情形2和3分別是關於A節點的鏡像對稱，故在理論上是兩種情況，而編程具體實現還是需要考慮四種。

　　單旋轉--情形1和4：

　　雙旋轉--情形2和3：

　　情形2和3就是向上圖中的子樹Y插入一個節點，由上圖可知，無論是左單旋還是右單旋都無法改變子樹Y的高度。解決辦法是再將子樹Y分解成根節點和相應的左子樹和右子樹，然後對相應的節點做相應的旋轉，如下圖：

　　下面一個題即是考察AVL樹的旋轉：題目來源：http://www.patest.cn/contests/mooc-ds/04-%E6%A0%914

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.

Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<=20) which is the total number of keys to be inserted. Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print ythe root of the resulting AVL tree in one line.

Sample Input 1:

5
88 70 61 96 120

Sample Output 1:

70

Sample Input 2:

7
88 70 61 96 120 90 65

Sample Output 2:

88

題目大意是先輸入一個整數N，然後依次輸入N個節點的值，以此建立AVL樹，最後輸出AVL樹的根節點的值。

代碼如下：

#include <cstdio>
#include <cstdlib>

typedef struct TreeNode *AvlTree;
typedef struct TreeNode *Position;
struct TreeNode
{
    int Data;
    AvlTree Left;
    AvlTree Right;
    int Height;
};

AvlTree Insert(int x, AvlTree T);   //插入新節點，必要時調整
Position SingleRotateWithLeft(Position a);    //左單旋
Position SingleRotateWithRight(Position b);   //右單旋
Position DoubleRotateWithLeft(Position a);    //左右旋
Position DoubleRotateWithRight(Position b);   //右左旋

int Max(int x1, int x2);      //返回兩個int中較大的
int Height(Position P);     //返回一個節點的高度

int main()
{
    int n, x;
    AvlTree T = NULL;

    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &x);
        T = Insert(x, T);
    }
    printf("%d\n", T->Data);    //打印根節點的值

    return 0;
}

AvlTree Insert(int x, AvlTree T)
{
    if (T == NULL)
    {
        T = (AvlTree)malloc(sizeof(struct TreeNode));
        T->Data = x;
        T->Left = T->Right = NULL;
        T->Height = 0;
    }
    else if (x < T->Data)   //向左子樹插入
    {
        T->Left = Insert(x, T->Left);
        if (Height(T->Left) - Height(T->Right) == 2)    //需調整
        {
            if (x < T->Left->Data)
                T = SingleRotateWithLeft(T);
            else
                T = DoubleRotateWithLeft(T);
        }
    }
    else if (x > T->Data)   //向右子樹插入
    {
        T->Right = Insert(x, T->Right);
        if (Height(T->Right) - Height(T->Left) == 2)    //需調整
        {
            if (x > T->Right->Data)
                T = SingleRotateWithRight(T);
            else
                T = DoubleRotateWithRight(T);
        }
    }
    /*else值為x的節點已經存在樹中，無需插入*/

    /*更新節點高度*/
    T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
    return T;
}

Position SingleRotateWithLeft(Position a)
{
    Position b = a->Left;
    a->Left = b->Right;
    b->Right = a;
    //更新a, b節點高度
    a->Height = Max(Height(a->Left), Height(a->Right)) + 1;
    b->Height = Max(Height(b->Left), Height(b->Right)) + 1;

    return b;      /*新的根節點*/
}

Position SingleRotateWithRight(Position b)
{
    Position a = b->Right;
    b->Right = a->Left;
    a->Left = b;
    //更新a,b節點高度
    a->Height = Max(Height(a->Left), Height(a->Right)) + 1;
    b->Height = Max(Height(b->Left), Height(b->Right)) + 1;
    return a;       /*新的根節點*/
}

Position DoubleRotateWithLeft(Position a)
{
    a->Left = SingleRotateWithRight(a->Left);
    return SingleRotateWithLeft(a);
}

Position DoubleRotateWithRight(Position b)
{
    b->Right = SingleRotateWithLeft(b->Right);
    return SingleRotateWithRight(b);
}

int Max(int x1, int x2)
{
    return (x1 > x2) ? x1 : x2;
}

int Height(Position P)
{
    if (P == NULL)  //空節點高度為-1
        return -1;
    return P->Height;
} 

　　需要注意的細節是我們需要快速得到一個節點（包括空節點）的高度，所以我們需要些一個函數來處理空節點（空指針）的情況，而不是簡單的Position->Height。