Homework 3

Due: October 12th, 2012 at the beginning of class
Homework turned in after class will not be accepted.
Homework turned in during class but after I have collected it will lose 20%.

Do your own work for this assignment; do not work with others. Consult the book and your professor for help if you need it. Please write neatly, or preferably type your answers. Use good grammar, spelling, and complete sentences.


Each problem (not including the extra credit) is worth 10 points.

  1. Exercise 4.19 from your book. Show the tree after each insertion (before rebalancing), point out each imbalance (when they occur), and show the tree after rebalancing (if it is necessary).
  2. Show how the following AVL-balanced tree will change after removing each of the following nodes: 17, 13, 20, and 2. After removing each node, it should remain removed for the rest of the exercise. Make sure that your changes are clear.

    AVL tree for remove exercise

  3. Exercise 4.27 from your book. Like the previous problem, show the tree after each access. For each rotation, clearly indicate its type, location in the tree, and direction(s) of rotation.
  4. For the BSTNode class from project 3, write a function called duplicate() with the following signature:
    template <class T>
    BSTNode<T> *BSTNode<T>::duplicate() const;
    This function should return a deep copy of the node it is called on and the entire subtree below it. Using recursion, I can write this function in one line. Try for the simplest function possible, but make sure it's correct -- test it!
  5. Exercise 6.2 from your book. For part (a), show a tree representation and an array representation for each insertion. For part (b), show the final result as a tree and as an array.
  6. Exercise 6.3 from your book. Use the answer you got from part (a) of exercise 6.2, and show the array and the tree representation after each deleteMin.
  7. Extra credit: Exercise 6.12 from your book. You should turn in your code as well as your timing results.

Copyright © 2012 Adam Sealey, based largely on a syllabus by Greg Hamerly .
Computer Science Department
Baylor University

valid html and css