CSSE 230
Data Structures and Algorithm Analysis

Homework 6  -  54 points

Don't forget that you should be making notes about your team and team members, for eventual use in the EditorTrees team evaluation.

To Be Turned In

Questions 1 and 2 should be submitted to the drop box and the last two questions should be committed to your repository in SVN.  You may earn a late day by submitting all parts early, or use a late day if submit any part late.

    1. (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      

    2. (10 points) Exercise 19.2 included finding the probability (based on equally likely insertion orders of each of the 24 permutations) of each of the 14 different trees that can result when inserting the numbers 1, 2, 3, and 4 into an initially empty BST (with no re-balancing).

      1. With the same assumption (that all permutations of the four numbers are equally likely), what is the (weighted) average height of the BSTs?
      2. With the same assumptions, do the same exercise for inserting the four numbers into an AVL tree. In other words, what is the average height of the AVL trees?

    3. (32 points) For this task you’ll add four more methods to the Threaded Binary Search Tree project. Check out the new template code given in ThreadedTree2 in your individual SVN repository.

      The methods you are to write are the last two methods in ThreadedBinaryNode and the last two in ThreadedBinarySearchTree. Near the end of ThreadedBinarySearchTree, you’ll find a couple of new methods that illustrate the use of the methods you will write. The code in the JUnit tests in ThreadedTree2Test.java should also help you to understand how your methods should work.

      Your code, which you should commit to your repository, should pass all of the unit tests in ThreadedTree2Test.java, plus the other unit tests that are already passed by the template code. That is, don’t break the existing code while adding your code. You can right-click a project to run all the JUnit tests in the entire project. That’s how we’ll test your solution.

    Other problems for your consideration

    6.5[6.5], 6.31[6.17], 6.37[6.22], 7.3[7.3], 7.4[7.4], 7.23[7.19], 7.28[7.23]