Algorithm Alley
by Timothy Rolfe


Listing One
void BST::Insert( BSTnode* &Node, const Data &Value )
{
   if ( Node == NULL )  // failure point --- recursion base case
      Node = new BSTnode(Value);  // change Node (reference parameter)
   else if ( Value < Node->Value )
      Insert(Node->Left, Value);  // recurse left
   else                           // equal keys go right
      Insert(Node->Right, Value); // recurse right
}

Listing Two
void AVL::RotateRight(BasePtr &Rt)
// Rotate rightward --- right node moves down, left node moves up.
{  BasePtr  Lt = Rt->Left,
            Q  = Lt->Right;
   Lt->Right= Rt;
   Rt->Left = Q;
   HtAdjust (Lt);  // Shifting Q may well have changed Lt and Rt heights
   HtAdjust (Rt);
   Rt = Lt;        // Change the link itself that was passed by reference
}

Listing Three
void AVL::AVLadjust ( AVLnode* &Node )
{//We presume the AVL class has access to AVLnode's Height data member
   int Lht = Node->Left  == NULL ? -1 : Node->Left->Height,
       Rht = Node->Right == NULL ? -1 : Node->Right->Height,
       Diff = Lht - Rht;
   if ( abs(Diff) < 2 ) // AVL condition is met
      HtAdjust(Node);   // May need to adjust the height anyway
   else if ( Lht > Rht )// Left side two longer than right
   {  int Lck = Node->Left->Left  == NULL ? -1 : Node->Left->Left->Height,
          Rck = Node->Left->Right == NULL ? -1 : Node->Left->Right->Height;
      if ( Lck < Rck )
         RotateLeft (Node->Left); // Make left the longer
      RotateRight (Node);         // Adjust Node itself
      HtAdjust(Node);             // Update current node's height
   }
   else  // Mirror image logic to that above:  Right is two longer than left
   {  int Lck = Node->Right->Left  == NULL ? -1 : Node->Right->Left->Height,
          Rck = Node->Right->Right == NULL ? -1 : Node->Right->Right->Height;
      if ( Lck > Rck )
         RotateRight (Node->Right); 
      RotateLeft (Node); 
      HtAdjust(Node);
   }
}



1