Why does the method remove(x) in the RedBlackTree implementation perform the assignment u:parent = w:parent? Shouldn’t this already be done by the call to splice(w)?
bool remove(T x) {
Node *u = findLast(x);
if (u == nil || compare(u->x, x) != 0)
Node *w = u->right;
if (w == nil) {
w = u; u = w->left; }
else {
while (w->left != nil)
w = w->left;
u->x = w->x;
u = w->right; }
splice(w); //fixs color of tree after removal
u->colour += w->colour;
u->parent = w->parent; ************************
delete w;
removeFixup(u);
return true; }
From what I understand of the code w.parent adopts u therefore w parent is now u.parent. Does this seem correct? Thank You!
Aucun commentaire:
Enregistrer un commentaire