$13-$I Persistent dynamic sets

During the course of an algorithm, you sometimes find that you 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 modi$-$

fied, but this approach can slow down a program and also consume a lot of space.

Sometimes, you can do much better.

Consider a persistent set $S$ with the operations INSERT, Delete, and SEARCh,

which you implement using binary search trees as shown in Figure $13\mathrm{.}8($a$).$ Main$-$

tain a separate root for every version of the set. In order to insert the key $5$ into the

set, create a new node with key $5.$ This node becomes the left child of a new node

with key $7,$ since you cannot modify the existing node with key $7.$ Similarly, the

new node with key $7$ becomes the left child of a new node with key $8$ whose right

child is the existing node with key $10.$ The new node with key $8$ becomes, in turn,

the right child of a new root $r^{\text{'}}$ with key $4$ whose left child is the existing node with

key $3.$ Thus, you copy only part of the tree and share some of the nodes with the

original tree, as shown in Figure $13\mathrm{.}8($b$).$

Assume that each tree node has the attributes key, left, and right but no parent.

$($See also Exercise $13\mathrm{.}3-6$ on page $346.)$

a$.$ For a persistent binary search tree $($not a red$-$black tree, just a binary search

tree$),$ identify the nodes that need to change to insert or delete a node.

Figure $13\mathrm{.}8($a$)$ A binary search tree with keys $2,3,4,7,8,10.($b$)$ The persistent binary search

tree that results from the insertion of key $5.$ The most recent version of the set consists of the nodes

reachable from the root $r^{\text{'}},$ and the previous version consists of the nodes reachable from $r.$ Blue

nodes are added when key $5$ is inserled.

b$.$ Write a procedure Persistent$-$Tree$-$InSert $(T,z)$ that, given a persistent

binary search tree $T$ and a node $z$ to insert, returns a new persistent tree $T^{\text{'}}$

that is the result of inserting $z$ into $T.$ Assume that you have a procedure

COPY$-$NODE $(x)$ that makes a copy of node $x,$ including all of its attributes.

c$.$ If the height of the persistent binary search tree $T$ is $h,$ what are the time and

space requirements of your implementation of PERSISTENT$-$TREE$-$INSERT?

$($The space requirement is proportional to the number of nodes that are copied.$)$

d$.$ Suppose that you include the parent attribute in each node. In this case, the

Persistent$-$TREe$-$INSERT procedure needs to perform additional copying.

Prove that Persistent$-$Tree$-$InSert then requires $(n)$ time and space,

where $n$ 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)$ per insertion or deletion. You may assume that all keys

are distinct.