I am going through problem 13-1 in CLRS 3rd edition. I came up with the following algorithm as a solution:
PERSISTENT-TREE-INSERT(T,z)
y= T.nil
x=T.root
while x != T.nil
y=x
if z.key < x.key
x = x.left
else x = x.right
if y == T.nil
T'.root = z
return T'
else if z.key = y.key
y'=copy(y)
y'.left = z
z.p = y'
else y'= copy(y)
y'.right=z
z.p = y'
x = y'
while x.p != T.nil
if x.key < x.p.key
x' = copy(x.p)
x'.left = x
x.p = x'
else x' = copy(x.p)
x'.right = x
x.p = x'
T'.root = x
return T'
Now the copy procedure is :
copy(x)
w.p = x.p
w.right= x.right
w.left = x.left
w.key = x.key
return w
Now this means that I only need to copy the node that is going to be the father of the key that I'm adding and its ancestors. The book however says that additional copying is needed just because we have a reference to the parent, but I don't see it. If someone could point me in the right direction I would be much grateful.
For reference this is the exercise:
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 S with the operations INSERT, DELETE, and 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 5 into the set, we create a new node with key 5. This node becomes the left child of a new node with key 7, since we 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 r0 with key 4 whose left child is the existing node with key 3. 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).
d) Suppose that we had included the parent attribute in each node. In this case, PERSISTENT-TREE-INSERT would need to perform additional copying. Prove that PERSISTENT-TREE-INSERT would then require .n/ time and space, where n is the number of nodes in the tree.
