of 15
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
  Lecture Notes onRed/Black Trees 15-122: Principles of Imperative ComputationFrank PfenningLecture 17October 21, 2010 1 Introduction In 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 Invariants Ared/blacktreeisabinarysearchtreeinwhicheachnodeiscoloredeitherred 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 of the 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 . L ECTURE  N OTES  O CTOBER  21, 2010  Red/Black Trees L17.2 3 Insertion The trick is, of course, to maintain all three invariants while sticking to thelogarithmictimeboundforeachinsertandsearchoperation. Searchiseasy,sincethesearchalgorithmdoesnotrequirethenodecolors: itworksexactlyas 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. ! !$ !% ! !& ' ( )*+ ,-+* ./012 ,-+* ./012 3*4536 7 8 1-/-) 4,9: ;0<;=*+ 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 the L ECTURE  N OTES  O CTOBER  21, 2010  Red/Black Trees L17.3 height invariant, we must color the new node red. ! # %&# '()*+ %&# '()*+ , -.,/ 0 1 *&(&! -%23 4)546 # 78 79 7: 7 7; < = 7= 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.   ! # %&# '()*+ %&# '()*+ , -.,/ 0 1 *&(&! -%23 2-&()/ # )/ 45647 48 49 4: 4 4; < 5 45 47 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 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 preservingthe black height invariant. However, we introduce a new color conflict between  14  and its parent. ! #$% '()*'+ , - $. ./ )012 /(3+./(4 #+ 56758 $. ./ )012 1). #+(4 #+ 59756 59 5: 5; 5 56 < 6 58 5= Now we can apply a right rotation, moving  14  up one level, immediatelyfollowed by a left rotation, moving  14  up to the root.   ! !$ !% ! !& ' & !( !) ! !$ !% ! !& ' & !( !) 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 to black. Thisincreasestheblackheightoneverypathfromtherootbyone,soit preserves the height invariant. Generally speaking, the fewer red nodes L ECTURE  N OTES  O CTOBER  21, 2010


Sep 14, 2019
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!