Topic 19 Red Black TreesAttendance Question 1Binary Search TreesRed Black TreesPaths to Single or Zero Child NodesRed Black Tree RulesExample of a Red Black TreeRed Black Tree?Attendance Question 2Slide 10Attendance Question 3Implications of the RulesProperties of Red Black TreesMax Height Red Black TreeMaintaining the Red Black Properties in a TreeInsertions with Red Parent - ChildCase 1Case 1 - The PictureFixing the ProblemSingle RotationCase 2After Double RotationCase 3 Sibling is Red, not BlackFixing Tree when S is RedMore on InsertExample of Inserting Sorted NumbersInsert 2Insert 3Insert 4Insert 5Finish insert of 5Insert 6Finishing insert of 6Insert 7Finish insert of 7Insert 8Still Inserting 8Finish inserting 8Insert 9Finish Inserting 9Insert 10Insert 11Finish inserting 11CS 307 Fundamentals of Computer Science Red Black Trees1Topic 19 Red Black Trees"People in every direction No words exchanged No time to exchange And all the little ants are marching Red and black antennas waving" -Ants Marching, Dave Matthew's Band"Welcome to L.A.'s Automated Traffic Surveillance and Control Operations Center. See, they use video feeds from intersections and specifically designed algorithms to predict traffic conditions, and thereby control traffic lights. So all I did was come up with my own... kick ass algorithm to sneak in, and now we own the place."-Lyle, the Napster, (Seth Green), The Italian JobAttendance Question 12000 elements are inserted one at a time into an initially empty binary search tree using the traditional algorithm. What is the maximum possible height of the resulting tree?A.1B.11C.1000D.1999E.4000CS 307 Fundamentals of Computer Science Red Black Trees2CS 307 Fundamentals of Computer Science Red Black Trees3Binary Search TreesAverage case and worst case Big O for–insertion–deletion–accessBalance is important. Unbalanced trees give worse than log N times for the basic tree operationsCan balance be guaranteed?CS 307 Fundamentals of Computer Science Red Black Trees4Red Black TreesA BST with more complex algorithms to ensure balanceEach node is labeled as Red or Black.Path: A unique series of links (edges) traverses from the root to each node. –The number of edges (links) that must be followed is the path lengthIn Red Black trees paths from the root to elements with 0 or 1 child are of particular interestCS 307 Fundamentals of Computer Science Red Black Trees5Paths to Single or Zero Child NodesHow many?19123531656211CS 307 Fundamentals of Computer Science Red Black Trees6Red Black Tree Rules1. Every node is colored either Red or black2. The root is black3. If a node is red its children must be black. (a.k.a. the red rule)4. Every path from a node to a null link must contain the same number of black nodes (a.k.a. the path rule)CS 307 Fundamentals of Computer Science Red Black Trees7Example of a Red Black TreeThe root of a Red Black tree is blackEvery other node in the tree follows these rules:–Rule 3: If a node is Red, all of its children are Black–Rule 4: The number of Black nodes must be the same in all paths from the root node to null nodes191235316562130CS 307 Fundamentals of Computer Science Red Black Trees8Red Black Tree?1912350-10-5-8-6507513510080Attendance Question 2Is the tree on the previous slide a binary search tree? Is it a red black tree?BST? Red-Black?A. No NoB. No YesC. Yes NoD. Yes YesCS 307 Fundamentals of Computer Science Red Black Trees9CS 307 Fundamentals of Computer Science Red Black Trees10Red Black Tree?1912353160Perfect?Full?Complete?Attendance Question 3Is the tree on the previous slide a binary search tree? Is it a red black tree?BST? Red-Black?A. No NoB. No YesC. Yes NoD. Yes YesCS 307 Fundamentals of Computer Science Red Black Trees11CS 307 Fundamentals of Computer Science Red Black Trees12Implications of the RulesIf a Red node has any children, it must have two children and they must be Black. (Why?)If a Black node has only one child that child must be a Red leaf. (Why?)Due to the rules there are limits on how unbalanced a Red Black tree may become.–on the previous example may we hang a new node off of the leaf node that contains 0?CS 307 Fundamentals of Computer Science Red Black Trees13Properties of Red Black TreesIf a Red Black Tree is complete, with all Black nodes except for Red leaves at the lowest level the height will be minimal, ~log NTo get the max height for N elements there should be as many Red nodes as possible down one path and all other nodes are Black–This means the max height would be < 2 * log N–see example on next slideCS 307 Fundamentals of Computer Science Red Black Trees14Max Height Red Black Tree1412355643992111315258010070CS 307 Fundamentals of Computer Science Red Black Trees15Maintaining the Red Black Properties in a TreeInsertionsMust maintain rules of Red Black Tree.New Node always a leaf–can't be black or we will violate rule 4–therefore the new leaf must be red–If parent is black, done (trivial case)–if parent red, things get interesting because a red leaf with a red parent violates rule 3CS 307 Fundamentals of Computer Science Red Black Trees16Insertions with Red Parent - Child3015708580906010205065540 55Must modify tree when insertion would result in Red Parent - Child pair using color changes androtations.CS 307 Fundamentals of Computer Science Red Black Trees17Case 1Suppose sibling of parent is Black.–by convention null nodes are blackIn the previous tree, true if we are inserting a 3 or an 8. –What about inserting a 99? Same case?Let X be the new leaf Node, P be its Red Parent, S the Black sibling and G, P's and S's parent and X's grandparent–What color is G?CS 307 Fundamentals of Computer Science Red Black Trees18Case 1 - The PictureGPSEDXCABRelative to G, X could be an inside or outside node.Outside -> left left or right right movesInside -> left right or right left movesCS 307 Fundamentals of Computer Science Red Black Trees19Fixing the ProblemGPSEDXCAB If X is an outside node a single rotation between P and G fixes the problem.A rotation is an exchange of roles between a parentand child node. So P becomes G's parent. Also must recolor P and G.CS 307 Fundamentals of Computer Science Red Black Trees20Single RotationPXGSCABEDApparent rule violation?CS 307 Fundamentals of Computer Science Red Black Trees21Case 2What if X is an inside node relative to G?–a single rotation will not workMust
View Full Document
Unlocking...