Winter 2000

1. Write a method called union for my list class that is given two lists L1 and L2 whose element values are in sorted ascending order and an empty third list L3. It should make L3 become a list that is the union (also in sorted ascending order) of L1 and L2. This should be done efficiently through iteration, not recursion. The idea is to move one pointer ptr1 through L1 and another pointer ptr2 through L2, deciding which elements to add to L3. Note that L1 and L2 will not have any duplicate values, and the union must not have any duplicate values. You can add any utility methods you need, since I didn't write them all. Type your answer. Running it is not required, but feel free to do so.

2. Write a function called count_range(t,low,high) that takes in a pointer to a binary search tree whose elements are integers and returns a count of the number of nodes in the tree whose element values lie between the integers low and high, ie. low <= value <= high. The procedure should be recursive, and it should be as efficient as possible. That means, at least, that it should not just call isin for very possible value in the range, and it should also not descend into a subtree if all the values in that subtree are out of range. You may assume no duplicate values in the tree. Type your answer. Running it is not required, but feel free to do so.

3. Ex. 4.9 (modified) from book

a. Show the result of inserting 3, 1, 4, 6, 9, 2, 5, 7 into an initially empty binary search tree, and then show the result of deleting the root from this tree.
b. Show the 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 from this tree.

c. Show the 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 from this tree.

4. Ex. 4.19 from book. Show the result of inserting 2, 1, 4, 5, 9, 3, 6, 7 into an initially empty AVL tree.

5. Ex 4.27 (modified) Show the result of accessing the keys 3 and 9 in order in the splay tree of Figure 4.69. First draw pictures for the two rebalancing operations that are the symmetric versions of the ones given in Figures 4.47 and 4.48.

6. Show how to insert the sequence 3, 1, 4, 5, 9, 2, 6, 8, 7, 0 into an initally empty B+ tree of order 3 (sometimes called a 2-3 tree, since each node can contain up to 2 keys and 3 pointers).

NOTE: