#include <iostream>
#include<stdio.h>
#include<string.h>
#include<fstream>
using namespace std;
class avltree;
class node
{
public:
string keyw;
string meaning;
int bf;
node *lchild, *rchild;
friend class tree;
node(string y,string z)
{
keyw = y;
meaning = z;
bf = 0;
lchild = rchild=NULL;
}
};
class avltree
{
node *root;
public:
void display();
void inorder(node *);
int insert(string,string);
avltree()
{
root = NULL;
}
};
void avltree :: display()
{
inorder(root);
}
void avltree :: inorder(node *t)
{
if (t!= NULL)
{
inorder(t->lchild);
cout<<t->keyw<<" Balance Factor is "<<t->bf<<"\n";
inorder(t->rchild);
}
}
int avltree :: insert (string y1,string z)
{
node *a , *b , *c, *f, *p, *q, *y ;
int found , unbalanced, d ;
unbalanced = 1 ;
if (!root)
{
y = new node(y1,z);
root = y;
return(0);
}
f = q = NULL ;
found = 0 ;
a = p = root ;
while(p && !found )
{
if (p->bf)
{
a = p ;
f = q ;
}
if (y1 < p->keyw)
{
q = p ;
p = p->lchild ;
}
else if (y1> p->keyw)
{
q = p ;
p= p->rchild;
}
else
{
y = p ;
found = 1 ;
}
}
if (found!=1)
{
y = new node(y1,z) ;
if(y1< q->keyw)
q->lchild = y ;
else
q->rchild = y ;
if (y1>a->keyw)
{
p = a->rchild ;
b = p ;
d = -1 ;
}
else
{
p = a->lchild ;
b = p ;
d = 1 ;
}
while(p!= y)
{
if (y1<p->keyw)
{
p->bf = 1 ;
p = p->lchild ;
}
else
{
p->bf =-1 ;
p = p->rchild ;
}
}
if(!(a->bf)||!(a->bf+d))
{
a->bf += d ;
unbalanced = 0;
}
if(unbalanced)
{
if(d==1)
{
if(b->bf==1)
{
a->lchild = b->rchild ;
b->rchild = a ;
a->bf = b->bf = 0;
}
else
{
c = b ->rchild ;
b->rchild = c->lchild ;
a->lchild = c->rchild ;
c ->lchild = b ;
c->rchild = a;
switch(c-> bf)
{
case 1 :
a->bf = -1;
b-> bf = 0 ;
break ;
case -1 :
b->bf = 1 ; a ->bf = 0 ;
break ;
case 0 : a->bf = b->bf = 0 ;
break;
}
c->bf = 0 ;
b = c ;
}
}
else
{
if(b->bf==-1)
{
a->rchild = b->lchild ;
b->lchild = a ;
a->bf = b-> bf = 0 ;
}
else
{
c = b->lchild ;
b->lchild = c->rchild ;
a->rchild = c->lchild ;
c->rchild = b ;
c->lchild = a ;
switch (c->bf )
{
case 1: a->bf =0 ;
b->bf = -1 ;
break ;
case -1 : a->bf = +1;
b->bf = 0 ;
break ;
case 0 : a->bf=b->bf = 0;
break ;
}
c->bf = 0;
b= c ;
}
}
if (!f)
root = b ;
else if(a ==f->lchild)
f->lchild = b;
else if(a== f->rchild)
f->rchild = b ;
}
}
return 1 ;
}
int main()
{
fstream f1;
ifstream f2;
avltree a1;
int ch,opt,n;
string k,m;
do
{
cout<<"Program for AVL Tree"<<endl;
cout<<"1.Create/Insert \n2.Display"<<endl;
cout<<"Enter your Choice"<<endl;
cin>>ch;
switch (ch)
{
case 1: cout<<" Enter keyword to be entered - ";
cin.ignore();
cin>>k;
cout<<" Enter meaning to be entered - ";
cin.ignore();
cin>>m;
a1.insert(k,m);
break;
case 2 : a1.display();
break;
}
cout<<"Do you want to continue?? (Enter 1 to Continue)"<<endl;
cin>>opt;
}while(opt ==1);
return 0;
}
#include<stdio.h>
#include<string.h>
#include<fstream>
using namespace std;
class avltree;
class node
{
public:
string keyw;
string meaning;
int bf;
node *lchild, *rchild;
friend class tree;
node(string y,string z)
{
keyw = y;
meaning = z;
bf = 0;
lchild = rchild=NULL;
}
};
class avltree
{
node *root;
public:
void display();
void inorder(node *);
int insert(string,string);
avltree()
{
root = NULL;
}
};
void avltree :: display()
{
inorder(root);
}
void avltree :: inorder(node *t)
{
if (t!= NULL)
{
inorder(t->lchild);
cout<<t->keyw<<" Balance Factor is "<<t->bf<<"\n";
inorder(t->rchild);
}
}
int avltree :: insert (string y1,string z)
{
node *a , *b , *c, *f, *p, *q, *y ;
int found , unbalanced, d ;
unbalanced = 1 ;
if (!root)
{
y = new node(y1,z);
root = y;
return(0);
}
f = q = NULL ;
found = 0 ;
a = p = root ;
while(p && !found )
{
if (p->bf)
{
a = p ;
f = q ;
}
if (y1 < p->keyw)
{
q = p ;
p = p->lchild ;
}
else if (y1> p->keyw)
{
q = p ;
p= p->rchild;
}
else
{
y = p ;
found = 1 ;
}
}
if (found!=1)
{
y = new node(y1,z) ;
if(y1< q->keyw)
q->lchild = y ;
else
q->rchild = y ;
if (y1>a->keyw)
{
p = a->rchild ;
b = p ;
d = -1 ;
}
else
{
p = a->lchild ;
b = p ;
d = 1 ;
}
while(p!= y)
{
if (y1<p->keyw)
{
p->bf = 1 ;
p = p->lchild ;
}
else
{
p->bf =-1 ;
p = p->rchild ;
}
}
if(!(a->bf)||!(a->bf+d))
{
a->bf += d ;
unbalanced = 0;
}
if(unbalanced)
{
if(d==1)
{
if(b->bf==1)
{
a->lchild = b->rchild ;
b->rchild = a ;
a->bf = b->bf = 0;
}
else
{
c = b ->rchild ;
b->rchild = c->lchild ;
a->lchild = c->rchild ;
c ->lchild = b ;
c->rchild = a;
switch(c-> bf)
{
case 1 :
a->bf = -1;
b-> bf = 0 ;
break ;
case -1 :
b->bf = 1 ; a ->bf = 0 ;
break ;
case 0 : a->bf = b->bf = 0 ;
break;
}
c->bf = 0 ;
b = c ;
}
}
else
{
if(b->bf==-1)
{
a->rchild = b->lchild ;
b->lchild = a ;
a->bf = b-> bf = 0 ;
}
else
{
c = b->lchild ;
b->lchild = c->rchild ;
a->rchild = c->lchild ;
c->rchild = b ;
c->lchild = a ;
switch (c->bf )
{
case 1: a->bf =0 ;
b->bf = -1 ;
break ;
case -1 : a->bf = +1;
b->bf = 0 ;
break ;
case 0 : a->bf=b->bf = 0;
break ;
}
c->bf = 0;
b= c ;
}
}
if (!f)
root = b ;
else if(a ==f->lchild)
f->lchild = b;
else if(a== f->rchild)
f->rchild = b ;
}
}
return 1 ;
}
int main()
{
fstream f1;
ifstream f2;
avltree a1;
int ch,opt,n;
string k,m;
do
{
cout<<"Program for AVL Tree"<<endl;
cout<<"1.Create/Insert \n2.Display"<<endl;
cout<<"Enter your Choice"<<endl;
cin>>ch;
switch (ch)
{
case 1: cout<<" Enter keyword to be entered - ";
cin.ignore();
cin>>k;
cout<<" Enter meaning to be entered - ";
cin.ignore();
cin>>m;
a1.insert(k,m);
break;
case 2 : a1.display();
break;
}
cout<<"Do you want to continue?? (Enter 1 to Continue)"<<endl;
cin>>opt;
}while(opt ==1);
return 0;
}
No comments:
Post a Comment