C Program to implement an AVL tree

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


Bhanu Namikaze

Bhanu Namikaze is an Ethical Hacker, Web Developer, Student and Mechanical Engineer. He Enjoys writing articles, Blogging, Solving Errors and Social Networking. Feel Free to let me know any of your concerns about hacking or let me know if you need any more methods on hacking anything. Enjoy Learning

No comments:

Post a Comment