StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PORed black tree pseudocode redundancy
text
Body
copied!<p>In introduction to Algorithms Third Edition they have a pseudocode implementation of red-black tree deletion. Here it is...</p> <pre><code>RB-DELETE(T, z) y = z y-original-color = y.color if z.left == T.nil x = z.right RB-TRANSPLANT(T, z, z.right) elseif z.right == T.nil x = z.left RB-TRANSPLANT(T, z, z.left) else y = TREE-MINIMUM(z.right) y-original-color = y.color x = y.right if y.p == z x.p = y // <--------- why???? else RB-TRANSPLANT(T, y, y.right) y.right = z.right y.right.p = y RB-TRANSPLANT(T, z, y) y.left = z.left y.left.p = y y.color = z.color if y-original-color == BLACK RB-DELETE-FIXUP(T, x) </code></pre> <p>TREE-MINIMUM just finds the smallest value in a tree, RB-TRANSPLANT takes the parent of the second parameter and has it point to the third parameter, and has the third parameter's parent be the second parameter's parent.</p> <p>By my comment, they test if y.p is z and if so set x.p to y. But x is already y.right, so this is like saying y.right.p = y, but y.right.p is already y! Why are they doing this?</p> <p>Here is their explanation...</p> <blockquote> <p>“When y's original parent is z, however, we do not want x.p to point to y's original parent, since we are removing that node from the tree. Because node y will move up to take z's position in the tree, setting x.p to y in line 13 causes x.p to point to the original position of y's parent, even if x == T.nil.”</p> </blockquote> <p>So they want to keep x's parent to be y...it already is y...</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload