Autumn 2000

1. Deletion in binary search trees:

a. Show all intermediate steps of inserting the elements 3, 1, 4, 6, 9, 2, 5, 7 into an initially empty binary search tree. Then show the result of deleting the root of this tree.
b. Show the final result of inserting 4, 1, 6, 5, 8, 2, 9, 7 into an initially empty binary search tree, and then show the result of deleting the root of this tree.

c. Show the final result of inserting 4, 1, 7, 5, 6, 8, 9 into an initially empty binary search tree, and then show the result of deleting the root of this tree.

2. Show all intermediate steps of inserting the elements 2, 1, 4, 5, 9, 3, 6, 7 into an initially empty AVL tree.

3. First draw pictures for the two rebalancing operations that are the symmetric versions of the ones given in Figures 4.44 and 4.45 (4.47 and 4.48 in C++ book). Then show the intermediate "rebalancing" steps, resulting from accessing keys 3 and 9 in this order for the splay tree of Figure 4.61 (Figure 4.69 in the C++ book).

4. This part is due by noon, Thursday, October 19. Help us create the "database" for Programming Project #2. E-mail back one or more database records to Ann Li, observing the format described below:

7 characters: StudentNumber (no blanks)

1 blank space

15 characters: LastName (pad on the right with blanks, if needed)

1 blank space

15 characters: FirstName (pad on the right with blanks, if needed)

1 blank space

2 characters: Age (2 digit integer between 10 and 99)

1 blank space

2 characters: Class (1 digit integer between 1 and 9)

Example:

6413578 Buckingham      Christopher     29 4

Ann Li has already sent a request e-mail to the class mailing list. You should reply (not Reply All, just Reply) to that e-mail, back to her.