CSSE 230
Data Structures and Algorithm Analysis

Homework 5 - 57 points

To Be Turned In

Submit to the dropbox, except the last problem which goes to the repo. You may earn or use a late day for this assignment. Like all written assignments, this is an individual assignment. You may discuss it with others, but you should write (and code) your answers yourself.

  1. (10 points) Let S(H) denote the minimum number of nodes in a height-balanced tree of height H. Prove that S(H) = Fib(H+3) - 1 for all H ≥ 0 by induction. Hint: We observed in class that S(H) = S(H-1) + S(H-2) + 1. Use this observation in your proof. (If you missed this observation, you should review it, asking for help if needed, until you convince yourself this is true.) Here are a couple of supplementary online resources on induction that I like: (1) Video demo and web page (this page does a few examples, and explains more about why is works with a couple of cool examples showing what happens if you use math induction incorrectly!)
  2. (10 points) Height-balanced (AVL) trees guarantee that the difference in height between subtrees is limited to at most one. But how different could the relative sizes of AVL subtrees be? Answer this question by considering an AVL tree of height H, where the root has left subtree TL of as small a size as possible and right subtree TR of as large a size as possible. Compute formulas (in terms of H) for the sizes of TL and TR, and take the ratio N(TR)/N(TL) of their sizes. Then take the limit of this ratio as H increases. Is the ratio of sizes limited to a constant, or can it grow arbitrarily large?

  3. (12 points) Fill in the following table. Be very careful to get the exact values. Most of the credit will be for the last column. Don't use the AVL approximation formula (H < 1.44log(...)). Instead, draw trees and look for the patterns, like we did on day 13 in class.

    Feel free to include explanations of your answers. correct_answer → full_credit.  wrong_answer + no_explanation → no_credit.

    1/2 point for each entry in the first two columns, and 2 points each for each entry in the last column.

    n Height of shortest binary tree with n nodes Height of tallest binary tree with n nodes Height of tallest AVL tree with n nodes
    7 2 6 3
    8      
    370      
    17000      
    50000      
  4. (25 points) More tree practice! You will write three methods for Binary Trees. Like the last homework, the trick to these is to add parameters or multiple return values (through your own custom class) to your recursive helper method. 
    1. getSumOfHeights. Find the sum of the heights of every node in the tree. This is an interesting problem if you want to do it efficiently, meaning in O(n) time. Just calling height() on each node will give the correct answer, but it duplicates a lot of work and leads to an O(n log n) algorithm. Could you somehow combine finding the height with finding the sum of the heights in your method? Hint: don't use a field - that has a side effect of modifying each node. Instead, use either multiple return values (which I think is clean) or mutable parameters to do the trick. Hint: I solved this problem step-by-step in a couple Session 12 videos.
    2. isHeightBalanced. Determine if the given tree is height-balanced, using the definition given in class. This is an another interesting problem. For full credit, do it efficiently, meaning in O(n) time. Like the previous problem, just calling height() on each node will give the correct answer, but it duplicates a lot of work and leads to an O(n log n) algorithm. Could you somehow combine finding the height with finding if the node is height-balanced in your method? See the hint on the previous problem.
    3. Full tree constructor. Create a full tree of Integers whose leaves have the given depth, and where every node is labeled with its own depth. (Reminder: Full trees are those in which all the leaves have the same depth.) It is good experience to know how to build a whole tree by calling a single method. 
            Commit your work to Git as you make progress and when you finish.