Thursday, July 11, 2013

Simple AVL Tree – C++.




#include <iostream.h>
#define FALSE 0
#define TRUE 1

  class Avl_Tree
      {
          char Data;
          Avl_Tree *Left;
          Avl_Tree *Right;
          int status;
          public:
  Avl_Tree * Right_Bal(Avl_Tree *Root, int *Num)
      {
          Avl_Tree *Ptr1, *Ptr2;
          switch(Root->status)
             {
                 case -1:
                      Root->status = 0;
                      break;
                 case 0:
                      Root->status = 1;
                      *Num= FALSE;
                      break;
                 case 1:
                      Ptr1 = Root->Right;
                      if(Ptr1->status >= 0)
                         {
                             Root->Right= Ptr1->Left;
                             Ptr1->Left = Root;
                             if(Ptr1->status == 0)
                                {
                                     Root->status = 1;
                                     Ptr1->status = -1;
                                     *Num = FALSE;
                                }
                             else
                                {
                                     Root->status = Ptr1->status = 0;
                         }
                      Root = Ptr1;
                 }
             else
                 {
                      Ptr2 = Ptr1->Left;
                      Ptr1->Left = Ptr2->Right;
                      Ptr2->Right = Ptr1;
                      Root->Right = Ptr2->Left;
                      Ptr2->Left = Root;
                      if(Ptr2->status == 1)
                         Root->status = -1;
                      else
                         Root->status = 0;
                      if(Ptr2->status == -1)
                         Ptr1->status = 1;
                      else
                         Ptr1->status = 0;
                      Root = Ptr2;
                      Ptr2->status = 0;
                 }
             }
          return(Root);
      }

  Avl_Tree * Left_Bal(Avl_Tree *Root, int *Num)
      {
          Avl_Tree *Ptr1, *Ptr2;

          switch(Root->status)
             {
                 case 1:
                      Root->status = 0;
                      break;
                 case 0:
                      Root->status = -1;
                      *Num= FALSE;
                      break;
                 case -1:
                     Ptr1 = Root->Left;
                      if(Ptr1->status <= 0)
                         {
                             Root->Left= Ptr1->Right;
                             Ptr1->Right = Root;
                             if(Ptr1->status == 0)
                                {
                                     Root->status = -1;
                                     Ptr1->status = 1;
                                     *Num = FALSE;
                                }
                             else
                                {
                                     Root->status = Ptr1->status = 0;
                                }
                             Root = Ptr1;
                         }
                      else
                         {
                             Ptr2 = Ptr1->Right;
                             Ptr1->Right = Ptr2->Left;
                             Ptr2->Left = Ptr1;
                             Root->Left = Ptr2->Right;
                             Ptr2->Right = Root;

                             if(Ptr2->status == -1)
                                Root->status = 1;
                             else
                                Root->status = 0;

                             if(Ptr2->status == 1)
                                Ptr1->status = -1;
                             else
                                Ptr1->status = 0;
                                Root = Ptr2;
                                Ptr2->status = 0;
                         }
             }
          return(Root);
      }


  Avl_Tree * Replace(Avl_Tree *R, Avl_Tree *Tmp, int *Num)
      {
          Avl_Tree *rNode = R;
          if( R->Right != NULL)
             {
                 R->Right = Replace(R->Right, Tmp, Num);
                 if(*Num)
                      R = Left_Bal(R, Num);
             }
          else
             {
                 rNode = R;
                 Tmp->Data = R->Data;
                 R = R->Left;
                 delete(rNode);
                 *Num = TRUE;
             }
          return(R);
      }


  Avl_Tree *  Insert (char Data, Avl_Tree *Root, int *Num)
      {
          Avl_Tree *Ptr1;
          Avl_Tree *Ptr2;
          if(!Root)
             {
                 Root = new Avl_Tree();
                 Root->Data = Data;
                 Root->Left = NULL;
                 Root->Right = NULL;
                 Root->status = 0;
                 *Num = TRUE;
                 return (Root);
             }

          if(Data < Root->Data)
             {
                 Root->Left = Insert(Data, Root->Left, Num);
                 if(*Num)
                      {
                         switch(Root->status)
                             {
                                case 1:
                                     Root->status = 0;
                                     *Num = FALSE;
                                     break;
                                case 0:
                                     Root->status = -1;
                                     break;
                                case -1:
                                     Ptr1 = Root->Left;
                                     if(Ptr1->status == -1)
                                          {
                                                Root->Left= Ptr1->Right;
                                                Ptr1->Right = Root;
                                                Root->status = 0;
                                                Root = Ptr1;
                                          }
                                     else
                                          {
                                                Ptr2 = Ptr1->Right;
                                                Ptr1->Right = Ptr2->Left;
                                                Ptr2->Left = Ptr1;
                                                Root->Left = Ptr2->Right;
                                                Ptr2->Right = Root;
                                                if(Ptr2->status == -1)
                                                          Root->status = 1;
                                                else
                                                          Root->status = 0;
                                                if(Ptr2->status == 1)
                                                          Ptr1->status = -1;
                                                else
                                                          Ptr1->status = 0;
                                                          Root = Ptr2;
                                          }

                                     Root->status = 0;
                                     *Num = FALSE;
                             }
                      }
             }

          if(Data > Root->Data)
             {
                 Root->Right = Insert(Data, Root->Right, Num);
                 if(*Num)
                      {
                         switch(Root->status)
                             {
                                case -1:
                                     Root->status = 0;
                                     *Num = FALSE;
                                     break;
                                case 0:
                                     Root->status = 1;
                                     break;

                                case 1:
                                     Ptr1 = Root->Right;
                                     if(Ptr1->status == 1)
                                          {
                                                Root->Right= Ptr1->Left;
                                                Ptr1->Left = Root;
                                                Root->status = 0;
                                                Root = Ptr1;
                                          }
                                     else
                                          {
                                                Ptr2 = Ptr1->Left;
                                                Ptr1->Left = Ptr2->Right;
                                                Ptr2->Right = Ptr1;
                                                Root->Right = Ptr2->Left;
                                                Ptr2->Left = Root;
                                                if(Ptr2->status == 1)
                                                          Root->status = -1;
                                                else
                                                          Root->status = 0;
                                                if(Ptr2->status == -1)
                                                          Ptr1->status = 1;
                                                else
                                                          Ptr1->status = 0;
                                                          Root = Ptr2;
                                          }

                                     Root->status = 0;
                                     *Num = FALSE;
                             }
                      }
             }
          return(Root);
      }
      Avl_Tree *Del(Avl_Tree *Root, char Data, int *Num)
          {
             Avl_Tree *Tmp;
             if(!Root)
                 {
                      cout<<"\n\tEmpty Tree!!!\n";
                      return(Root);
                 }
             else
                 {
                      if (Data < Root->Data )
                         {
                             Root->Left = Del(Root->Left, Data, Num);
                             if(*Num)
                                Root = Right_Bal(Root, Num);
                         }
                      else
                         if(Data > Root->Data)
                             {
                                Root->Right = Del(Root->Right, Data, Num);
                                if(*Num)
                                     Root = Left_Bal(Root, Num);
                             }
                         else
                             {
                                Tmp= Root;
                                if(Tmp->Right == NULL)
                                     {
                                          Root = Tmp->Left;
                                          *Num = TRUE;
                                          delete(Tmp);
                                     }
                                else if(Tmp->Left == NULL)
                                     {
                                          Root = Tmp->Right;
                                          *Num = TRUE;
                                          delete(Tmp);
                                     }
                                else
                                     {
                                          Tmp->Left = Replace(Tmp->Left, Tmp, Num);
                                          if(*Num)
                                                Root = Right_Bal(Root, Num);
                                     }
                             }
                 }
          return(Root);
      }


  void Disp(Avl_Tree *Tnode,int Level)
      {
          int i;
          if (Tnode)
             {
                 Disp(Tnode->Right, Level+1);
                 cout<<Tnode->Data;
                 Disp(Tnode->Left, Level+1);
             }
      }

};

  int main()
      {
          int Num;
          char Data ;
          int ch;
          Avl_Tree AT;
          Avl_Tree *Tnode = new Avl_Tree;
          Tnode =  NULL;

          while(ch != 4)
             {
                 cout<<"\n\t1. Create \n\t2. Display \n\t3. Delete \n\t4. Exit";
                 cout<<"\n\tEnter the Choice ";
                 cin>>ch;
                 switch(ch)
                      {
                         case 1:
                             cout<<"\n\tEnter Data : " ;
                             cin>>Data;
                             Tnode = AT.Insert(Data, Tnode, &Num);
                             break;
                         case 2:
                             cout<<"\n\t Tree Elements : ";
                             AT.Disp(Tnode, 1);break;
                         case 3:
                             cout<<"\n\tEnter Data to Delete : ";
                             cin>>Data;
                             Tnode = AT.Del(Tnode, Data, &Num);
                             break;
                         case 4:
                             cout<<"\n\n\n\t\tQuiting....";
                             break;
                 }
             }
          return 0;
      }



Posted by at
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)