mapavl.template.cpp

The existed tree implementation

      if ( taller )
      {
         switch( tree->factor )          // Determine current balance type
         {
           case RH:                      // Now, left and right same height
              tree->factor = EQ;
              taller = false;
              return tree;

           case EQ:                      // Now, left 1 higher than right
              tree->factor = LH;
              taller = true;
              return tree;

           case LH:                      // Now, we must rebalance ourselves
              tree = leftBalance( tree );
              taller = false;
              return tree;
         }
      }

      // If the subtree is not taller, then this tree is not taller either. Just return it.
      return tree;
   }

   //  Last possibility, the value we want to insert is greater than the
   //  value stored in the current node, so insert in the right subtree

   tree->right = addNode( tree->right, key, taller );

   //  If the subtree grew in size, we must check to see if we are now
   //  unbalanced. As mentioned in class, there are three possible cases:
   //
   //  1. currently LH, so right subtree grew, so we are now EQ, and we
   //     report that this tree did not grow in height
   //  2. currently EQ, so right subtree grew, so we are now RH, and we
   //     report that this tree did grow in height
   //  3. currently RH, so right subtree grew, so we are out of balance,
   //     and must peform a rotation to bring ourselves back into balance
   //
   //  If the subtree didn't grow in size, than we didn't grow, either

   if ( taller )
   {
       switch( tree->factor )          // Determine current balance type
       {
          case LH:                      // Now, left and right same height
             tree->factor = EQ;
             taller = false;
             return tree;

          case EQ:                      // Now, right 1 higher than left
             tree->factor = RH;
             taller = true;
             return tree;

          case RH:                      // Now, we must rebalance ourselves
             tree = rightBalance( tree );
             taller = false;
             return tree;
       }
   }

  // If the subtree is not taller, then this tree is not taller either. Just return it.
  return tree;
}


template <class Key, class Value>
const Value& MapAVL<Key,Value>::operator[]( const Key& key ) const
// Pre: key is in the map
// Post: const reference to value corresponding to key has been returned
// Exception: if the key is not in the map, not_valid_key has been thrown
{
   MapAVLNode<Key,Value>* ptr;

   if (root == NULL)
   {
     throw not_valid_key();
   }

   ptr = root;

   while( true )
   {
     if (ptr->key == key)
     {
        return ptr->value;
     }

     if (ptr->key < key)
     {
        if (ptr->right == NULL)
        {
           throw not_valid_key();
        }
        ptr = ptr->right;
     }
     else
     {
        if (ptr->left == NULL)
        {
           throw not_valid_key();
        }
        ptr = ptr->left;
     }
   }
}


template <class Key, class Value>
void MapAVL<Key,Value>::dump( Pair<Key,Value>* data ) const
// Pre: array is an array of pairs of Key and Value
//      array must be at least size() elements long
// Post: key and value pairs have been written into the array
{
   dumpHelper( root, data );
}


template <class Key, class Value>
int MapAVL<Key,Value>::dumpHelper( MapAVLNode<Key,Value>* ptr, Pair<Key,Value>* data) const
// Helper function that stores the keys and values of a particular SUBTREE
//   into a user supplied array.
// PRE:  array is an array of at least size() elements long.
//
// POST: All <key,value> pairs in the subtree is written into the array.
//       The number of pairs written is returned as the function return value.
{
   int offset;

   if (ptr == NULL)
   {
      return 0;
   }

   if (ptr->left != NULL)
   {
      offset = dumpHelper(ptr->left, data );
   }
   else
   {
      offset = 0;
   }

   data[offset].setLeft( ptr->key );
   data[offset].setRight( ptr->value );

   offset++;

   return offset + dumpHelper(ptr->right, data + offset);
}


template <class Key, class Value>
void MapAVL<Key,Value>::copy( const MapAVL<Key,Value>& someMapAVL )
// Helper function used by MapAVL( const MapAVL& someMapAVL )
// and operator=( const MapAVL& someMapAVL )
// POST: The contents of 'someMapAVL' are copied into the current MapAVL
{
   count = someMapAVL.count;

   if (someMapAVL -> root == NULL)
   {
      root = NULL;
   }
   else
   {
      root = new MapAVLNode<Key,Value>;
      copySubTree(root, someMapAVL->root);
   }
}


template <class Key, class Value>
void MapAVL<Key,Value>::copySubTree( MapAVLNode<Key,Value>& root, const MapAVLNode<Key,Value>& otherRoot )
// Private helper function that copies all values from 'otherRoot' into this root,
//   including all children nodes.
// POST:  All childr nodes are copied from 'otherRoot' into 'root'.
{
   root->factor = otherRoot->factor;
   root->key = otherRoot->key;
   root->value = otherRoot->value;

   if (otherRoot->left != NULL)
   {
      root->left = new MapAVLNode<Key,Value>;
      copySubTree( root->left, otherRoot->left );
   }
   else
   {
      root->left = NULL;
   }

   if (otherRoot->right != NULL)
   {
      root->right = new MapAVLNode<Key,Value>;
      copySubTree( root->right, otherRoot->right );
   }
   else
   {
      root->right = NULL;
   }
}


template <class Key, class Value>
void MapAVL<Key,Value>::eraseTree( MapAVLNode<Key,Value>* ptr )
// Private helper function that deletes a node and all children.
// POST:  If the pointer is NULL, then nothing happens.
//        otherwise, the node and all children are deleted.
{
   if (ptr != NULL)
   {
      eraseTree( ptr -> left );
      eraseTree( ptr -> right );
      delete ptr;
   }
}


template <class Key, class Value>
MapAVLNode<Key,Value>* MapAVL<Key,Value>::leftBalance( MapAVLNode<Key,Value>* tree )
// Private helper function that performs with a LL or a LR rotation on a node.
{
   MapAVLNode<Key,Value>* left_sub;                     // Pointer to left subtree root

   left_sub = tree->left;

   //  There are three possible balance types for the left subtree, and
   //  the type of rotation we perform depends on this, namely:
   //
   //  1. left subtree is LH, so perform an LL rotation
   //  2. left subtree is RH, so perform an LR rotation
   //  3. left subtree is EQ (this can only happen during deletion), so
   //     perform an LL rotation

   switch( left_sub -> factor )
   {
     case LH:
       tree->factor = EQ;
       left_sub->factor = EQ;
       return LL_rotate( tree );

     case RH:
       tree->factor = EQ;
       left_sub->factor = EQ;
       left_sub->right->factor = EQ;
       return LR_rotate( tree );

     default:  // case EQ:
       tree->factor = LH;
       left_sub->factor = RH;
       return LL_rotate( tree );
   }
}


template <class Key, class Value>
MapAVLNode<Key,Value>* MapAVL<Key,Value>::LL_rotate( MapAVLNode<Key,Value>* tree )
// Private helper function that performs with a LL rotation on a node.

   //  This private method performs an LL rotation. This means that we have
   //  the following situation:
   //
   //          1(-2)             2(+0)
   //         / \               / \
   //        /   \             /   \
   //       2(-1) D     ==>   /     \
   //      / \               /       \
   //     /   \             3(+0)     1(+0)
   //    3(+0) C           / \       / \
   //   / \               /   \     /   \
   //  A   B             A     B   C     D
   //
   //  Note A, B, C, and D represent (possibly NULL) subtrees of nodes 1,
   //  2, and 3. The only nodes will will modify are 1, 2, and 3
   //
   //  tree:  Pointer to root of subtree to rotate
{
   MapAVLNode<Key,Value>* node_2;          // Pointer to node 2

   node_2 = tree->left;                 // Get a pointer to node 2

   tree->left = node_2->right;          // Update node 1's left subtree
   node_2->right = tree;                // Update node 2's right subtree

   return node_2;                       // Node 2 is new root node
}


template <class Key, class Value>
MapAVLNode<Key,Value>* MapAVL<Key,Value>::LR_rotate( MapAVLNode<Key,Value>* tree )
// Private helper function that performs with a LR rotation on a node.

   //  This private method performs an LR rotation. This means that we have
   //  the following situation:
   //
   //         1(-2)               2(+0)
   //        / \                 / \
   //       /   \               /   \
   //      3(+1) D     ==>     /     \
   //     / \                 3(+0)   1(+0)
   //    A   2(+0)           / \     / \
   //       / \             /   \   /   \
   //      B   C           A     B C     D
   //
   //  Note A, B, C, and D represent (possibly NULL) subtrees of nodes 1,
   //  2, and 3. The only nodes will will modify are 1, 2, and 3
   //
   //  tree:  Pointer to root of subtree to rotate
{
   MapAVLNode<Key,Value>* node_2;          // Pointer to node 2
   MapAVLNode<Key,Value>* node_3;          // Pointer to node 3

   node_2 = tree->left->right;          // Get a pointer to node 2
   node_3 = tree->left;                 // Get a pointer to node 3

   tree->left = node_2->right;          // Update node 1's left subtree
   node_3->right = node_2->left;        // Update node 3's right subtree
   node_2->right = tree;                // Update node 2's right subtree
   node_2->left = node_3;               // Update node 2's left subtree

   return node_2;                       // Node 2 is new root node
}


template <class Key, class Value>
MapAVLNode<Key,Value>* MapAVL<Key,Value>::rightBalance( MapAVLNode<Key,Value>* tree )
// Private helper function that performs with a RL or a RR rotation on a node.
{
   MapAVLNode<Key,Value>* right_sub = tree->right;         // Pointer to right subtree root

   //  There are three possible balance types for the right subtree, and
   //  the type of rotation we perform depends on this, namely:
   //
   //  1. right subtree is RH, so perform an RR rotation
   //  2. right subtree is LH, so perform an RL rotation
   //  3. right subtree is EQ (this can only happen during deletion), so
   //     perform an RR rotation

   switch( right_sub->factor )
   {
     case RH:
       tree->factor = EQ;
       right_sub->factor = EQ;
       return RR_rotate( tree );

     case LH:
       tree->factor = EQ;
       right_sub->factor = EQ;
       right_sub->left->factor = EQ;
       return RL_rotate( tree );

     default: // case EQ:
       tree->factor = RH;
       right_sub->factor = LH;
       return RR_rotate( tree );
   }
}


template <class Key, class Value>
MapAVLNode<Key,Value>* MapAVL<Key,Value>::RL_rotate( MapAVLNode<Key,Value>* tree )
// Private helper function that performs with a RL rotation on a node.

   //  This private method performs an RL rotation. This means that we have
   //  the following situation:
   //
   //     1(+2)                 2(+0)
   //    / \                   / \
   //   A   3(-1)     ==>     /   \
   //      / \               /     \
   //     /   \             1(+0)   3(+0)
   //    2(+0) D           / \     / \
   //   / \               /   \   /   \
   //  B   C             A     B C     D
   //
   //  Note A, B, C, and D represent (possibly NULL) subtrees of nodes 1,
   //  2, and 3. The only nodes will will modify are 1, 2, and 3
   //
   //  tree:  Pointer to root of subtree to rotate
{
   MapAVLNode<Key,Value>* node_2;          // Pointer to node 2
   MapAVLNode<Key,Value>* node_3;          // Pointer to node 3

   node_2 = tree->right->left;          // Get a pointer to node 2
   node_3 = tree->right;                // Get a pointer to node 3

   tree->right = node_2->left;          // Update node 1's right subtree
   node_3->left = node_2->right;        // Update node 3's left subtree
   node_2->left = tree;                 // Update node 2's left subtree
   node_2->right = node_3;              // Update node 2's right subtree

   return node_2;                       // Node 2 is new root node
}


template <class Key, class Value>
MapAVLNode<Key,Value>* MapAVL<Key,Value>::RR_rotate( MapAVLNode<Key,Value>* tree )
// Private helper function that performs with a RR rotation on a node.

   //  This procedure performs an RR rotation. This means that we have the
   //  following situation:
   //
   //     1(+2)                2(+0)
   //    / \                  / \
   //   A   2(+1)     ==>    /   \
   //      / \              /     \
   //     B   3(+0)        1(+0)   3(+0)
   //        / \          / \     / \
   //       C   D        A   B   C   D
   //
   //  Note A, B, C, and D represent (possibly NULL) subtrees of nodes 1,
   //  2, and 3. The only nodes will will modify are 1, 2, and 3
   //
   //  tree:  Pointer to root of subtree to rotate
{
   MapAVLNode<Key,Value>* node_2;          // Pointer to node 2

   node_2 = tree->right;                // Get a pointer to node 2

   tree->right = node_2->left;          // Update node 1's right subtree
   node_2->left = tree;                 // Update node 2's left subtree
   return node_2;                       // Node 2 is new root node
}