Red-Black TreesRecall “ordinary” BST DeleteBottom-Up DeletionWhich RB Property may be violated after deletion?Fixing the problemTerminologyBottom-Up Deletion Case 1Case 1 DiagramBottom-Up Deletion Case 2Case 2 diagramBottom-Up Deletion Case 3Case 3 diagramsBottom-Up Deletion Case 4Case 4 DiagramsTop-Down DeletionSlide 16Red-Black TreesBottom-Up Deletion8/3/2007UMBC CSMC 341 Red-Black-Trees-22Recall “ordinary” BST Delete1. If node to be deleted is a leaf, just delete it.2. If node to be deleted has just one child, replace it with that child (splice)3. If node to be deleted has two children, replace the value in the node by its in-order predecessor/successor’s value then delete the in-order predecessor/successor (a recursive step)8/3/2007UMBC CSMC 341 Red-Black-Trees-23Bottom-Up Deletion1. Do ordinary BST deletion. Eventually a “case 1” or “case 2” deletion will be done (leaf or just one child).-- If deleted node, U, is a leaf, think of deletion as replacing U with the NULL pointer, V. -- If U had one child, V, think of deletion as replacing U with V.2. What can go wrong??8/3/2007UMBC CSMC 341 Red-Black-Trees-24Which RB Property may be violated after deletion?1. If U is Red?Not a problem – no RB properties violated2. If U is Black?If U is not the root, deleting it will change the black-height along some path8/3/2007UMBC CSMC 341 Red-Black-Trees-25Fixing the problemThink of V as having an “extra” unit of blackness. This extra blackness must be absorbed into the tree (by a red node), or propagated up to the root and out of the tree.There are four cases – our examples and “rules” assume that V is a left child. There are symmetric cases for V as a right child.8/3/2007UMBC CSMC 341 Red-Black-Trees-26TerminologyThe node just deleted was UThe node that replaces it is V, which has an extra unit of blacknessThe parent of V is PThe sibling of V is SBlack NodeRed NodeRed or Black and don’t care8/3/2007UMBC CSMC 341 Red-Black-Trees-27Bottom-Up DeletionCase 1V’s sibling, S, is RedRotate S around P and recolor S & PNOT a terminal case – One of the other cases will now applyAll other cases apply when S is Black8/3/2007UMBC CSMC 341 Red-Black-Trees-28Case 1 DiagramPSV+PSV+Rotate S around PPV+SRecolor S & P8/3/2007UMBC CSMC 341 Red-Black-Trees-29Bottom-Up DeletionCase 2V’s sibling, S, is Black and has two Black children.Recolor S to be RedP absorbs V’s extra blacknessIf P is Red, we’re done (it absorbed the blackness)If P is Black, it now has extra blackness and problem has been propagated up the tree8/3/2007UMBC CSMC 341 Red-Black-Trees-210Case 2 diagramPSV+P+SVRecolor S P absorbs blacknessEither extra Black absorbed by P orP now has extra blackness8/3/2007UMBC CSMC 341 Red-Black-Trees-211Bottom-Up DeletionCase 3S is BlackS’s right child is RED (Left child either color)Rotate S around PSwap colors of S and P, and color S’s right child BlackThis is the terminal case – we’re done8/3/2007UMBC CSMC 341 Red-Black-Trees-212Case 3 diagramsPSV+PSV+Rotate S around PPSVSwap colors of S & PColor S’s right child Black8/3/2007UMBC CSMC 341 Red-Black-Trees-213Bottom-Up DeletionCase 4S is Black, S’s right child is Black and S’s left child is RedRotate S’s left child around SSwap color of S and S’s left childNow in case 38/3/2007UMBC CSMC 341 Red-Black-Trees-214Case 4 DiagramsPSV+PSV+Rotate S’s left around SPSV+Swap colors of S and S’s original left child8/3/2007UMBC CSMC 341 Red-Black-Trees-215Top-Down DeletionAn alternative to the recursive “bottom-up” deletion is “top-down” deletion.This method is iterative. It moves down the tree only, “fixing” things as it goes.What is the goal of top-down deletion?8/3/2007UMBC CSMC 341 Red-Black-Trees-216655080106070 9062Perform the following deletions, in the order specifiedDelete 90, Delete 80, Delete
View Full Document
Unlocking...