【种树系列】中秋特辑之AvlTree

/* This ADT can carry out major operations of AvlTree if you achieve the rest. */
/* AvlTree was created to keep an ideal balance of tree height. */ 
/* We all know that AvlTree major contains Single Rotation and Double Rotation. */  

#define ElementType int

typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;

struct AvlNode{
    ElementType Data;
    AvlTree Left;
    AvlTree Right;
    int Height;
};

static int Height(Position P){
    if(!P)    return -1;
    else return P->Height;
}

int Max ( int a, int b )
{
    return a > b ? a : b;
}

AvlTree Insert(ElementType X, AvlTree T){
    if(!T){
        T=malloc(sizeof(struct AvlNode));
        if(!T)
            FatalError("Out of space!!!");
        else{
            T->Data=X;
            T->Height=0;
            T->Left=T->Right=NULL;
        }
    }
    else if(X<T->Data){
        T->Left=Insert(X,T->Left);
        if(2 == (Height(T->Left)-Height(T->Right)))
            if(X<T->Left->Data)
                T = SingleRotateWithLeft(T);
            else
                T = DoubleRotateWithLeft(T);            
    }
    else if(X>T->Data){
        T->Right=Insert(X,T->Right);
        if(2 == (Height(T->Right)-Height(T->Left)))
            if(X>T->Right->Data)
                T = SingleRotateWithRight(T);
            else
                T = DoubleRotateWithRight(T);
    }
    /*Else X is in the tree already; we' ll do nothing*/

    // don't forget to renew Height of AvlTree 
    T->Height=Max(Height(T->Left),Height(T->Right)) + 1 ;
    return T;
}

static Position SingleRotateWithLeft(Position B){
    Position A;

    /*ATree are dancing with BTree*/
    A = B->Left;
    B->Left = A->Right;
    A->Right = B;

    B->Height = Max(Height(B->Left),Height(B->Right))+1;
    A->Height = Max(Height(A->Left),Height(A->Right))+1;

    return A;   /*New root*/
} 

static Position DoubleRotateWithLeft(Position C){
    /*Rotate between A and B */
    C->Left = SingleRotateWithRight(C->Left);

    /*Rotate between C and B */
    return SingleRotateWithLeft(C);
}