University of Utah School of Computing
CS 2420:
Introduction to Computer Science II
Homework 8
Assigned: Friday, Oct 31, 2014
Due: Monday, Nov 10, 2014, at 3pm.

Homework 8

Part I: Implement an AVL Tree

Implement single and double rotations and make sure that during insertions and deletions your tree maintains the AVL property. I recommend writing a check_ballance() method that ensures your tree is balanced and using this for testing. For full credit insertion and deletion must be logarithmic time. This means you have to compute the height of a node in constant time. I recommend writing the tree first using an expensive, recursive height() method and, once its working, developing another mechanism for computing the height.
I recommend starting from your vanilla binary search tree from last week and adding balancing routines.

Part II: Timing results

Compare your AVL tree to last weeks binary search tree. Which is faster? How much faster? Can you come up with an input on which the vanilla tree is faster?

Part III: Written Homework

What to hand in

Create a web page for the assignment. Add a description of your program, graphs and the conclusions you've drawn. Use the CADE online handin system or Terminal Handin to handin your source code. Please zip and handin your entire project directory (including an info.txt file). If you work in a team only one of you need to submit the source code.

Grading

Each homework assignment will receive a grade out of 100 points. This week, the available points will be broken down like so:
  • 40 points: AVL Tree/Rotations
  • 10 points: Logarithmic-time insert/delete
  • 5 points: Graphs and conclusions
  • 10 points: Comments describing the class, each method as well as the interesting pieces of the code itself
  • 10 points: Elegence of programming
  • 5 points: Figures and web page
  • 20 points: Written Homework