CSSE 230
Data Structures and Algorithm Analysis

Homework 6 - 32 points

To Be Turned In

Upload your submission to the Moodle assignment.

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      

Other problems for your consideration