CSE 373 Homework Assignment 3

Problem 1

(8 pts) In this problem you will practice insertion and deletion in binary search trees.

1. Show all intermediate steps of inserting the elements 7, 3, 6, 5, 8, 9 into a binary search tree which is initially empty. Then, show the result of deleting the root of this tree.

2. Show the final result of inserting 4, 1, 6, 5, 8, 2, 9, 7 into a binary search tree which is initially empty. Then, show the result of deleting the root of this tree.

3. Show the final result of inserting 4, 1, 7, 5, 6, 8, 9 into a binary search tree which is initially empty. Then, show the result of deleting the root of this tree.

4. Of the three search trees above (before deleting the root), which are balanced in the AVL sense? That is, which of the search trees satisfy the invariant that AVL trees maintain?

Problem 2

(8 pts) Show all intermediate steps of inserting the elements 6, 9, 10, 3, 2, 1, 8, 7 into an AVL tree which is initially empty. For each rotation, mark the unbalanced nodes with a "U" and give the type of rotation: "RFR" (rotate from right), "RFL", "DRFR", or "DRFL". See AVL diagram.

Problem 3

(8 pts) Look at Figure 4.44 and Figure 4.45 in the Java version of the textbook (or Figure 4.47 and Figure 4.48 in the C++ version). Draw pictures for the two rebalancing operations that are the symmetric versions of the operations depicted by these figures. Your answers should look like the figures in the text with all the appropriate subtrees.

Now, look at Figure 4.66 in the Java textbook (or Figure 4.69 in the C++ textbook). Show the intermediate rebalancing steps resulting from accessing keys 3 and 9 (in that order) in this splay tree.

Problem 4

(10 pts) Insert the following keys in the given order into a B+ tree of order 3 which is initially empty: 3, 1, 4, 5, 9, 6, 2, 8, 7, 0. Draw the tree after each insertion including both keys and pointers. Just to be clear, your tree should have the following properties:

• Each non-leaf node has either 1 key and 2 children, or 2 keys and 3 children.
• Each leaf node has either 1 or 2 keys.

Problem 5

(9 pts) Consider the hash function h(x) = x mod 10 and the ordered input sequence of elements 4371, 1323, 6173, 4199, 4344, 9679, 1989. Show the final result of inserting these elements (in that order) into a hash table with 10 bins (indexed 0 through 9), and organized:

1. by separate chaining, where each list is treated as a stack
2. by open addressing with linear probing, where F(i) = i
3. by open addressing with quadratic probing, where F(i) = i²