AVL(Adelson-Velskii和Landis)树是带有平衡条件的二叉查找树，一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树

头文件

#ifndef _AvlTree_H

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

AvlTree MakeEmpty( AvlTree T );
Position Find( ElementType X, AvlTree T );
Position FindMin( AvlTree T );
Position FindMax( AvlTree T );
AvlTree Insert( ElementType X, AvlTree T );
AvlTree Delete( ElementType X, AvlTree T );
ElementType Retrieve( Position P );

#endif /* _AvlTree_H */

/* Place in the implementation file */
struct AvlNode
{
	ElementType Element;
	AvlTree Left;
	AvlTree Right;
	int Height;
}

主要例程，对于删除节点较为复杂，如果删除节点操作较少，懒惰删除无疑是最好的办法

AvlTree MakeEmpty( AvlTree T )
{
	if( T != NULL )
	{
		MakeEmpty( T->Left );
		MakeEmpty( T->Right );
		free( T );
	}
	return NULL;
}

Position Find( ElementType X, AvlTree T )
{
	if( T == NULL )
		return NULL;
	if( X > T->Element )
		return Find( X, T->Right );
	else
		if( X < T->Element )
			return Find( X, T->Left );
		else
			return T;
}

Position FindMin( AvlTree T )
{
	if( T != NULL )
		while( T->Left != NULL )
			T = T->Left;
	
	return T;
}

Position FindMax( AvlTree T )
{
	if( T != NULL )
		while( T->Right != NULL )
			T = T->Right;

	return T;
}

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

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

	T->Height = Max( Height( T->Left ), Height( T->Right ) ) + 1;
	return T;
}

/* This function can be called only if K2 has a left child */
/* Perform a rotate between a node (K2) and its left child */
/* Update heights,then return new root */
static Position SingleRotateWithLeft( Position K2 )
{
	Position K1;

	K1 = K2->Left;
	K2->Left = K1->Right;
	K1->Right = K2;

	K2->Height = Max( Height( K2->Left ), Height( K2->Right ) ) + 1;
	K1->Height = Max( Height( K1->Left ), K2->Height ) + 1;

	return K1;/* New root */
}


/* This function can be called only if K1 has a right child */
/* Perform a rotate between a node (K1) and its right child */
/* Update heights,then return new root */
static Position SingleRotateWithRight( Position K1 )
{
	Position K2;

	K2 = K1->Right;
	K1->Right = K2->Left;
	K2->Left = K1;

	K1->Height = Max( Height( K1->Left ), Height( K1->Right ) ) + 1;
	K2->Height = Max( K1->Height, Height( K2->Right ) ) + 1;

	return K2; /* New root */
}

/* This function can be called only if K3 has a left  */
/* child and K3's left child has a right child */
/* Do the left-right double rotation */
/* Update heights, then return new root */
static Position DoubleRotateWithLeft( Position K3 )
{
	/* Rotate between K1 and K2 */
	K3->Left = SingleRotateWithRight( K3->Left );

	return SingleRotateWithLeft( K3 );
}

/* This function can be called only if K1 has a right  */
/* child and K1's right child has a left child */
/* Do the right-left double rotation */
/* Update heights, then return new root */
static Position DoubleRotateWithRight( Position K1 )
{
	/* Rotate between K2 and K3 */
	K1->Right = SingleRotateWithLeft( K1->Right );

	return SingleRotateWithLeft( K1 );
}