Written Assignment #6: Searching

Corrections to the original version:

• #5 - parenthetical should be (or the record in the right subtree having the minimum value for the key), not maximum, as it said in the original. (2pts dt28)
• #8 - x could be the root, or a child or grandchild of the root. (2pts dt28).

1. Sequential Lists
   1. How many compares would be required to search for 2?
   2. How many compares would be required to search for 1?
   3. How many compares would be required to search for 30?
   4. What is the maximum possible number of compares needed?

2. Sorted Lists
   1. Show the sorted list.
   2. How many compares would be required to search the sorted list for 2?
   3. How many compares would be required to search the sorted list for 1?
   4. How many compares would be required to search for 30?
   5. what is the maximum possible number of compares needed?

3. Binary Searching
   1. Assuming you have access to any element, and can perform binary search, show the comparisons required to search for 16.
   2. Show the comparisons required to search for 30, using binary search.
   3. What is the maximum possible number of compares needed using binary search?

4. Binary Search Trees
   1. Draw the binary search tree for this sequence of data.
   2. How many comparisons are required to find 16?
   3. How many comparisons are required to find 30?
   4. What is the maximum possible number of compares needed?
   5. Where would 17 be inserted in the tree?
   6. Delete 10 and show the updated tree.

5. Samet [1], p. 212. #6: Suppose you delete a record from a binary tree. The first step is to find the position of the record in the left subtree having the maximum value for the key (or the record in the right subtree having the minimum value for the key), say p. Prove that p has at most one child.

6. AVL Trees
   1. Draw the AVL tree for this sequence of data. State which insertions cause rotation operations (you only have to draw the final tree, but you might find it helpful to draw some intermediate results as well).
   2. How many comparisons are required to find 16?
   3. What is the maximum possible number of compares needed?
   4. Delete 10 and show the updated tree.

7. Splay Trees
   1. Draw the splay tree for this sequence of data. You only have to draw the final tree, but remember that each search, insertions and deletion provokes a splay operation.
   2. What is the maximum possible number of compares needed?
   3. Delete 10 and show the updated tree.

8. Given that an item x was successfully searched for in a splay tree, and that the next operation was a search for y, prove that the resulting tree has x as the root or as a child or grandchild of the root, for any values of x and y.

9. List Arrays
   1. Show a list array for this data (you only need to show the final list).
   2. How many comparisons are required to find 16?
   3. What is the maximum possible number of compares needed?

10. B-trees
    1. Show a 2-3 tree (B-tree of order 3) for this data. State which insertions cause splits (you only need to show the final tree, but you might find it helpful to draw some intermediate results as well).
    2. what is the maximum possible number of compares needed?
    3. Delete 8 and show the updated tree.
    4. Draw the corresponding Red-Black tree for this B-tree.

11. What is the maximum depth of a red-black tree corresponding to a 2-3 tree of depth n? Prove your answer.