What is the problem
You’ll be given a RB Tree and asked to delete a set of (to-be-deleted) nodes from it.
Before you begin
Going through each to-be-deleted node, u should:
-
perform the regular BST node deletion (but DON’T get rid of the node yet) ⇒ this will make the to-be-deleted node a leaf node.
-
If it’s red, u may delete it (you’re done).
Otherwise, mark it as Z and turn it into a DB node, mark its parent as P, its sibling as S, its sibling’s near child as NC, and its sibling’s far child as FC.
-
follow the strategy below.
The keys
Symbols Key
Arrows/lines Key
The Strategy
NOTE
I let Z be the left child of P while showing the strategy. However, this strategy will work just as well it was reversed.
