AVL樹單旋轉和雙旋轉算法（c）

要理解這段代碼必須把單旋轉和雙旋轉的算法搞明白。其次，要真正理解遞歸的用法。

[html]
/* 
 * avl tree. 
 */ 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
 
struct AvlNode; 
typedef struct AvlNode *Position; 
typedef struct AvlNode *AvlTree; 
 
struct AvlNode 
{ 
    int Element; 
    AvlTree Left; 
    AvlTree Right; 
    int Height; 
}; 
 
int Max(int a, int b)  
{ 
    return (a >  b) ? a : b ;     
} 
 
static int HeightAvl(Position P) 
{ 
    if (P == NULL) 
    { 
        return -1; 
    } 
    else 
    { 
        return P->Height; 
    } 
 
} 
 
 
static Position SingleRotateWithLeft(Position K2) 
{ 
        Position K1; 
 
        K1 = K2->Left; 
        K2->Left = K1->Right; 
        K1->Right = K2; 
 
        K2->Height = Max(HeightAvl(K2->Left), HeightAvl(K2->Right)) +1; 
        K1->Height = Max(HeightAvl(K1->Left), HeightAvl(K2->Right)) +1; 
 
        return K1; 
} 
 
static Position SingleRotateWithRight(Position K2) 
{ 
    Position K1; 
 
    K1 = K2->Right; 
    K2->Right = K1->Left; 
    K1->Left = K2; 
 
    K2->Height = Max(HeightAvl(K2->Left), HeightAvl(K2->Right)) +1; 
    K1->Height = Max(HeightAvl(K1->Left), HeightAvl(K2->Right)) +1; 
 
    return K1; 
} 
 
static Position DoubleRotateWithLeft(Position K3) 
{ 
    K3->Left = SingleRotateWithRight(K3->Left); 
    return SingleRotateWithLeft(K3); 
} 
 
static Position DoubleRotateWithRight(Position K3) 
{ 
    K3->Left = SingleRotateWithLeft(K3->Left); 
    return SingleRotateWithRight(K3); 
} 
 
AvlTree InsertAvl(int X, AvlTree T) 
{ 
    if (T == NULL) 
    { 
        T = (AvlTree)malloc(sizeof(AvlTree)); 
        if (T == NULL) 
        { 
            printf("out of space!!!\n"); 
        } 
        else 
        { 
            T->Left = NULL; 
            T->Right = NULL; 
        } 
        T->Element = X; 
        T->Height = 0; 
    } 
    else if (X < T->Element) 
    { 
        T->Left = InsertAvl(X, T->Left); 
         if (HeightAvl(T->Left) - HeightAvl(T->Right) == 2) 
         { 
            if (X < T->Left->Element) 
            { 
                T = SingleRotateWithLeft(T); 
            } 
            else 
            { 
                T = DoubleRotateWithLeft(T); 
            } 
         } 
    } 
    else if (X > T->Element) 
    { 
        T->Right = InsertAvl(X, T->Right); 
        if (HeightAvl(T->Right) - HeightAvl(T->Left) == 2) 
        { 
            if (X > T->Right->Element) 
            { 
                T = SingleRotateWithRight(T); 
            } 
            else 
            { 
                T = DoubleRotateWithRight(T); 
            } 
        } 
    } 
    T->Height = Max(HeightAvl(T->Left), HeightAvl(T->Right)) + 1; 
    return T; 
} 
 
 
int main(void) 
{ 
    AvlTree Tree; 
    InsertAvl(1, Tree); 
}