0
01 void RedBlackTree::deleteNode(Node *z)
02 {
03     Node *y = z;
04     Color yOriginalColor = y->color;
05     Node *x;
06     if (z->left == sentinel)
07     {
08         x = z->right;
09         transplant(z, z->right);
10     }
11     else if (z->right == sentinel)
12     {
13         x = z->left;
14         transplant(z, z->left);
15     }
16     else
17     {
18         y = minimum(z->right);
19         yOriginalColor = y->color;
20         x = y->right;
21         if (y->parent == z)
22         {
23             x->parent = y;  // WHY??
24         }
25         else
26         {
27             transplant(y, y->right);
28             y->right = z->right;
29             y->right->parent = y;
30         }
31         transplant(z, y);
32         y->left = z->left;
33         y->left->parent = y;
34         y->color = z->color;
35     }
36 
37     delete z;
38 
39     if (yOriginalColor == Color::BLACK)
40     {
41         deleteFixUp(x);
42     }
43 }

In line 20, we assign y->right to x. In line 23, we assign y to x->parent. Isn't the assignment in line 23 redundant since the parent of x is y already?

In the book it says

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.

I don't understand the explanation from the book, why would x.p points to z. When we move node y from its original position to z's position, shouldn't y's child x remain unaffected, still attached to y?

I come across 2 posts asking similar queations as I do, however, I'm still confused after reading through the answers.

After these 2 questions, I get one more question. I don't understand the assignment of y to x.p in line 23 has anything to do with x being the sentinel node (e.g. T.nil) or not.

Zack
  • 1
  • 2
  • The pseudo-code question's answer points out that if using an explicit sentinel node (as this code does) and y->right is the tree's sentinel then the parent value is not necessarily y (in fact, very likely is not), but that it needs to be for the following node removal to work. – SoronelHaetir Dec 24 '22 at 22:06
  • Do you mean the sentinel node's parent needs to be `y` in order for *RB-DELETEFIXUP* to work properly? – Zack Dec 25 '22 at 05:28
  • That's what the comment in the answer to the pseudo-code answer says. When I've done RB trees I just went with an actual NULL value rather than a sentinel so haven't tried scanning through the code to confirm it. – SoronelHaetir Dec 25 '22 at 17:43

0 Answers0