DOC PREVIEW
UMBC CMSC 341 - Red-Black Trees

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 DiagramsPowerPoint PresentationRed-Black TreesBottom-Up DeletionRecall “ordinary” BST Delete1. If vertex to be deleted is a leaf, just delete it.2. If vertex to be deleted has just one child, replace it with that child3. If vertex to be deleted has two children, replace the value in the node by it’s in-order predecessor/successor’s value then delete the in-order predecessor/successor (a recursive step)Bottom-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??Which 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 pathFixing the problem•Think 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 childTerminology•The node just deleted was U•The node that replaces it is V, which has an extra unit of blackness•The parent of V is P•The sibling of V is SBlack NodeRed NodeRed or Black and don’t careBottom-Up DeletionCase 1•V’s sibling, S, is Red–Rotate S around P and recolor S & P•NOT a terminal case – One of the other cases will now apply•All other cases apply when S is BlackCase 1 DiagramPSV+PSV+RotatePV+SRecolorBottom-Up DeletionCase 2•V’s sibling, S, is black and has two black children.–Recolor S to be Red–P absorbs V’s extra blackness•If P is Red, we’re done•If P is Black, it now has extra blackness and problem has been propagated up the treeCase 2 diagramPSV+P+SVRecolor and absorbEither extra black absorbed by P orP now has extra blacknessBottom-Up DeletionCase 3•S is black•S’s RIGHT child is RED (Left child either color)–Rotate S around P–Swap colors of S and P, and color S’s Right child Black•This is the terminal case – we’re doneCase 3 diagramsPSV+PSVRotatePSVRecolorBottom-Up DeletionCase 4•S is Black, S’s right child is Black and S’s left child is Red–Rotate S’s left child around S–Swap color of S and S’s left child–Now in case 3Case 4 DiagramsPSV+PSV+RotatePSV+Recolor655080106070 9062Perform the following deletions, in the order specifiedDelete 90, Delete 80, Delete


View Full Document

UMBC CMSC 341 - Red-Black Trees

Download Red-Black Trees
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Red-Black Trees and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Red-Black Trees 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?