AVL tree operations implementation

/*program of AVL tree implementation.
compiler- Turbo c++     author- Mangilal Sharma
--------------------------------------------------------*/
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>

struct avl_node
{
 avl_node * left;
 avl_node * right;
 avl_node * parent;
 int info;
};
avl_node * t;

class avl
{
 public:
 void insertval(avl_node **curr,int val,avl_node *par);
 void deleteval(avl_node **root,avl_node **curr);
 int  search(avl_node * curr,int val);
 void preorder(struct avl_node *root);
 void inorder(struct avl_node *root);
 void postorder(struct avl_node *root);
 void findval(avl_node **curr,int val,avl_node **del);
 avl_node *successor(avl_node* curr);
 void height(avl_node *curr,int &maxx);
 int balancefactor(avl_node *curr);
 void LLrotate(avl_node **curr);
 void RRrotate(avl_node **curr);
 avl();
};

avl_node* avl::successor(avl_node* curr)
{
 if(curr->right==NULL)
 return curr;
 curr = curr->right;
 while(curr->left !=NULL)
 curr = curr->left;
 return curr;
}

void avl::findval(avl_node **curr,int val,avl_node **del)
{
 if((*curr)!=NULL)
 {
  findval(&(*curr)->left,val,&(*del));
  if((*curr)->info==val)
  {
   (*del) = (*curr);
  }
  findval(&(*curr)->right,val,&(*del));
 }
}

void avl::height(avl_node *curr,int &maxx)
{
 static int cnt = 0;
 if(curr!=NULL)
 {
  cnt++;
  height(curr->left,maxx);
  height(curr->right,maxx);
  cnt--;
 }
}

int avl::balancefactor(avl_node *curr)
{
 int h_left=0,h_right=0;
 height(curr->left,h_left);
 height(curr->right,h_right);
 return(h_left - h_right);
}

void avl::preorder(struct avl_node *root)
{
 if(root!=NULL)
 {
  cout<<root->info<<" ";
  preorder(root->left);
  preorder(root->right);
 }
}

void avl::inorder(struct avl_node *root)
{
 if(root!=NULL)
 {
  inorder(root->left);
  cout<<root->info<<" ";
  inorder(root->right);
 }
}

void avl::postorder(struct avl_node *root)
{
 if(root!=NULL)
 {
  postorder(root->left);
  postorder(root->right);
  cout<<root->info<<" ";
 }
}

void avl::LLrotate(avl_node **curr)
{
 avl_node *child = (*curr)->left;
 child->parent = (*curr)->parent;
 if((*curr)->parent!=NULL);
 {
  if((*curr)==(*curr)->parent->left)
  (*curr)->parent->left = child;
  else
  (*curr)->parent->right = child;
 }
 (*curr)->parent = child;
 (*curr)->left = child->right;
 child->right = (*curr);
}

void avl::RRrotate(avl_node **curr)
{
 avl_node *child = (*curr)->right;
 child->parent = (*curr)->parent;
 if((*curr)->parent!=NULL);
 {
  if((*curr)==(*curr)->parent->left)
  (*curr)->parent->left = child;
  else
  (*curr)->parent->right = child;
 }
 (*curr)->parent = child;
 (*curr)->right = child->left;
 child->left = (*curr);
}

void avl::insertval(avl_node **curr,int val,avl_node *par)
{
 if(*curr==NULL)
 {
  avl_node* temp = new avl_node;
  temp->info = val;
  temp->left = (avl_node*)NULL;
  temp->right = (avl_node*)NULL;
  *curr = temp;
  (*curr)->parent = par;
  cout<<"Node inserted
";
  if(par!=NULL)
  cout<<"Its parent is "<<par->info;
  temp = *curr;
  while(temp!=NULL&&abs(balancefactor(temp))<2)
  temp = temp->parent;
  if(balancefactor(temp)==2)
  {
   if(balancefactor(temp->left)==1) //LL rotation...
   {
    LLrotate(&temp);
   }
   else if(balancefactor(temp->left)==-1) //LR rotation...
   {
    t = temp;
    RRrotate(&(temp->left));
    LLrotate(&t);
    temp = t;
   }
  }
  else if(balancefactor(temp)==-2)
  {
   if(balancefactor(temp->right)==-1) //RR rotation...
   {
    RRrotate(&temp);
   }
   else if(balancefactor(temp->right)==1) //RL rotation...
   {
    t =  temp;
    LLrotate(&(temp->right));
    RRrotate(&t);
    temp = t;
   }
  }
 }
 else if((*curr)->info>val)
 {
  insertval(&(*curr)->left,val,*curr);
 }
 else if((*curr)->info<val)
 {
  insertval(&(*curr)->right,val,*curr);
 }
 else
 cout<<"
Node already Exists...";
}

int avl::search(avl_node * curr,int val)
{
 int k=0;
 if(curr!=NULL)
 {
  search(curr->left,val);
  if(val==curr->info)
  {
   k++;
  }
  search(curr->right,val);
 }
 return k;
}

void avl::deleteval(avl_node **root,avl_node **curr)
{
 avl_node *y,*x;
 if(((*curr)->left==NULL)||((*curr)->right==NULL))
   y = (*curr);
 else
   y = successor((*curr));

 if(y->left != NULL)
    x = y->left;
 else
    x = y->right;

 if(x != NULL)
   x->parent = y->parent;

 if(y->parent == NULL)
   (*root) = x;
 else if(y == y->parent->left)
    y->parent->left = x;
 else
    y->parent->right = x;

 if(y != (*curr))
    (*curr)->info = y->info;
}

avl::avl()
{
 avl_node* root;
 root = (avl_node*)NULL;
 clrscr();
 int ch;
 do
 {
  cout<<"
AVL TREE
";
  cout<<" 1. Insert element
";
  cout<<" 2. Preorder Traversing
";
  cout<<" 3. Inorder Traversing
";
  cout<<" 4. Postorder Traversing
";
  cout<<" 5. Delete element
";
  cout<<" 6. Search
";
  cout<<" 7. To main page
";
  cout<<" 8. Exit
";
  cout<<" Enter ur choice:";
  cin>>ch;
  int value;
  avl_node *temp = NULL;
  switch(ch)
  {
   case 1:
 cout<<"
Enter the value to insert:";
 cin>>value;
 insertval(&root,value,NULL);
 break;
   case 2:
 preorder(root);break;
   case 3:
 inorder(root);break;
   case 4:
 postorder(root);break;
   case 5:
 cout<<"
Enter the value to delete:";
 cin>>value;
 temp = NULL;
 findval(&root,value,&temp);
 if(temp == NULL)
 {
  cout<<"
The value does not exist:";
  getch();
  break;
 }
 deleteval(&root,&temp);
 break;
   case 6:
 cout<<"
Enter the element to search:";
 int val;
 cin>>val;
 int n=search(root,val);
 if(n==1) cout<<"
Element "<<val<<" Exist in the tree";
 else     cout<<"
Element "<<val<<" not found in the tree";
 break;
   case 7:
 return;
   case 8:
 exit(1);
   default:
 cout<<"
Enter a valid choice:";
  }
 }while(1);
}
/*=========================15Nov.,2010=============================*/

Related Post: