1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Can you give a self-contained statement of the task you're trying to solve, so we don't have to refer to CLRS to understand what you're trying to achieve? $\endgroup$
    – D.W.
    Mar 12, 2021 at 19:26

1 Answer 1

1
$\begingroup$

Alright, it was all in the diagram:

We need to copy the descendants of the nodes in the path to make sure we don't end up with a single node having two parents

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.