Homework Help is Here – Start Your Trial Now!
Engineering
Data Structures and Algorithms
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)

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)

icon
Related questions
Question

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)

boolean remove(T x) { Node<T> u = findLast(x); if (u == nil || compare (u.x, x) != 0) return false; Node<T> w = u.right; if (w == nil) { §9.2 W = U; u = w.left; } else { while (w.left != nil) w = w.left; } RedBlackTree U.X = W.X; u = W.right; splice (w); u.colour +=w.colour; u.parent = w.parent; removeFixup (u); return true; 199 Red-Black Trees
Transcribed Image Text:boolean remove(T x) { Node<T> u = findLast(x); if (u == nil || compare (u.x, x) != 0) return false; Node<T> w = u.right; if (w == nil) { §9.2 W = U; u = w.left; } else { while (w.left != nil) w = w.left; } RedBlackTree U.X = W.X; u = W.right; splice (w); u.colour +=w.colour; u.parent = w.parent; removeFixup (u); return true; 199 Red-Black Trees
Expert Solution
steps

Step by step

Solved in 3 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer