Topic 19RedBlack TreesRedBlack Trees"People in every direction pyNo words exchanged No time to exchange And all the little ants are marching gRed 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 gg p , ylights. 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 JobCS 307 Fundamentals of Computer Science Red Black Trees1y, p ,( ),Attendance Question 1882000 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. 11C1000C.1000D. 1999E4000E.4000CS 307 Fundamentals of Computer Science Red Black Trees2Binary Search Trees88Average case and worst case Big O for– insertion– deletion– access8Balance is important. Unbalanced trees give worse than log N times for the basic tree goperations8Can balance be guaranteed?Can balance be guaranteed?CS 307 Fundamentals of Computer Science Red Black Trees3Red Black Trees88A BST with more complex algorithms to ensure balance8Each node is labeled as Red or Black.8Path: A unique series of links (edges) at u que se es o s (edges)traverses from the root to each node. –The number of edges (links) that must beThe number of edges (links) that must be followed is the path length8InRedBlack trees paths from the root toIn RedBlack trees paths from the root to elements with 0 or 1 child are of particular interestCS 307 Fundamentals of Computer Science Red Black Trees4interestPaths to Single or Zero Child NodesNodes8How many?1912351621316562111CS 307 Fundamentals of Computer Science Red Black Trees5Red Black Tree Rules1. Every node is colored either Redor black2. The root is black3If d idit hild t3.If a node is redits children must be black. (a.k.a. the red rule)4. Every path from a node to a null link must contain the samelink must contain the same number of black nodes (a.k.a. the path rule)CS 307 Fundamentals of Computer Science Red Black Trees6the path rule)Example of a Red Black Tree8 The root of a Red Black tree is black8 Every 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 pathsRule 4: The number of Black nodes must be the same in all paths from the root node to null nodes191912353165621CS 307 Fundamentals of Computer Science Red Black Trees730Red Black Tree?19123512050-10575135-5-8135100-6 80CS 307 Fundamentals of Computer Science Red Black Trees8Attendance Question 288Is the tree on the previous slide a binary search tree? Is it a red black tree?BST? Red-Black?A. No NoB. No YesCYesNoC.YesNoD. Yes YesCS 307 Fundamentals of Computer Science Red Black Trees9Red Black Tree?1912353163160Perfect?F ll?Full?Complete?CS 307 Fundamentals of Computer Science Red Black Trees10Attendance Question 388Is the tree on the previous slide a binary search tree? Is it a red black tree?BST? Red-Black?A. No NoB. No YesCYesNoC.YesNoD. Yes YesCS 307 Fundamentals of Computer Science Red Black Trees11Implications of the Rules88If a Red node has any children, it must have two children and they must be Black. (Why?)8If a Black node has only one child that child must be a Red leaf. (Why?)8Due to the rules there are limits on how unbalanced a RedBlack tree may become.ubaacedaedac ee ay beco e– 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 Trees12Properties of Red Black Trees88If a Red Black Tree is complete, with all Black nodes except for Red leaves at the lowest level the height will be minimal, ~log N8To 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 slidepCS 307 Fundamentals of Computer Science Red Black Trees13Max Height Red Black Tree141235123556211356439921113152515258010070CS 307 Fundamentals of Computer Science Red Black Trees14Maintaining the Red Black Properties in a TreeProperties in a Tree8Insertions8Must maintain rules of Red Black Tree.8New Node always a leafNew Node always a leaf– can't be black or we will violate rule 4–therefore the new leaf must bered–therefore the new leaf must be red– If parent is black, done (trivial case)if parentredthings get interesting because ared–if parent red, things get interesting because a redleaf with a red parent violates rule 3CS 307 Fundamentals of Computer Science Red Black Trees15Insertions with Red Parent - ChildMust modify tree when insertion would result in RedParent-Child pair using color changes and30RedParent Child pair using color changes androtations.157085601020809050655CS 307 Fundamentals of Computer Science Red Black Trees1640 55Case 188Suppose sibling of parent is Black.– by convention null nodes are black8In the previous tree, true if we are inserting a 3 or an 8. – What about inserting a 99? Same case?8Let X be the new leaf Node P be itsRedLet X be the new leaf Node, P be its RedParent, S the Black sibling and G, P's and S's parent and X's grandparentSs parent and Xs grandparent– What color is G?CS 307 Fundamentals of Computer Science Red Black Trees17Case 1 - The PictureGPSEDXCABRelative to GXcouldbeaninsideoroutsidenodeRelative to G, Xcould be an insideor outsidenode.Outside -> left left or right right movesInside -> left right or right left movesCS 307 Fundamentals of Computer Science Red Black Trees18ggFixing the ProblemGPSEDXCABIf X is an outside node a single rotation between P and G fixes the problem.pA rotation is an exchange of roles between a parentand child node. So P becomes G's parent. Also must lPdGCS 307 Fundamentals of Computer Science Red Black Trees19recolor Pand G.Single RotationPXGSCABEDApparent rule violation?ppCS 307 Fundamentals of Computer Science Red Black Trees20Case 288What if X is an inside node relative to G?– a single rotation will not work8Must perform a double rotation–rotate X and P– rotate X and GGPSPSEDXAEXABCCS 307 Fundamentals of Computer Science Red Black Trees21After Double RotationXPGCABSCABEDApparent rule violation?CS 307 Fundamentals of Computer Science
View Full Document
Unlocking...