EECE 352: PS9

Due: Tuesday 2 November 1999

This problem set does not involve any programming. You will hand in your written solutions as usual (don't forget the cover sheet).

Problem 1 (10%): Show the tree that results after inserting the following numbers into a Binary Search Tree (in the order they are given).

10, 9, 11, 7, 5, 2, 1, 12, 13, 15, 20
    

Problem 2 (10%): Show the tree that results after removing each one of the numbers below from the tree in Problem 1. Remove the numbers in the order that they appear.

10, 9, 11, 7

Problem 3 (10%): Show the tree that results after inseting each one of the numbers below into an AVL tree. For each insertion you must also specify:

  1. Which was the deepest unbalanced node. If any.
  2. If there was one, whether a single or double rotation was performed, and which elements were involved in the rotation.
10, 9, 11, 7, 5, 2, 20, 13, 21
    

Problem 4 (14%): Repeat Problem 3 for this list:

10, 12, 14, 16, 18, 20, 19, 17, 15, 13, 11, 9, 8, 7, 6
    

Problem 5 (14%): Show the tree that results after inseting each one of the numbers below into a Red Black tree. Make sure your drawings show which are the red and which are the black nodes. For each insertion you must also specify which, if any, rotations where performed.

10, 9, 11, 7, 5, 2, 1, 12, 13, 15, 20
    

Problem 6 (14%): Repeat Problem 5 for this list:

10, 9, 8, 7, 6, 3, 4, 1, 2, 15, 14, 13, 12, 11
    
Problem 7 (14%): Show the tree that results after inseting each one of the numbers below into an AA tree.
10, 9, 11, 7, 5, 2, 1, 12, 13, 15, 20
    

Problem 8 (14%): Repeat Problem 7 for this list:

10, 9, 8, 7, 6, 3, 4, 1, 2, 15, 14, 13, 12, 11
    

Jose M. Vidal
Last modified: Fri Oct 22 12:58:55 EDT 1999