ADS LAB@AVL-TREE

07:51 | Posted by b.phanikrishna |

Experiment No:
2
Name of the Experiment:
To perform various operations i.e., insertions and deletions on AVL trees

Aim: To perform various operations i.e., insertions and deletions on AVL trees
Description:
AVL Tree: AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.
Why AVL Trees?
Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where h is the height of the BST. The cost of these operations may become O(n) for a skewed Binary tree. If we make sure that height of the tree remains O(Logn) after every insertion and deletion, then we can guarantee an upper bound of O(Logn) for all these operations. The height of an AVL tree is always O(Logn) where n is the number of nodes in the tree (See this video lecture for proof).

PROGRAM:-
#include<stdio.h>
typedef struct node
{  int data;
   struct node *left,*right;
   int ht;
}node;

  node *insert(node *,int);
  node *Delete(node *,int);
  void  preorder(node *);
  void  inorder(node *);
  int   height( node *);
  node *rotateright(node *);
  node *rotateleft(node *);
  node *RR(node *);
  node *LL(node *);
  node *LR(node *);
  node *RL(node *);
  int BF(node *);


void main()
{
    node *root=NULL;
    int x,n,i,op;
    do
        {
            printf("\n1)Create : ");
            printf("\n2)Insert : ");
            printf("\n3)Delete : ");
            printf("\n4)Print  : ");
            printf("\n5)Quit   : ");
            printf("\nEnter Your Choice : ");
            scanf("%d",&op);
            switch(op)
                {
                case 1:printf("\nEnter no.of elements :");
                       scanf("%d",&n);
                       printf("\n Enter tree data :");
                       root=NULL;
                       for(i=0;i<n;i++)
                       {
                        scanf("%d",&x);
                        root=insert(root,x);
                       }
                       break;
                case 2:printf("\nEnter a data : ");
                       scanf("%d",&x);
                       root=insert(root,x);
                       break;
                case 3:printf("\nEnter a data : ");
                       scanf("%d",&x);
                       root=Delete(root,x);
                       break;
                case 4:    printf("\nPreorder sequence :\n");
                    preorder(root);
                    printf("\nInorder sequence :\n");
                    inorder(root);
                    break;
                 }

    }while(op!=5);

}
node * insert(node *T,int x)
{
    if(T==NULL)
    {
        T=(node*)malloc(sizeof(node));
        T->data=x;
        T->left=NULL;
        T->right=NULL;
    }
    else
        if(x > T->data)                // insert in right subtree
        {
            T->right=insert(T->right,x);
            if(BF(T)==-2)
                if(x>T->right->data)
                    T=RR(T);
                else
                    T=RL(T);
        }
        else
            if(x<T->data)
            {
                T->left=insert(T->left,x);
                if(BF(T)==2)
                    if(x < T->left->data)
                        T=LL(T);
                    else
                        T=LR(T);
            }
            T->ht=height(T);
            return(T);
}

node * Delete(node *T,int x)
{       node *p;

    if(T==NULL)
    {
        return NULL;
    }
    else

        if(x > T->data)                // insert in right subtree
        {
            T->right=Delete(T->right,x);
            if(BF(T)==2)
                if(BF(T->left)>=0)
                    T=LL(T);
                else
                    T=LR(T);
        }
        else
            if(x<T->data)
                {
                    T->left=Delete(T->left,x);
                    if(BF(T)==-2)//Rebalance during windup
                        if(BF(T->right)<=0)
                            T=RR(T);
                        else
                            T=RL(T);
                }
            else
              {
                //data to be deleted is found
                  if(T->right !=NULL)
                  {  //delete its inorder succesor
                      p=T->right;
                      while(p->left != NULL)
                      p=p->left;

                      T->data=p->data;
                      T->right=Delete(T->right,p->data);
                      if(BF(T)==2)//Rebalance during windup
                        if(BF(T->left)>=0)
                            T=LL(T);
                        else
                            T=LR(T);
                   }
                  else
                   return(T->left);

              }
    T->ht=height(T);
    return(T);
}

int height(node *T)
{
    int lh,rh;
    if(T==NULL)
        return(0);
    if(T->left==NULL)
        lh=0;
    else
        lh=1+T->left->ht;
    if(T->right==NULL)
        rh=0;
    else
        rh=1+T->right->ht;
    if(lh>rh)
        return(lh);
    return(rh);
}
node * rotateright(node *x)
{
    node *y;
    y=x->left;
    x->left=y->right;
    y->right=x;
    x->ht=height(x);
    y->ht=height(y);
    return(y);
}
node * rotateleft(node *x)
{
    node *y;
    y=x->right;
    x->right=y->left;
    y->left=x;
    x->ht=height(x);
    y->ht=height(y);
    return(y);
}
node * RR(node *T)
{
    T=rotateleft(T);
    return(T);
}
node * LL(node *T)
{
    T=rotateright(T);
    return(T);
}
node * LR(node *T)
{
    T->left=rotateleft(T->left);
    T=rotateright(T);
    return(T);
}
node * RL(node *T)
{
    T->right=rotateright(T->right);
    T=rotateleft(T);
    return(T);
}
int BF(node *T)
{
    int lh,rh;
    if(T==NULL)
    return(0);
    if(T->left==NULL)
        lh=0;
    else
        lh=1+T->left->ht;
    if(T->right==NULL)
        rh=0;
    else
        rh=1+T->right->ht;
    return(lh-rh);
}
void preorder(node *T)
{
    if(T!=NULL)
    {
        printf(" %d(Bf=%d)",T->data,BF(T));
        preorder(T->left);
        preorder(T->right);
    }
}
void inorder(node *T)
{
    if(T!=NULL)
    {
        inorder(T->left);
        printf(" %d(Bf=%d)",T->data,BF(T));
        inorder(T->right);
    } }

Output@avl tree:
1)Create :
2)Insert :
3)Delete :
4)Print  :
5)Quit   :
Enter Your Choice : 1
Enter no.of elements :6
 Enter tree data :10 5 1 6 13 17
1)Create :
2)Insert :
3)Delete :
4)Print  :
5)Quit   :
Enter Your Choice : 4
Preorder sequence :
 10(Bf=0) 5(Bf=0) 1(Bf=0) 6(Bf=0) 13(Bf=-1) 17(Bf=0)
Inorder sequence :
 1(Bf=0) 5(Bf=0) 6(Bf=0) 10(Bf=0) 13(Bf=-1) 17(Bf=0)
1)Create :
2)Insert :
3)Delete :
4)Print  :
5)Quit   :

Enter Your Choice : 3
Enter a data : 17
1)Create :
2)Insert :
3)Delete :
4)Print  :
5)Quit   :
Enter Your Choice : 4

Preorder sequence :
 10(Bf=1) 5(Bf=0) 1(Bf=0) 6(Bf=0) 13(Bf=0)
Inorder sequence :
 1(Bf=0) 5(Bf=0) 6(Bf=0) 10(Bf=1) 13(Bf=0)
1)Create :
2)Insert :
3)Delete :
4)Print  :
5)Quit   :
Enter Your Choice : 2

Enter a data : 16
1)Create :
2)Insert :
3)Delete :
4)Print  :
5)Quit   :
Enter Your Choice : 4

Preorder sequence :
 10(Bf=0) 5(Bf=0) 1(Bf=0) 6(Bf=0) 13(Bf=-1) 16(Bf=0)
Inorder sequence :
 1(Bf=0) 5(Bf=0) 6(Bf=0) 10(Bf=0) 13(Bf=-1) 16(Bf=0)
1)Create :
2)Insert :
3)Delete :
4)Print  :
5)Quit   :
Enter Your Choice : 2

Enter a data : 17
1)Create :
2)Insert :
3)Delete :
4)Print  :
5)Quit   :
Enter Your Choice : 4

Preorder sequence :
 10(Bf=0) 5(Bf=0) 1(Bf=0) 6(Bf=0) 16(Bf=0) 13(Bf=0) 17(Bf=0)
Inorder sequence :
 1(Bf=0) 5(Bf=0) 6(Bf=0) 10(Bf=0) 13(Bf=0) 16(Bf=0) 17(Bf=0)
1)Create :
2)Insert :
3)Delete :
4)Print  :
5)Quit   :
Enter Your Choice :5




Labels: , , ,

1 comments:

Unknown said...

thanks

8 April 2015 at 00:06

Post a Comment

Subscribe to: Post Comments (Atom)

Copyright © . All Rights Reserved.

Blogger Template created with Artisteer by Patricia P..