DOC PREVIEW
CMU CS 15122 - Lecture

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:

IntroductionThree InvariantsInsertionRotationsAbstract Data Types RevisitedDefining InvariantsImplementing InsertionImplementing RebalancingLecture Notes onRed/Black Trees15-122: Principles of Imperative ComputationFrank PfenningLecture 17October 21, 20101 IntroductionIn this lecture we discuss an ingenious way to maintain the balance invari-ant for binary search trees. The resulting data structure of red/black trees isused in a number of standard library implementations in C, C++, and Java.2 Three InvariantsA red/black tree is a binary search tree in which each node is colored eitherred or black. At the interface, we maintain three invariants:Ordering Invariant This is the same as for binary search trees: all the keysto left of a node are smaller, and all the keys to the right of a node arelarger than the key at the node itself.Height Invariant The number of black nodes on every path from the rootto each leaf is the same. We call this the black height of the tree.Color Invariant No two consecutive nodes are red.The balance and color invariants together imply that the longest path fromthe root to a leaf is at most twice as long as the shortest path. Since insertand search in a binary search tree have time proportional to the length ofthe path from the root to the leaf, this guarantees O(log(n)) times for theseoperations, even if the tree is not perfectly balanced. We therefore refer tothe height and color invariants collectively as the balance invariant.LECTURE NOTES OCTOBER 21, 2010Red/Black Trees L17.23 InsertionThe trick is, of course, to maintain all three invariants while sticking to thelogarithmic time bound for each insert and search operation. Search is easy,since the search algorithm does not require the node colors: it works exactlyas for the general case of balanced binary trees.Insertion, however, is not obvious. Let’s try just following the usualalgorithm for insertion. We compare the key of the new element with thekey at the root. If it is equal, we replace the current element. If it is less werecursively insert into the left subtree. If it is greater, we recursively insertinto the right subtree. Below is a concrete example.16#10#19#1# 13#7#4#red#node#black#node#black#height#=#2#color#inv.#sa<sfied#If we want to insert a new element with a key of 14, the insertion algorithmsketched above would put it to the right of 13. In order to preverse theLECTURE NOTES OCTOBER 21, 2010Red/Black Trees L17.3height invariant, we must color the new node red.red$node$black$node$black$height$=$2$color$inv.$sa5sfied$16$10$19$1$ 13$7$4$14$Both color and height invariants are still satisfied, as is the ordering invari-ant (which we always preserve).Now consider another insertion, this time of an element with key 15.This is inserted to the right of the node with key 14. Again, to preserve theheight invariant we must color it red, but this violates the color invariantsince we have to adjacent red nodes.red$node$black$node$black$height$=$2$color$inv.$violated$at$14‐15$16$10$19$1$ 13$7$4$14$15$In order to restore the color invariant between 14 and 15 we can apply a leftrotation, moving 14 up in the tree and 13 to the left. At the same time weLECTURE NOTES OCTOBER 21, 2010Red/Black Trees L17.4recolor 15 to be black, so as to remove the color conflict while preservingthe black height invariant. However, we introduce a new color conflictbetween 14 and its parent.black&height&=&2&color&inv.&restored&at&14‐15&color&inv.&violated&at&16‐14&16&10&19&1& 14&7&4&15&13&Now we can apply a right rotation, moving 14 up one level, immediatelyfollowed by a left rotation, moving 14 up to the root.16#10#19#1#14#7#4#15#13#16#10#19#1#14#7#4#15#13#Such a sequence of two rotations is called a double rotation. The result nowsatisfies the height invariant (still with height 2) and the color invariant.We can apply one further simple step, which is to recolor the root toblack. This increases the black height on every path from the root by one, soit preserves the height invariant. Generally speaking, the fewer red nodesLECTURE NOTES OCTOBER 21, 2010Red/Black Trees L17.5in the tree the fewer rotations will be forced, which is why we perform thisrecoloring. The final result is16#10#19#1#14#7#4#15#13#black#height#=#3#color#inv.#sa;sfied#4 RotationsThe general shape of a left rotation is shown in the following diagram. Witheach potential subtree and its interval we also show the black height of thethe tree. The whole tree has black height h + 1 which means each elidedsubtree must have height h.z"y"(‐∞,"+∞)"(z,"+∞)"(‐∞,"x)" (y,"z)"(x,"y)"x"x"y"(‐∞,"+∞)"(z,"+∞)"(‐∞,"x)"(x,"y)"(y,"z)"z"h"h"h"h"h"h" h" h"h+1"h+1"We see that all invariants are preserved, and the color invariant is restored.Of course, if this is a subtree below a red node, the tree on the left wouldsatisfy the color invariant at the connection to its parent, while the tree onthe right would not. We also saw this in the example.LECTURE NOTES OCTOBER 21, 2010Red/Black Trees L17.6The right rotation is entirely symmetric, so we don’t show it here.The double rotation is best thought of as a single operation, so we canexamine its shape directly to verify that it preserves the invariants.z"y"(‐∞,"+∞)"(z,"+∞)"(‐∞,"x)" (y,"z)"(x,"y)"x"x"y"(‐∞,"+∞)"(z,"+∞)"(‐∞,"x)"(x,"y)" (y,"z)"z"h"h" h"h"h"h" h" h"h+1"h+1"Observe that all invariants are preserved and, in fact, the tree on the rightdoes observe the color invariant. As with a single rotation, however, wemay still violate the color invariant at the interface of the node y at the topand its parent.5 Abstract Data Types RevisitedWe revisit some of the ideas underlying abstract types, as they are exhib-ited in this implementation. One of them is the fact that sometimes theclient has to provide some operations to the implementation of an abstracttype. Exactly which operations have to be supplied varies from case tocase. Here, the client needs to provide the type of elem of elements (whichmust be a pointer type so it can be null), the function elem_key to extractkeys from elements, and compare which compares two keys and returnstheir order ( < 0 for less, = 0 for equal and > 0 for greater). First, the typedefinitions and the functions themselves./* elements */struct elem {string word; /* key */int count; /* information */};/* key comparison */int compare(string s1, string s2) {LECTURE NOTES OCTOBER 21, 2010Red/Black Trees L17.7return string_compare(s1,s2);}/*


View Full Document

CMU CS 15122 - Lecture

Download Lecture
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 Lecture 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 Lecture 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?