Lecture Notes on Red Black Trees 15 122 Principles of Imperative Computation Frank Pfenning Lecture 17 October 21 2010 1 Introduction In this lecture we discuss an ingenious way to maintain the balance invariant for binary search trees The resulting data structure of red black trees is used in a number of standard library implementations in C C and Java 2 Three Invariants A red black tree is a binary search tree in which each node is colored either red or black At the interface we maintain three invariants Ordering Invariant This is the same as for binary search trees all the keys to left of a node are smaller and all the keys to the right of a node are larger than the key at the node itself Height Invariant The number of black nodes on every path from the root to 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 from the root to a leaf is at most twice as long as the shortest path Since insert and search in a binary search tree have time proportional to the length of the path from the root to the leaf this guarantees O log n times for these operations even if the tree is not perfectly balanced We therefore refer to the height and color invariants collectively as the balance invariant L ECTURE N OTES O CTOBER 21 2010 Red Black Trees 3 L17 2 Insertion The trick is of course to maintain all three invariants while sticking to the logarithmic time bound for each insert and search operation Search is easy since the search algorithm does not require the node colors it works exactly as for the general case of balanced binary trees Insertion however is not obvious Let s try just following the usual algorithm for insertion We compare the key of the new element with the key at the root If it is equal we replace the current element If it is less we recursively insert into the left subtree If it is greater we recursively insert into the right subtree Below is a concrete example 10 4 1 16 7 13 black height 2 color inv sa s ed 19 red node black node If we want to insert a new element with a key of 14 the insertion algorithm sketched above would put it to the right of 13 In order to preverse the L ECTURE N OTES O CTOBER 21 2010 Red Black Trees L17 3 height invariant we must color the new node red 10 4 16 1 7 13 red node black height 2 color inv sa5s ed 19 14 black node Both color and height invariants are still satisfied as is the ordering invariant 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 the height invariant we must color it red but this violates the color invariant since we have to adjacent red nodes 10 4 16 1 7 red node black node 13 black height 2 color inv violated at 14 15 19 14 15 In order to restore the color invariant between 14 and 15 we can apply a left rotation moving 14 up in the tree and 13 to the left At the same time we L ECTURE N OTES O CTOBER 21 2010 Red Black Trees L17 4 recolor 15 to be black so as to remove the color conflict while preserving the black height invariant However we introduce a new color conflict between 14 and its parent 10 4 black height 2 color inv restored at 14 15 color inv violated at 16 14 16 1 7 14 19 15 13 Now we can apply a right rotation moving 14 up one level immediately followed by a left rotation moving 14 up to the root 10 14 4 10 14 16 1 7 16 4 13 13 15 19 1 15 19 7 Such a sequence of two rotations is called a double rotation The result now satisfies the height invariant still with height 2 and the color invariant We can apply one further simple step which is to recolor the root to black This increases the black height on every path from the root by one so it preserves the height invariant Generally speaking the fewer red nodes L ECTURE N OTES O CTOBER 21 2010 Red Black Trees L17 5 in the tree the fewer rotations will be forced which is why we perform this recoloring The final result is 14 10 16 black height 3 color inv sa s ed 4 15 13 1 4 19 7 Rotations The general shape of a left rotation is shown in the following diagram With each potential subtree and its interval we also show the black height of the the tree The whole tree has black height h 1 which means each elided subtree must have height h h 1 x x h x y h y z h h 1 y y z z h x z x x y h h y z z h h 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 would satisfy the color invariant at the connection to its parent while the tree on the right would not We also saw this in the example L ECTURE N OTES O CTOBER 21 2010 Red Black Trees L17 6 The 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 can examine its shape directly to verify that it preserves the invariants h 1 x x h x y h h 1 y z x y z h y z h z x x y h h y z z h h Observe that all invariants are preserved and in fact the tree on the right does observe the color invariant As with a single rotation however we may still violate the color invariant at the interface of the node y at the top and its parent 5 Abstract Data Types Revisited We revisit some of the ideas underlying abstract types as they are exhibited in this implementation One of them is the fact that sometimes the client has to provide some operations to the implementation of an abstract type Exactly which operations have to be supplied varies from case to case Here the client needs to provide the type of elem of elements which must be a pointer type so it can be null the function elem key to extract keys from elements and compare which compares two keys and returns their order 0 for less 0 for equal and 0 for greater First the type definitions and the functions themselves elements struct elem string word key int count information key comparison int compare string …