dimanche 25 novembre 2018

RedBlackTree remove hard to understand

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