CSSE 230
Data Structures and Algorithm Analysis

Written Assignment 7

To Be Turned In

Except where noted, these are to be turned in as hard copy. You can write solutions out by hand, or write them on your computer and print them.

Papers must not have ragged, spiral-notebook edges. Multiple page solutions must be stapled. Solutions not following these guidelines will be returned ungraded. I regret this rigidity, but it is necessary given the number of students in CSSE 230 this term.

Late days may not be used for written assignments.

  1. Don’t forget: You should be keeping an individual log about your team project work so that you can write a performance evaluation for each of your teammates. You do not need to turn in this log, but I wanted to remind you while I had your attention.
  2. (20 points) Weiss Exercise 19.2. 10 points for drawing the trees, and 10 for the probability.

  3. (20 points) Fill in the following table. Be very careful to get the exact values. Half of the credit will be for the last column.

    Feel free to include explanations of your answers. (wrong answer) + (no explanation) = (no credit).

    1 point each for entries in the first two columns, and 3 points each for entries 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. (10 points) In a previous problem, you did Exercise 19.2, which 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 average height of the BSTs?
    2. With the same assumptions, do the same exercise for inserting the four numbers into an AVL tree. I.e., what is the average height of the AVL trees?

  5. (15 points) Start with the following Binary Search Tree:

    See the hint at the end!

    1. Is this an AVL tree? ____ If not, rearrange it so that it is height-balanced.
    2. Draw the tree after insertion of a node containing 11, using the usual BST insertion algorithm.
    3. Is the new tree AVL? ______ If not, name the node where the rotation should be done, according to the algorithm from class. ______ Single or double rotation? ____________ If you need to do a rotation, draw the resulting tree.
    4. Delete the element 5 from the original tree (not the one from part c), using the BST deletion algorithm described in class and in the textbook. Draw the new tree.
    5. Is the new tree AVL? ______ If not, name the node where the rotation should be done, according to the algorithm from class. ______ Single or double rotation? ____________ If you need to do a rotation, draw the resulting tree.
    6. Is your new tree (if any) AVL? ______ If not, name the node where the rotation should be done, according to the algorithm from class. ______ Single or double rotation? ____________ If you need to do a rotation, draw the resulting tree.
    7. Add the element 5 to the tree from part (f) using the BST algorithm. Draw the new tree.
    8. Is the new tree AVL? ______ If not, name the node where the rotation should be done, according to the algorithm from class. ______ Single or double rotation? ____________ If you need to do a rotation, draw the resulting tree.
    9. Add the element 12 to the tree from part (h). Draw the new tree.
    10. Is the new tree AVL? ______ If not, name the node where the rotation should be done, according to the algorithm from class. ______ Single or double rotation? ____________ If you need to do a rotation, draw the resulting tree.
    11. Add the element 7 to the tree from part (j). Draw the new tree.
    12. Is the new tree AVL? ______ If not, name the node where the rotation should be done, according to the algorithm from class. ______ Single or double rotation? ____________ If you need to do a rotation, draw the resulting tree.

    Hint: In my solution, for all the sub-parts together, I did three single rotations and no double rotations. The first four leaf nodes in my final tree were 3, 5, 7, and 9. (In my first attempt, I misread part d) and deleted from the tree in part c) rather than the original tree. With that mistake, for all the sub-parts together, I did two single rotations and one double rotation and the first four leaf nodes in my final tree were also 3, 5, 7, and 9.)