AVLtree

From Minor Miracle Software
Jump to: navigation, search

AVLtree

// AVL binary tree
// Jesse B. Dooley
// (c) 26 May 1996

// template tree class
// strict binary search tree
// The following overloaded operators are
// assumed for the T data type.
// <  LESS THAN
// >  greater than
// == equals
// << OUTPUT STREAM
// >> input stream
// =  assignment

// avl_tree.cc

#ifndef  AVL_TREE_CC
#define AVL_TREE_CC


#ifndef STACK_CC
  #include "stack.cc"
#endif


template<CLASS T> class treenode {

      friend class avl_tree<T>;

friend istream& operator >> (istream& IS, treenode<T> &A)
{
     if( IS )
     {
         IS >> A.Tdata;
     }
     return IS;
}

friend ostream& operator << (OSTREAM& OS, TREENODE<T> &A)
{
    OS << A.TDATA;
    RETURN OS;
}

PUBLIC:

      T TDATA;
      UNSIGNED LONG ULLEFTHEIGHT;
      UNSIGNED LONG ULRIGHTHEIGHT;
      TREENODE<T> *Left, *Right;

treenode()
{
     ulLeftHeight = 0;
     ulRightHeight = 0;
     Left = NULL;
     Right = NULL;
}

treenode(const treenode<T> &A)
{
     Tdata = A.Tdata;
     ulLeftHeight = A.ulLeftHeight;
     ulRightHeight = A.ulRightHeight;
     Left = A.Left;
     Right = A.Right;
}

~treenode(){}


treenode operator  = (const treenode<T> &A)
{
     Tdata = A.Tdata;
     ulLeftHeight = A.ulLeftHeight;
     ulRightHeight = A.ulRightHeight;
     Left = A.Left;
     Right = A.Right;
     return *this;
}

T getdata()
{
  return Tdata;
}
};



template<CLASS T> class avl_tree: public treenode<T> {

   enum TranverseType{INORDER, PREORDER, POSTORDER, REVERSE};

   enum LeftRight{LEFT,RIGHT};

   treenode<T> *Root, *Current;

   unsigned long m_ulPopulation;
   TranverseType m_TranverseType;
   stack<TREENODE<T>*> m_stackTreePath;
   stack<LEFTRIGHT> m_stackLeftRight;

friend istream& operator >> (istream& IS, avl_tree<T> &A)
{
    T temp;
    IS >> temp;
    A += temp;
    return IS;
}

friend ostream& operator << (OSTREAM& OS, CONST AVL_TREE<T> &Q)
{
   if ( Q.Root )
   {
      switch (Q.m_TranverseType) {
            case INORDER:
                 printinorder(OS, Q.Root);
                 break;
            case PREORDER:
                 printpreorder(OS, Q.Root);
                 break;
            case POSTORDER:
                 printpostorder(OS, Q.Root);
                 break;
            case REVERSE:
                 printreverse(OS, Q.Root);
                 break;
            default:
               ;
      }
      return OS;
   }
   return OS;
}

void avlbalancetree()
{
    long l_avlbalance = calc_avlbalance( Current ); //Current->avl_balance;
    if ( !m_stackTreePath.isempty() )
    {
        if(l_avlbalance > 1)  // left rotation
           rotate_left();
        if(l_avlbalance < -1) // RIGHT ROTATION
           ROTATE_RIGHT();
        CURRENT = M_STACKTREEPATH.POP();
        LEFTRIGHT LR_TEMP = M_STACKLEFTRIGHT.POP();
        AVLBALANCETREE();
    }
    ELSE
    {
       IF(L_AVLBALANCE > 1)  // left rotation
         rotate_left();
       if(l_avlbalance < -1) // RIGHT ROTATION
         ROTATE_RIGHT();
    }
}

LONG CALC_AVLBALANCE(TREENODE<T>* ptr)
{
  if(ptr)
  {
      ptr->ulLeftHeight = getreeheight( ptr->Left );
      ptr->ulRightHeight = getreeheight( ptr->Right );
      return (long)(ptr->ulRightHeight - ptr->ulLeftHeight);
  }
  return 0;
} // calc_avlbalance

unsigned long getreeheight( treenode<T>* P )
{
  if( P )
  {
    return (P->ulLeftHeight > P->ulRightHeight) ? (P->ulLeftHeight + 1) : (P->ulRightHeight + 1);
  }
  return 0;
}// getreeheight

void copynode(treenode<T> *ptrn, treenode<T> *ptr )
{
   if(ptr)
   {
	 ptrn = new treenode<T>;
	 ptrn->Tdata = ptr->Tdata;
	 ptrn->Left = ptr->Left;
	 ptrn->Right = ptr->Right;
     copynode( ptrn->Left, ptr->Left );
     copynode( ptrn->Right, ptr->Right );
   }
} // copynode

void deletenode( treenode<T>* P )
{
   if ( P )
   {
    deletenode( P->Left );
    deletenode( P->Right );
    delete P;
   }
} // deletenode

void getleft()
{
   m_stackTreePath.push( Current );
   m_stackLeftRight.push( LEFT );
   Current = Current->Left;
} // getleft

void getparent()
{
   Current = m_stackTreePath.pop();
}

void getright()
{
   m_stackTreePath.push( Current );
   m_stackLeftRight.push( RIGHT );
   Current = Current->Right;
} // getright

void getroot ()
{
   Current = Root;
   m_stackTreePath.erase();
   m_stackLeftRight.erase();
} // getroot

void rotate_left( )
{
    if (Current == Root)  // rotate the root
    {
        Root = Current->Right;
        Current->Right = Root->Left;
        Current->ulRightHeight = getreeheight( Current->Right );
        Root->Left = Current;
        Root->ulLeftHeight = getreeheight( Root->Left );
    }
    else // rotate subroot
    {
        LeftRight lr_Temp = m_stackLeftRight.top();
        treenode<T> *p_Parent = m_stackTreePath.top();
        treenode<T> *p_CurrentR = Current->Right;
        if (lr_Temp == LEFT)
        {
           p_Parent->Left = Current->Right;
           Current->Right = p_CurrentR->Left;
           Current->ulRightHeight = getreeheight( Current->Right );
           p_CurrentR->Left = Current;
           p_CurrentR->ulLeftHeight = getreeheight( p_CurrentR->Left );
           Current = p_Parent->Left;
           p_Parent->ulLeftHeight = getreeheight( p_Parent->Left );
        }
        else
        {
           p_Parent->Right = Current->Right;
           Current->Right = p_CurrentR->Left;
           Current->ulRightHeight = getreeheight( Current->Right );
           p_CurrentR->Left = Current;
           p_CurrentR->ulLeftHeight = getreeheight( p_CurrentR->Left );
           Current = p_Parent->Right;
           p_Parent->ulRightHeight = getreeheight( p_Parent->Right );
        }
    }
}

void rotate_right()
{
    if (Current == Root)  // rotate the root
    {
        Root = Current->Left;
        Current->Left = Root->Right;
        Current->ulLeftHeight = getreeheight( Current->Left );
        Root->Right = Current;
        Root->ulRightHeight = getreeheight( Root->Right );
    }
    else // rotate subroot
    {
        LeftRight lr_Temp = m_stackLeftRight.top();
        treenode<T> *p_Parent = m_stackTreePath.top();
        treenode<T> *p_CurrentL = Current->Left;
        if (lr_Temp == LEFT)
        {
            p_Parent->Left = Current->Left;
            Current->Left = p_CurrentL->Right;
            Current->ulLeftHeight = getreeheight( Current->Left );
            p_CurrentL->Right = Current;
            p_CurrentL->ulRightHeight = getreeheight( p_CurrentL->Right );
            Current = p_Parent->Left;
            p_Parent->ulLeftHeight = getreeheight( p_Parent->Left );
        }
        else
        {
            p_Parent->Right = Current->Left;
            Current->Left = p_CurrentL->Right;
            Current->ulLeftHeight = getreeheight( Current->Left );
            p_CurrentL->Right = Current;
            p_CurrentL->ulRightHeight = getreeheight( p_CurrentL->Right );
            Current = p_Parent->Right;
            p_Parent->ulRightHeight = getreeheight( p_Parent->Right );
        }
    }
}

int searchtree( T Xname )
{
   if (Current == NULL)
      return 0;
   else
   {
         if ( Current->Tdata == Xname)
            return 1;
         else if (Current->Tdata < XNAME)
         {
            GETRIGHT();
            RETURN SEARCHTREE (XNAME);
         }
         ELSE
         {
            GETLEFT();
            RETURN SEARCHTREE (XNAME);
         }
   }
} // SEARCHTREE

VOID DEL( )
{
	IF ( CURRENT == ROOT )
	{
		IF ( CURRENT->Right != NULL )
		{
			Root = Current->Right;
			Root->Right = NULL;
	    }
	    else
			Root = NULL;
	}
	else
	{
	   treenode<T>* Parent = m_stackTreePath.top();
	   LeftRight lr_Temp = m_stackLeftRight.top();
	   if ( lr_Temp == RIGHT )
	   {
 			Parent->Right = Current->Right;
            delete Current;
            Current = Parent->Right;
       }
       else
       {
			Parent->Left = Current->Right;
            delete Current;
            Current = Parent->Left;
	   }
	}
    m_ulPopulation--;
    avlbalancetree();
}  // del

friend ostream& printinorder(ostream& OS, treenode<T>* Q)
{
   if ( Q )
   {
      printinorder( OS, Q->Left );
      OS << Q->Tdata << ENDL;
      PRINTINORDER(OS, Q->Right);
      return OS;
   }
   return OS;
}

friend ostream& printpostorder(ostream& OS, treenode<T>* Q)
{
   if ( Q )
   {
      printpostorder(OS, Q->Left);
      printpostorder(OS, Q->Right);
      OS << Q->Tdata;
      return OS;
   }
   return OS;
}

friend ostream& printpreorder(ostream& OS, treenode<T>* Q)
{
   if ( Q )
   {
      OS << Q->Tdata;
      printpreorder(OS, Q->Left);
      printpreorder(OS, Q->Right);
      return OS;
   }
   return OS;
}

friend ostream& printreverse(ostream& OS, treenode<T>* Q)
{
   if ( Q )
   {
      printreverse(OS, Q->Right);
      OS << Q->Tdata;
      printreverse(OS, Q->Left);
      return OS;
   }
   return OS;
}

public:

avl_tree()
{
   Root = NULL;
   Current = NULL;
   m_ulPopulation = 0;
   m_TranverseType = INORDER;
}

~avl_tree ()
{
   if ( Root )
   {
    deletenode( Root->Left );
    deletenode( Root->Right );
    delete Root;
   }
}

avl_tree(const avl_tree<T> &n)
{
   if (n.Root)
   {
      Root = new treenode<T>;
      Root->Tdata = n.Root->Tdata;
      Root->ulLeftHeight = n.Root->ulLeftHeight;
      Root->ulRightHeight = n.Root->ulRightHeight;
      Current = n.Current;
      m_ulPopulation = n.m_ulPopulation;
      m_TranverseType = n.m_TranverseType;
      m_stackTreePath = n.m_stackTreePath;
      m_stackLeftRight = n.m_stackLeftRight;
      treenode<T> *currL = n.Root->Left;
      treenode<T> *currR = n.Root->Right;
      copynode( Root->Left, currL );
      copynode( Root->Right, currR );
   }
   else
   {
     Root = NULL;
     Current = NULL;
     m_ulPopulation = 0;
     m_TranverseType = INORDER;
   }
}

void erase()
{
   if ( Root )
   {
    deletenode( Root->Left );
    deletenode( Root->Right );
    delete Root;
   }
   Root = NULL;
   Current = NULL;
   m_ulPopulation = 0;
   m_stackTreePath.erase();
   m_stackLeftRight.erase();
}

T* returncurrent()
{
   if (Current)
      return &Current->Tdata;
   return NULL;
}

int operator += ( T Temp )
{
    if(!locate( Temp ))
    {
        treenode<T> *tempnode = new treenode<T>;
        if ( tempnode == NULL )
            return 0;

        tempnode->Tdata = Temp;
        tempnode->ulLeftHeight = 0;
        tempnode->ulRightHeight = 0;
        tempnode->Left = NULL;
        tempnode->Right = NULL;
        if ( Root == NULL )
        {
            Root = tempnode;
            Current = tempnode;
        }
        else
        {
           treenode<T>* p_Parent = m_stackTreePath.top();
           if ( p_Parent->Tdata > Temp )
           {
                p_Parent->Left = tempnode;
                m_stackLeftRight.push( LEFT );
           }
       	   else
       	   {
       	        m_stackLeftRight.push( RIGHT );
                p_Parent->Right = tempnode;
           }
        }
        Current = tempnode;
        m_ulPopulation++;
        avlbalancetree();
        return 1;
    }
    getroot();
    return 0;
}

void operator -= (  T &U )
{
   if (locate( U ))
   {
      treenode<T> *current, *parent;
      if ( Current->Left != NULL )
      {
         parent = Current;
         current = Current->Left;
		 while ( current->Right != NULL )
		 {
                m_stackTreePath.push( parent );
                m_stackLeftRight.push( RIGHT );
                parent = current;
                current = current->Right;
         }
         Current->Tdata = current->Tdata;
		 Current = current;
         parent->Right = current->Left;
         delete current;
         avlbalancetree();
         m_ulPopulation--;
      }
      else
         del();
   }
}


avl_tree<T> operator=( const avl_tree<T> &n )
{
   if (n.Root)
   {
      Root = new treenode<T>;
      Root->Tdata = n.Root->Tdata;
      Current = n.Current;
      m_ulPopulation = n.m_ulPopulation;
      m_TranverseType = n.m_TranverseType;
      m_stackTreePath = n.m_stackTreePath;
      m_stackLeftRight = n.m_stackLeftRight;
      treenode<T> *currL = n.Root->Left;
      treenode<T> *currR = n.Root->Right;
      copynode( Root->Left, currL );
      copynode( Root->Right, currR );
   }
   else
   {
     Root = NULL;
     Current = NULL;
     m_ulPopulation = 0;
     m_TranverseType = INORDER;
   }
   return *this;
}

unsigned long census()
{
    return m_ulPopulation;
}

int isempty()
{
   return (Root == NULL);
} // isempty

int locate ( T Yname )
{
   getroot();
   return searchtree ( Yname );
} // locate

int printkey(ostream& OS, T i_Nodes )
{
    if(locate( i_Nodes ))
    {
       OS << CURRENT->Tdata;
       return 1;
    }
    return 0;
}

int returncurrent ( T &B )
{
    if ( Current )
    {
        B = Current->Tdata;
        return 1;
    }
    return 0;
} // returncurrent

void set_Tree_INORDER()
{
   m_TranverseType = INORDER;
}

void set_Tree_PREORDER()
{
   m_TranverseType = PREORDER;
}

void set_Tree_POSTORDER()
{
   m_TranverseType = POSTORDER;
}

void set_Tree_REVERSE()
{
   m_TranverseType = REVERSE;
}

};
#endif  // AVL_TREE_CC


Internal Links

Parent Article: Main Page