avl.h

AVLTREE

#include "AvlTree.h"
#include <stdlib.h>
#include <iostream>
using namespace std;

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->Left );
	else
		if( X > T->Element )
			return Find( X, T->Right );
		else
			return T;
}

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

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

	return T;
}

/* START: fig4_36.txt */
static int height( Position P )
{
	if( P == NULL )
		return -1;
	else
		return P->Height;
}
/* END */

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

/* START: fig4_39.txt */
/* 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 */
}
/* END */

/* 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 */
}

/* START: fig4_41.txt */
/* 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 );
}
/* END */

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


/* START: fig4_37.txt */
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 )
		//	 cout<<"Out of space!!!";
	//else
	//{
		T->Element = X; T->Height = 0;
		T->Left = T->Right = NULL;
	//}
	}
	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; we'll do nothing */

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



ElementType
Retrieve( Position P )
{
	return P->Element;
}

AvlTree Delete( ElementType X, AvlTree T )
{
	if( T->Element == X )
		T = NULL;
	else if( X < T->Element )
	{
		T->Left = Delete( X, T->Left );
		if( ( T->Left == NULL )&& ( T->Right == NULL ) )
			T->Height -= 1;
		if( height(T->Left) - height(T->Right) == -2 )
			T = SingleRotateWithRight( T );
	}
	else if( X > T->Element )
	{
		T->Right = Delete( X, T->Right );
		if( ( T->Left == NULL )&& ( T->Right == NULL ) )
			T->Height -= 1;
		if( height(T->Right) - height(T->Left) == -2 )
			T = SingleRotateWithLeft( T );
	}

	return T;
}