Question 1:

Can you implement the dynamic-set operation INSERT on a singly linked list in O(1) time? How about DELETE?

Question 2:

Suppose we have stored n keys in a hash table of size m, with collisions resolved by chaining, and that we know the length of each chain, including the length L of the longest chain. Describe a procedure that selects a key uniformly at random from among the keys in the hash table and returns it in expected time O(L . (1 + 1/α)).

Question 3:

Give a nonrecursive algorithm that performs an inorder tree walk. (Hint: An easy solution uses a stack as an auxiliary data structure. A more complicated, but elegant, solution uses no stack but assumes that we can test two pointers for equality.)

Question 4:

Show that if a node in a binary search tree has two children, then its successor has no left child and its predecessor has no right child.

Question 5:

Give a recursive version of the TREE-INSERT procedure.

Question 6:

Why don't we allow a minimum degree of t = 1?

Question 7:

As a function of the minimum degree 1, what is the maximum number of keys that can be stored in a B-tree of height h?

Question 8:

Explain how to find the minimum key stored in a B-tree and how to find the prede-cessor of a given key stored in a B-tree.

Below is the TREE-DELETE procedure

TREE-DELETE(T, Z)

1 if z.left == NIL

2       TRANSPLANT(T, z, z. right)

3 elseif z.right == NIL

4       TRANSPLANT(T, z, z. left)

5 else y = TREE-MINIMUM (z. right)

6       if y.p ≠ z

7       TRANSPLANT(T, y, y. right)

8       y.right = z.right

9       y.right.p = y

10     TRANSPLANT(T, z, y)

11     y.left = z.left

12     y. left. p = y

Exercise A1

Follow the TREE-DELETE procedure described in Chapter 12, show step-by-step output of each of the following operations applied on the binary search tree below.

a) Delete node 3.

b) Based on output from step a), delete node 7.

c) Based on output from step b), delete node 18.

Note: Strictly speaking, node i in the question should be interpreted as "a node that is represented by its key value of i".

B-TREE-INSERT (T, k)
1 r = T. root
2 if r.n==2t - 1
3 s = ALLOCATE-NODE 0
4 T. mot = s
5 s.leaf = FALSE
6 s.n = 0
7 s.c, = r
8 B-TREE-SPLIT-CHILD(S, 1)
9 B-TREE-INSERT-NoNFuLL(s,k)
10 else B-TREE-INSERT-NONFULL (r, k)

Exercise A2

Follow the B-TREE-INSERT procedure described in Chapter 18, show step-by-step output of each of the following operations applied on the B-tree below. Note that the B-tee has a minimum degree r=3 and the values inside each node show the key values stored in that node.

a) Insert key 13.

b) Based on output from step a), insert key 37.

c) Based on output from step b), insert key 34.

d) Based on output from step c), insert key 45.