13-1 Persistent dynamic sets

During the course of an algorithm, we sometimes find that we need to maintain past versions of a dynamic set as it is updated. We call such a set persistent. One way to implement a persistent set is to copy the entire set whenever it is modified, but this approach can slow down a program and also consume much space. Sometimes, we can do much better.

Consider a persistent set SS with the operations INSERT\text{INSERT}, DELETE\text{DELETE}, and SEARCH\text{SEARCH}, which we implement using binary search trees as shown in Figure 13.8(a). We maintain a separate root for every version of the set. In order to insert the key 55 into the set, we create a new node with key 55. This node becomes the left child of a new node with key 77, since we cannot modify the existing node with key 77. Similarly, the new node with key 77 becomes the left child of a new node with key 88 whose right child is the existing node with key 1010. The new node with key 88 becomes, in turn, the right child of a new root rr' with key 44 whose left child is the existing node with key 33. We thus copy only part of the tree and share some of the nodes with the original tree, as shown in Figure 13.8(b).

Assume that each tree node has the attributes keykey, leftleft, and rightright but no parent. (See also Exercise 13.3-6.)

a. For a general persistent binary search tree, identify the nodes that we need to change to insert a key kk or delete a node yy.

b. Write a procedure PERSISTENT-TREE-INSERT\text{PERSISTENT-TREE-INSERT} that, given a persistent tree TT and a key kk to insert, returns a new persistent tree TT' that is the result of inserting kk into TT.

c. If the height of the persistent binary search tree TT is hh, what are the time and space requirements of your implementation of PERSISTENT-TREE-INSERT\text{PERSISTENT-TREE-INSERT}? (The space requirement is proportional to the number of new nodes allocated.)

d. Suppose that we had included the parent attribute in each node. In this case, PERSISTENT-TREE-INSERT\text{PERSISTENT-TREE-INSERT} would need to perform additional copying. Prove that PERSISTENT-TREE-INSERT\text{PERSISTENT-TREE-INSERT} would then require Ω(n)\Omega(n) time and space, where nn is the number of nodes in the tree.

e. Show how to use red-black trees to guarantee that the worst-case running time and space are O(lgn)O(\lg n) per insertion or deletion.

(Removed)