AVL Tree Complete Code | Insert ,Balance,Rotations,Deletion,Display Functions.

 

What is the 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

 then one for all nodes. An Example Tree is an AVL Tree.


avl tree



C++ Example Of AVL Tree ....



#include<iostream>
using namespace::std;

class avl_node{
 public:
  int data;
  avl_node* left;
  avl_node* right;
  avl_node(){
   data=0;
   left=NULL;
   right=NULL;
  }
 void setData(int a)
 {
    this->data=a;
 }
 int getData()
 {
  return data;
 }
 void setLeft(avl_node* nextPointer)
 {
   this->left=nextPointer;
 }
 avl_node* getLeft()
 {
   return left;
 }
 void setRight(avl_node* nextPointer)
 {
  this->right=nextPointer;
 }
 avl_node* getRight()
 {
   return right;
 }
 bool isLeaf(int value)
 {
  if(this->left==NULL&&this->right==NULL)
  {
   return true;
  }
  else{
   return false;
  }
 }
};


class avlTree{
    public:
  avl_node *root;
  int height(avl_node*);
  int diff(avl_node*);
  avl_node *rr_rotation(avl_node*);
  avl_node *ll_rotation(avl_node*);
  avl_node *lr_rotation(avl_node*);
  avl_node *rl_rotation(avl_node*);

  avl_node * balance(avl_node*);
  avl_node* insert(avl_node*,int);
  avl_node* getSuccessor(avl_node*);
     deleteNode(int);
  void inorder(avl_node*);
  void postorder(avl_node*);
  void preorder(avl_node*);
  avlTree()
  {
     root=NULL;
  }
 
 };
 int avlTree::height(avl_node *temp)
 {
   int h=0;
   if(temp!=NULL)
   {
     int l_height=height(temp->left);
     int r_height=height(temp->right);
     int max_height=max(l_height,r_height);
     h=max_height+1;
   }
    return h;
 }
 int avlTree::diff(avl_node * temp)
 {
   int l_height=height(temp->left);
   int r_height=height(temp->right);
   int b_factor=l_height-r_height;
   return b_factor;
 }
 avl_node* avlTree::ll_rotation(avl_node * parent)
{
  avl_node* temp;
 temp=parent->left;
 parent->left=temp->right;
 temp->right=parent;
 return temp;
   }
 avl_node* avlTree::rr_rotation(avl_node * parent)
{
  avl_node* temp;
 temp=parent->right;
 parent->right=temp->left;
 temp->left=parent;
 return temp;
   }
avl_node *avlTree::lr_rotation(avl_node *parent)
{
  avl_node *temp;
  temp=parent->left;
  parent->left=rr_rotation(temp);
  return ll_rotation(parent);
}
 avl_node* avlTree::rl_rotation(avl_node *parent)
 {
    avl_node* temp;
    temp=parent->right;
    parent->right=ll_rotation(temp);
    return rr_rotation(parent);
 }

  avl_node* avlTree::balance(avl_node *temp)
  {
   int bal_factor=diff(temp);
   if(bal_factor>1)
   {
    if(diff(temp->left)>0)
    temp=ll_rotation(temp);
    else
    temp=lr_rotation(temp);
   
   }
   else if(bal_factor<-1)
   {
     if(diff(temp->right)>0)
     temp=rl_rotation(temp);
     else
      temp=rr_rotation(temp);
   }
   return temp;
  }
   avl_node* avlTree::insert(avl_node *root,int value)
   {
     if(root==NULL)
     {
       root=new avl_node;
       root->data=value;
       root->left=NULL;
       root->right=NULL;
       return root;
     }
   else if(value<root->data)
   {
       root->left=insert(root->left,value);
       root=balance(root);
   }
   else if(value>=root->data)
   {
      root->right=insert(root->right,value);
      root=balance(root);
   }
 }
 void avlTree::inorder(avl_node *tree)
 {
   if(tree==NULL)
   return;
   inorder(tree->left);
   cout<<" "<<tree->data;
   inorder(tree->right);
 }
 void avlTree::postorder(avl_node *tree)
 {
   if(tree==NULL)
   return;
   inorder(tree->left);
   inorder(tree->right);
   cout<<" "<<tree->data;
 }
  void avlTree::preorder(avl_node *tree)
 {
   if(tree==NULL)
   return;
    cout<<" "<<tree->data;
   inorder(tree->left);
   inorder(tree->right);
 }
 avlTree::deleteNode(int r)
{
  avl_node* curr=root;
  avl_node* currP;
  bool goLeft=false;
  while(curr!=NULL)
  {
  
      if(curr->data==r){
       break;
   }
   else if(curr->data>r)
      {
       currP=curr;
     curr=curr->left;
        goLeft=true;
   }
   else if(curr->data<r)
   {
    currP=curr;
     curr=curr->right;
     goLeft=false;
   }
  }
  if(curr==NULL)
  {
     cout<<"Node Not Found !"<<endl;
     return 0;
  }
  if(curr->left==NULL&&curr->right==NULL)
  {
   cout<<"Case 1 ."<<endl;
   cout<<endl<<"Node With Value "<<r<<" Deleted !"<<endl;
     currP->left=currP->right=NULL;
     delete curr;
     root=balance(root);
  }
  else if(curr->right==NULL&&curr->left!=NULL)
  {
      cout<<"Case 2 ."<<endl;
      cout<<endl<<"Node With Value "<<r<<" Deleted !"<<endl;
      if(!goLeft)
      currP->right=curr->left;
      else
      currP->left=curr->left;
      curr->left=NULL;
      delete curr;
      root=balance(root);
    
  }
   else if(curr->right!=NULL&&curr->left==NULL)
  {
      cout<<"Case 3 ."<<endl;
      cout<<endl<<"Node With Value "<<r<<" Deleted !"<<endl;
      if(goLeft)
      currP->left=curr->right;
      else
      currP->left=curr->right;
   curr->right=NULL;
      delete curr;
      root=balance(root);
    
  }
       else {
               cout<<"Case 4 ."<<endl;
      cout<<endl<<"Node With Value "<<r<<" Deleted !"<<endl;
             avl_node* successor = getSuccessor(curr);
             if(curr == root){
                root = successor;
             }

             if(goLeft){
                currP->left = successor;
             }else{
               currP->right = successor;
             }

             successor->left= curr->left;
             delete curr;
             root=balance(root);
         }
     
        }
   

avl_node* avlTree::getSuccessor(avl_node *delNode){

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

 int main()
 {
    int choice,item;
    avlTree avl;
    while(1)
    {
        cout<<"\n-----------------------"<<endl;
        cout<<"AVL Tree Implementation|"<<endl;
        cout<<"-----------------------"<<endl;
        cout<<"1. Insert Element Into The Tree "<<endl;
        cout<<"2. Inorder Traversal"<<endl;
        cout<<"3. Preorder Traversal "<<endl;
           cout<<"4. Postorder Traversal"<<endl;
           cout<<"5. Display Root "<<endl;
     cout<<"6. Delete Node "<<endl;
     cout<<"7. Exit"<<endl;
           cout<<"Enter Your Choice :";
              cin>>choice;
              switch(choice)
              {
                case 1:
                 cout<<endl<<"Enter Value To Be Inserted : ";
                 cin>>item;
                 avl.root=avl.insert(avl.root,item);
                 break;
   case 2:
      cout<<endl<<"Inorder Traversal :"<<endl;
      avl.inorder(avl.root);
      cout<<endl;
      break;
   case 3:
      cout<<endl<<"Preorder Traversal :"<<endl;
      avl.preorder(avl.root);
      cout<<endl;
      break;
   case 4:
      cout<<endl<<"PostOrder Traversal :"<<endl;
      avl.postorder(avl.root);
      cout<<endl;
      break;
   case 5:
        cout<<endl<<"Displaying Root : "<<avl.root->data;
        break;
   case 6:
          int r;
         cout<<endl<<"Enter Id Of Node To Delete : ";
         cin>>r;
         avl.deleteNode(r);
         break;
   case 7:
         break;
   default:
      cout<<endl<<"Wrong Choice "<<endl;
     }
  }
  return 0;
}


avl tree


Post a Comment

0 Comments