Search Tutorials

Saturday, 20 April 2013

C code to implement AVL Tree

AVL tree(Adelson-Velskii and Ladis'tree, named after their inventors) is also called balanced binary tree. Property of AVL tree: the hieght of the two child subtree of any node differ by at most one.If they differ by more than one, re-balancing is done to restore this property.

/* C program to implement AVL Tree */

#include<stdio.h>
#include<malloc.h>

typedef enum { FALSE ,TRUE } bool;
struct node
{
    int info;
    int balance;
    struct  node *lchild;
    struct  node *rchild;
};

struct node *insert (int , struct node *, int *);
struct node* search(struct node *,int);

main()
{
    bool ht_inc;
    int info ;
    int choice;
    struct node *root = (struct node *)malloc(sizeof(struct node));
    root =  NULL;

    while(1)
    {
        printf("1.Insert\n");
        printf("2.Display\n");
        printf("3.Quit\n");
        printf("Enter your choice : ");
        scanf("%d",&choice);
        switch(choice)
        {
        case 1:
            printf("Enter the value to be inserted : ");
            scanf("%d", &info);
            if( search(root,info) == NULL )
                root = insert(info, root, &ht_inc);
            else
                printf("Duplicate value ignored\n");
            break;
        case 2:
            if(root==NULL)
            {
                printf("Tree is empty\n");
                continue;
            }
            printf("Tree is :\n");
            display(root, 1);
            printf("\n\n");
            printf("Inorder Traversal is: ");
            inorder(root);
            printf("\n");
            break;
        case 3:
            exit(1);
        default:
            printf("Wrong choice\n");
        }/*End of switch*/
    }/*End of while*/
}/*End of main()*/

struct node* search(struct node *ptr,int info)
{
    if(ptr!=NULL)
        if(info < ptr->info)
            ptr=search(ptr->lchild,info);
        else if( info > ptr->info)
            ptr=search(ptr->rchild,info);
    return(ptr);
}/*End of search()*/

struct node *insert (int info, struct node *pptr, int *ht_inc)
{
    struct node *aptr;
    struct node *bptr;

    if(pptr==NULL)
    {
        pptr = (struct node *) malloc(sizeof(struct node));
        pptr->info = info;
        pptr->lchild = NULL;
        pptr->rchild = NULL;
        pptr->balance = 0;
        *ht_inc = TRUE;
        return (pptr);
    }

    if(info < pptr->info)
    {
        pptr->lchild = insert(info, pptr->lchild, ht_inc);
        if(*ht_inc==TRUE)
        {
            switch(pptr->balance)
            {
            case -1: /* Right heavy */
                pptr->balance = 0;
                *ht_inc = FALSE;
                break;
            case 0: /* Balanced */
                pptr->balance = 1;
                break;
            case 1: /* Left heavy */
                aptr = pptr->lchild;
                if(aptr->balance == 1)
                {
                    printf("Left to Left Rotation\n");
                    pptr->lchild= aptr->rchild;
                    aptr->rchild = pptr;
                    pptr->balance = 0;
                    aptr->balance=0;
                    pptr = aptr;
                }
                else
                {
                    printf("Left to right rotation\n");
                    bptr = aptr->rchild;
                    aptr->rchild = bptr->lchild;
                    bptr->lchild = aptr;
                    pptr->lchild = bptr->rchild;
                    bptr->rchild = pptr;

                    if(bptr->balance == 1 )
                        pptr->balance = -1;
                    else
                        pptr->balance = 0;
                    if(bptr->balance == -1)
                        aptr->balance = 1;
                    else
                        aptr->balance = 0;
                    bptr->balance=0;
                    pptr=bptr;
                }
                *ht_inc = FALSE;
            }/*End of switch */
        }/*End of if */
    }/*End of if*/

    if(info > pptr->info)
    {
        pptr->rchild = insert(info, pptr->rchild, ht_inc);
        if(*ht_inc==TRUE)
        {
            switch(pptr->balance)
            {
            case 1: /* Left heavy */
                pptr->balance = 0;
                *ht_inc = FALSE;
                break;
            case 0: /* Balanced */
                pptr->balance = -1;
                break;
            case -1: /* Right heavy */
                aptr = pptr->rchild;
                if(aptr->balance == -1)
                {
                    printf("Right to Right Rotation\n");
                    pptr->rchild= aptr->lchild;
                    aptr->lchild = pptr;
                    pptr->balance = 0;
                    aptr->balance=0;
                    pptr = aptr;
                }
                else
                {
                    printf("Right to Left Rotation\n");
                    bptr = aptr->lchild;
                    aptr->lchild = bptr->rchild;
                    bptr->rchild = aptr;
                    pptr->rchild = bptr->lchild;
                    bptr->lchild = pptr;

                    if(bptr->balance == -1)
                        pptr->balance = 1;
                    else
                        pptr->balance = 0;
                    if(bptr->balance == 1)
                        aptr->balance = -1;
                    else
                        aptr->balance = 0;
                    bptr->balance=0;
                    pptr = bptr;
                }/*End of else*/
                *ht_inc = FALSE;
            }/*End of switch */
        }/*End of if*/
    }/*End of if*/

    return(pptr);
}/*End of insert()*/

display(struct node *ptr,int level)
{
    int i;
    if ( ptr!=NULL )
    {
        display(ptr->rchild, level+1);
        printf("\n");
        for (i = 0; i < level; i++)
            printf("    ");
        printf("%d", ptr->info);
        display(ptr->lchild, level+1);
    }/*End of if*/
}/*End of display()*/

inorder(struct node *ptr)
{
    if(ptr!=NULL)
    {
        inorder(ptr->lchild);
        printf("%d  ",ptr->info);
        inorder(ptr->rchild);
    }
}/*End of inorder()*/

/* Output of AVL Tree Program */

C code to implement AVL Tree
Output of AVL Tree Program
C code to implement AVL Tree
Output of AVL Tree Program

For more related to Data Structure check List of Data Structure Programs. If you like this program, Please share and comment to improve this blog.

6 comments:

  1. Wonderful beat ! I wish to apprentice while you amend your site, how could i subscribe for a post website? The account helped me a acceptable deal. I had been tiny bit acquainted of this your broadcast provided bright clear concept digital marketer

    ReplyDelete
  2. Hello! Do you know if they make any plugins to help with SEO? I'm trying to get my blog to rank for some targeted keywords but I'm not seeing very good gains. If you know of any please share. Thank you!google search engine marketing

    ReplyDelete
  3. Hello just wanted to give you a brief heads up and let you know a few of the pictures aren't loading properly. I'm not sure why but I think its a linking issue. I've tried it in two different web browsers and both show the same results.o level physics

    ReplyDelete
  4. Thanks for the auspicious writeup. It actually was a enjoyment account it. Look complex to more brought agreeable from you! By the way, how could we keep in touch? van for sale singapore

    ReplyDelete
  5. Whoa! This blog looks exactly like my old one! It's on a completely different subject but it has pretty much the same layout and design. Excellent choice of colors! corporate litigation lawyer

    ReplyDelete

Back to Top