/* Program to implement an AVL tree. */
#include
<stdio.h>
#include
<stdlib.h>
struct avlnode
{
int data;
struct avlnode *left;
struct avlnode *right;
int height;
};
typedef struct avlnode *position;
typedef struct avlnode *avltree;
avltree makeempty( avltree T )
{
if( T != NULL )
{
makeempty( T->left );
makeempty( T->right );
free( T );
}
return NULL;
}
position find( int X,
avltree T )
{
if( T == NULL )
return NULL;
if( X < T->data )
return find( X, T->left );
else
if( X > T->data )
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;
printf( "\nin SingleRotateWithleft\n" );
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;
printf( "\nin SingleRotateWithright\n" );
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 */
printf( "\nin DoubleRotateWithleft\n" );
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 */
printf( "\nin DoubleRotateWithright\n" );
K1->right =
SingleRotateWithleft( K1->right );
/* Rotate between K1 and K2 */
return SingleRotateWithright( K1 );
}
/* START: fig4_37.txt */
avltree Insert( int X,
avltree T )
{
if( T == NULL )
{
/* Create and return a one-node tree */
T = malloc( sizeof( struct avlnode ) );
if( T == NULL )
printf( "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( height( T->left ) - height( T->right ) == 2 )
if( X < T->left->data )
T =
SingleRotateWithleft( T );
else
T =
DoubleRotateWithleft( T );
}
else
if( X > T->data )
{
T->right = Insert( X,
T->right );
if( height( T->right ) - height( T->left ) == 2 )
if( X > T->right->data )
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 */
avltree
Delete( int X, avltree T
)
{
printf( "Sorry; Delete is unimplemented; %d
remains\n", X );
return T;
}
int
retrieve( position P )
{
return P->data;
}
/* traverse a
binary search tree in a LDR (left-Data-right) fashion */
void inorder (avltree sr
)
{
if ( sr != NULL )
{
inorder ( sr -> left )
;
/* print the data of the node whose
leftchild is NULL or the path has
already
been traversed */
printf ( "\t data = %d height = %d", sr -> data, height(sr)) ;
inorder ( sr -> right
) ;
}
else
return ;
}
main( )
{
avltree T;
position P;
int i;
int j = 0;
T = makeempty( NULL );
for( i = 0; i < 10; i++, j = ( j + 7 ) % 10 )
T = Insert( j, T );
for( i = 0; i < 10; i++ )
if( ( P = find( i, T ) )
== NULL || retrieve( P ) != i )
printf( "Error at %d\n", i );
inorder (T);
/*for( i = 0;
i < 50; i += 2 )
T = Delete( i, T );
for( i = 1; i < 50; i += 2 )
if( ( P = find( i, T ) ) == NULL || retrieve( P ) != i )
printf( "Error at %d\n",
i );
for( i = 0; i < 50; i += 2 )
if( ( P = find( i, T ) ) != NULL )
printf( "Error at %d\n", i );
*/
printf( "\nMin
is %d, Max is %d\n",
retrieve( findmin( T ) ),
retrieve( findmax( T ) ) );
printf( "\nheight
is: %d", height(T));
return 0;
}
/*C:\Users\Administrator\Desktop\stack>avltree.exe
in DoubleRotateWithright
in SingleRotateWithleft
in SingleRotateWithright
in SingleRotateWithright
data = 0 height = 0
data = 1 height = 2 data = 2
height = 1 data = 3 height =
0
data = 4 height = 3
data = 5 height = 1 data = 6
height = 0 data = 7 height =
2 data = 8 height = 1
data = 9 height = 0
Min is 0, Max is 9
height is: 3
*/
No comments:
Post a Comment