C program to implement Avl Tree

#include
#include
typedef int ElementType;
struct AvlNode;
typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;

AvlTree MakeEmpty( AvlTree T );

AvlTree Insert( ElementType X, AvlTree T );

void display(AvlTree T);


#include


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

void display(AvlTree T)
{
if(T->Left!=NULL)
display(T->Left);
if(T->Right!=NULL)
display(T->Right);
printf("%d",T->Element);
}
AvlTree MakeEmpty( AvlTree T )
{
if( T != NULL )
{
MakeEmpty( T->Left );
MakeEmpty( T->Right );
free( T );
}
return NULL;
}



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


static int Max( int Lhs, int Rhs )
{
return Lhs > Rhs ? Lhs : Rhs;
}


/* 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( Height( K2->Right ), K1->Height ) + 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 );

/* Rotate between K3 and K2 */
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 K3 and K2 */
K1->Right = SingleRotateWithLeft( K1->Right );

/* Rotate between K1 and K2 */
return SingleRotateWithRight( K1 );
}



AvlTree Insert( ElementType X, AvlTree T )
{
if( T == NULL )
{
/* Create and return a one-node tree */
T =(AvlTree) malloc( sizeof( struct AvlNode ) );
if( T == NULL )
printf( "Out of space!!!" );
else
{
T->Element = X; T->Height = 0;
T->Left = T->Right = NULL;
}
}
else
if( X <>Element )
{
T->Left = Insert( X, T->Left );
if( Height( T->Left ) - Height( T->Right ) == 2 )
if( X <>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; we'll do nothing */

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





main()
{
AvlTree T;
Position P;


int i=0,a,ch;
T = MakeEmpty( NULL );
while(1)
{
printf("\nenter your choice 1.insert 2.display 3.exit");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("enter the element");
scanf("%d",&a);
T = Insert( a, T );
break;
case 2:
printf("display by postorder traversal\n");
display(T);
break;
case 3:
exit(0);
break;
} }



}





OUTPUT:


enter your choice 1.insert 2.display 3.exit1
enter the element3

enter your choice 1.insert 2.display 3.exit1
enter the element2

enter your choice 1.insert 2.display 3.exit1
enter the element4

enter your choice 1.insert 2.display 3.exit
2
display by postorder traversal
243
enter your choice 1.insert 2.display 3.exit3