1
$\begingroup$

Whilst I was reading CLRS I came across this:

When TRANSPLANT replaces the subtree rooted at node u with the subtree rooted at node v, node u’s parent becomes node v’s parent, and u’s parent ends up having v as its appropriate child.

TRANSPLANT(T, u, v)
1  if u.p == NIL
2      T.root = v
3  elseif u == u.p.left
4      u.p.left = v
5  else u.p.right =  v
6  if v != NIL
7      v.p = u.p

Lines 1–2 handle the case in which u is the root of T . Otherwise, u is either a left child or a right child of its parent. Lines 3–4 take care of updating u.p.left if u is a left child, and line 5 updates u.p.right if u is a right child. We allow v to be NIL, and lines 6–7 update v.p if v is non-NIL.

Why wasn't v was checked for nil value in the starting of the procedure and if it was not checked then why was it checked in line 6. If v is nil then its parent will be its original parent and u's parent will reference to v - wouldn't this cause inconsistency in tree ?

Context

Transplant is the sub-procedure used in deletion of a node from a binary search tree. It is used in binary search tree not in RB Trees or B-Trees.

Details about the book

Edition - 3rd

Print - 2nd

PageNo - 296

$\endgroup$
3
  • 2
    $\begingroup$ 1. Looks like there's a typo in line 6. Since you're asking about line 6, that might be important. Can you edit to fix it? 2. Have you tried working through an example, to see if you can find a counterexample where this seems to do the wrong thing? It's not clear to me why you think it needs to be checked earlier, so an example would help. 3. Have you checked the errata for CLRS? $\endgroup$
    – D.W.
    Commented May 11, 2016 at 20:45
  • 1
    $\begingroup$ Please clarify which parts of your question are literal quotes and which are yours. Use the blockquote Markdown element (>). $\endgroup$
    – Raphael
    Commented May 12, 2016 at 7:38
  • $\begingroup$ Please put into words purpose and context of TRANSPLANT. (Suggest reviewing the title: CLRS TRANSPLANT RB(?) tree nodes: NIL check for 2nd node) $\endgroup$
    – greybeard
    Commented May 12, 2016 at 7:40

1 Answer 1

1
$\begingroup$

If $v$ is NIL then transplanting $v$ just transplants an empty tree. This is fine. It is handled in the exact same way as transplanting an actual tree, the only difference being that we don't need to update $v$'s parent pointer.

Could the code be structured differently? Probably. Why, then, did the authors choose this particular implementation? No deep reason. They programmed the algorithm, and that's the code they came up with. You might have come up with a different code. There's no one right answer in programming.

$\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.