Group D Assignment 19 : AVL Program

 Problem Statement: 

A Dictionary stores keywords and its meanings. Provide facility for adding new

keywords, deleting keywords, updating values of any entry. Provide facility to display

whole data sorted in ascending/ Descending order. Also find how many maximum

comparisons may require for finding any keyword. Use Height balance tree and find the

complexity for finding a keyword


Program :

#include<iostream>

#include<string.h>

using namespace std;


struct word

{

    char key[15];

    char meaning[20];


};


struct node

{

    word data;

    node *left,*right;

  };


class AVL

{

public:

    node *root;

    

   AVL()

    {

        root=NULL;

    }

    

    node * create();

    node *insert(node *,word);

    void inorder(node *);

    node *rotateright(node *);

    node *rotateleft(node *);

    node *rr(node *);

    node *ll(node *);

    node *lr(node *);

    node *rl(node *);

    int bf(node *t);

 

};


node * AVL::create()

     {

      int n1,i;

      word x;

      cout<<"\n Enter how many nodes you want to insert: ";

            cin>>n1;

            for(i=0;i<n1;i++)

            {

                cout<<"\n Enter word And meaning: \n";

                cin>>x.key>>x.meaning;

                root=insert(root,x);

            }

     return root;   

    }


node *AVL::insert(node *t,word x)

{

    if(t==NULL)

    {

        t=new node;

        t->data=x;

        t->left=NULL;

        t->right=NULL;


    }

    else

        if(strcmp(x.key,t->data.key)>0)

        {

            t->right=insert(t->right,x);

            if(bf(t)==-2)

                if(strcmp(x.key,t->right->data.key)>0)

                    t=rr(t);

                else

                    t=rl(t);


        }

        else

            if(strcmp(x.key,t->data.key)<0)

        {

            t->left=insert(t->left,x);

            if(bf(t)==2)

                if(strcmp(x.key,t->left->data.key)<0)

                    t=ll(t);

                else

                    t=lr(t);

        }

    return t;

}


node *AVL::rotateright(node *x)

{

    node *y;

    y=x->left;

    x->left=y->right;

    y->right=x;

  

    return(y);

}


node *AVL::rotateleft(node *x)

{

    node *y;

        y=x->right;

        x->right=y->left;

        y->left=x;

     

        return(y);

}


node *AVL::rr(node *t)

{

    t=rotateleft(t);

    return(t);


}


node *AVL::ll(node *t)

{

    t=rotateright(t);

    return(t);


}


node *AVL::lr(node *t)

{

    t->left=rotateleft(t->left);

    t=rotateright(t);

    return(t);

}


node *AVL::rl(node *t)

{

    t->right=rotateright(t->right);

    t=rotateleft(t);

    return(t);

}


int AVL::bf(node *t)

{

    int lh,rh;

    if(t==NULL)

        return 0;

    if(t->left==NULL)

        lh=0;

    else

        lh=1+lh;

    if(t->right==NULL)

        rh=0;

    else

        rh=1+rh;


        return(lh-rh);


}

void AVL::inorder(node *t)

{

    if(t!=NULL)

    {

        inorder(t->left);

        cout<<" ("<<t->data.key<<"  ---  "<<t->data.meaning<<") ";

        inorder(t->right);

    }

}



int main()

{

    AVL a;

    char ans;

    int op,n,n1,i;

    word x;

    do

    {

        cout<<"\n    MAIN MENU    ";

        cout<<"\n1. create";

        cout<<"\n2. display";

        cout<<"\n3. exit";

        cout<<"\n Enter your choice: ";

        cin>>op;

        switch(op)

        {

        case 1:

           a.root= a.create();

            break;

        case 2:

            cout<<"\n Inorder Sequence: \n";

            a.inorder(a.root);

            break;

        case 3:

            return 0;


        }

        cout<<"\n\n want to continue (y/n): ";

        cin>>ans;


    }while(ans=='y');

    return 0;


}







/*

 ######## OUTPUT #########



     MAIN MENU

1. create

2. display

3. exit

 Enter your choice: 1


 Enter how many nodes you want to insert: 5


 Enter word And meaning:

a

q


 Enter word And meaning:

s

w


 Enter word And meaning:

d

e


 Enter word And meaning:

f

r


 Enter word And meaning:

g

t



 want to continue (y/n): y


    MAIN MENU

1. create

2. display

3. exit

 Enter your choice: 2


 Inorder Sequence:

 (a  ---  q)  (d  ---  e)  (f  ---  r)  (g  ---  t)  (s  ---  w)


 want to continue (y/n): y


    MAIN MENU

1. create

2. display

3. exit

 Enter your choice: 4


 */

Comments