要理解这段代码必须把单旋转和双旋转的算法搞明白。其次，要真正理解递归的用法。

[html]
/*
* avl tree.
*/
#include
#include
#include

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);
}