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:

- Which was the deepest unbalanced node. If any.
- 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

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