CS251-Project 3 AVL Trees Solved

For the last couple weeks we have been building an AVL class --- it’s time to put all the pieces together.  The assignment is to create a templated avltree<TKey, TValue class in the file “avl.h” which properly balances trees as part of the insert function.  When completed, search and insert must be O(lgN) operations; size and height must be O(1) operations.  Recall that we began modifying insert in HW #07 to compute the heights; in HW #08 you were asked to implement the left and right rotate functions.  Your test cases were created as part of lab week #07.

 

The major change to make now is to modify insert so that as you walk up the tree updating heights, you also check to see if the AVL condition is broken.  If so then rotate to fix --- either one rotation for AVL cases 1 and 4, or 2 rotations for AVL cases 2 and 3.  Recall that in class (day 20) we discussed a _RotateToFix function that insert could call to fix the tree; this function in turn calls _LeftRotate and _RightRotate.

 

You will need to implement the following public functions in your avltree class, exactly as shown here.  You cannot add nor remove parameters, or change types:

 

template<typename TKey, typename TValue class avltree 

{ private: 

  . 

  . 

  .  public: 

  avltree() 

  avltree(avltree& other) 

   virtual ~avltree()          // destructor:   int size()   int height() 

   void clear()                // clear: 

 

  TValue* search(TKey key) 

  void insert(TKey key, TValue value) 

   int distance(TKey k1, TKey k2)    // distance: 

   void                inorder()   std::vector<TKey   inorder_keys()   std::vector<TValue inorder_values()   std::vector<int    inorder_heights() 

 

}; 

 

 

Note that three functions have been added for the purposes of project #03:  a destructor to free memory, a clear function to empty a given tree, and a distance function that returns the path length between 2 keys.  Your avltree class must now free all allocated memory; more details in the next section.

 

Assignment details
Your avlclass must now contain a destructor that properly frees all memory allocated by the avltree class.  On submission we’ll check using valgrind, so you should do the same as part of your testing; recall that destructors and valgrind were introduced in lab during week 05.   

 

Your avlclass must also contain a clear function that empties the tree of all nodes, properly freeing the memory.  Note that you *cannot* call the destructor to do this; destructors in C++ are special functions that should only be called by the compiler.  Instead, what you should do is create a private helper function that both the destructor and clear call.  When clear returns, the root should be nullptr and the size 0.

 

 Finally, add a function distance(k1, k2) that returns the “distance” between the keys k1 and k2.  The distance is defined as the length of the minimum path between k1 and k2.  For example, consider the following tree --------- The distance(5, 100) = 6.  The distance from 31 to 12 is 3.  And the distance from 46 to 12 = 3.  The reverse are also true, e.g. the distance(100, 5) = 6.

 

If k1 or k2 is not in the tree, then the distance is defined as -1.  If k1 = k2, then the distance is 0.