Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 51
Текст из файла (страница 51)
According to property 4, atleast half the nodes on any simple path from the root to a leaf, not including the root, must beblack. Consequently, the black-height of the root must be at least h/2; thus,n ≥ 2h/2 - 1.Moving the 1 to the left-hand side and taking logarithms on both sides yields lg(n + 1) ≥ h/2,or h ≤ 2 lg(n + 1).An immediate consequence of this lemma is that the dynamic-set operations SEARCH,MINIMUM, MAXIMUM, SUCCESSOR, and PREDECESSOR can be implemented in O(lgn) time on red-black trees, since they can be made to run in O(h) time on a search tree ofheight h (as shown in Chapter 12) and any red-black tree on n nodes is a search tree withheight O(lg n). (Of course, references to NIL in the algorithms of Chapter 12 would have tobe replaced by nil[T].) Although the algorithms TREE-INSERT and TREE-DELETE fromChapter 12 run in O(lg n) time when given a red-black tree as input, they do not directlysupport the dynamic-set operations INSERT and DELETE, since they do not guarantee thatthe modified binary search tree will be a red-black tree.
We shall see in Sections 13.3 and13.4, however, that these two operations can indeed be supported in O(lg n) time.Exercises 13.1-1In the style of Figure 13.1(a), draw the complete binary search tree of height 3 on the keys {1,2, ..., 15}. Add the NIL leaves and color the nodes in three different ways such that the blackheights of the resulting red-black trees are 2, 3, and 4.Exercises 13.1-2Draw the red-black tree that results after TREE-INSERT is called on the tree in Figure 13.1with key 36. If the inserted node is colored red, is the resulting tree a red-black tree? What if itis colored black?Exercises 13.1-3Let us define a relaxed red-black tree as a binary search tree that satisfies red- blackproperties 1, 3, 4, and 5.
In other words, the root may be either red or black. Consider arelaxed red-black tree T whose root is red. If we color the root of T black but make no otherchanges to T, is the resulting tree a red-black tree?Exercises 13.1-4Suppose that we "absorb" every red node in a red-black tree into its black parent, so that thechildren of the red node become children of the black parent. (Ignore what happens to thekeys.) What are the possible degrees of a black node after all its red children are absorbed?What can you say about the depths of the leaves of the resulting tree?Exercises 13.1-5Show that the longest simple path from a node x in a red-black tree to a descendant leaf haslength at most twice that of the shortest simple path from node x to a descendant leaf.Exercises 13.1-6What is the largest possible number of internal nodes in a red-black tree with black-height k?What is the smallest possible number?Exercises 13.1-7Describe a red-black tree on n keys that realizes the largest possible ratio of red internal nodesto black internal nodes.
What is this ratio? What tree has the smallest possible ratio, and whatis the ratio?13.2 RotationsThe search-tree operations TREE-INSERT and TREE-DELETE, when run on a red-black treewith n keys, take O(lg n) time. Because they modify the tree, the result may violate the redblack properties enumerated in Section 13.1. To restore these properties, we must change thecolors of some of the nodes in the tree and also change the pointer structure.We change the pointer structure through rotation, which is a local operation in a search treethat preserves the binary-search-tree property.
Figure 13.2 shows the two kinds of rotations:left rotations and right rotations. When we do a left rotation on a node x, we assume that itsright child y is not nil[T]; x may be any node in the tree whose right child is not nil[T]. Theleft rotation "pivots" around the link from x to y. It makes y the new root of the subtree, with xas y's left child and y's left child as x's right child.Figure 13.2: The rotation operations on a binary search tree. The operation LEFTROTATE(T, x) transforms the configuration of the two nodes on the left into theconfiguration on the right by changing a constant number of pointers.
The configuration onthe right can be transformed into the configuration on the left by the inverse operationRIGHT-ROTATE(T, y). The letters α, β, and γ represent arbitrary subtrees. A rotationoperation preserves the binary-search-tree property: the keys in α precede key[x], whichprecedes the keys in β, which precede key[y], which precedes the keys in γ.The pseudocode for LEFT-ROTATE assumes that right[x] ≠ nil[T] and that the root's parentis nil[T].LEFT-ROTATE(T, x)▹ Set y.1y ← right[x]23right[x] ← left[y]p[left[y]] ← x456789p[y] ← p[x]▹ Link x's parent to y.if p[x] = nil[T]then root[T] ← yelse if x = left[p[x]]then left[p[x]] ← yelse right[p[x]] ← y1011left[y] ← xp[x] ← y▹ Turn y's left subtree into x's right subtree.▹ Put x on y's left.Figure 13.3 shows how LEFT-ROTATE operates.
The code for RIGHT-ROTATE issymmetric. Both LEFT-ROTATE and RIGHT-ROTATE run in O(1) time. Only pointers arechanged by a rotation; all other fields in a node remain the same.Figure 13.3: An example of how the procedure LEFT-ROTATE(T, x) modifies a binarysearch tree. Inorder tree walks of the input tree and the modified tree produce the same listingof key values.Exercises 13.2-1Write pseudocode for RIGHT-ROTATE.Exercises 13.2-2Argue that in every n-node binary search tree, there are exactly n - 1 possible rotations.Exercises 13.2-3Let a, b, and c be arbitrary nodes in subtrees α, β, and γ, respectively, in the left tree of Figure13.2.
How do the depths of a, b, and c change when a left rotation is performed on node x inthe figure?Exercises 13.2-4Show that any arbitrary n-node binary search tree can be transformed into any other arbitraryn-node binary search tree using O(n) rotations. (Hint: First show that at most n - 1 rightrotations suffice to transform the tree into a right-going chain.)Exercises 13.2-5: ⋆We say that a binary search tree T1 can be right-converted to binary search tree T2 if it ispossible to obtain T2 from T1 via a series of calls to RIGHT-ROTATE.
Give an example oftwo trees T1 and T2 such that T1 cannot be right-converted to T2. Then show that if a tree T1can be right-converted to T2, it can be right-converted using O(n2) calls to RIGHT-ROTATE.13.3 InsertionInsertion of a node into an n-node red-black tree can be accomplished in O(lg n) time. We usea slightly modified version of the TREE-INSERT procedure (Section 12.3) to insert node zinto the tree T as if it were an ordinary binary search tree, and then we color z red. Toguarantee that the red-black properties are pre- served, we then call an auxiliary procedureRB-INSERT-FIXUP to recolor nodes and perform rotations. The call RB-INSERT(T, z)inserts node z, whose key field is assumed to have already been filled in, into the red-blacktree T.RB-INSERT(T, z)1 y ← nil[T]2 x ← root[T]3 while x ≠ nil[T]4do y ← x5if key[z] < key[x]6then x ← left[x]7else x ← right[x]8 p[z] ← y9 if y = nil[T]10then root[T] ← z11else if key[z] < key[y]12then left[y] ← z13else right[y] ← z14 left[z] ← nil[T]15 right[z] ← nil[T]16 color[z] ← RED17 RB-INSERT-FIXUP(T, z)There are four differences between the procedures TREE-INSERT and RB-INSERT.
First, allinstances of NIL in TREE-INSERT are replaced by nil[T]. Second, we set left[z] and right[z]to nil[T] in lines 14–15 of RB-INSERT, in order to maintain the proper tree structure. Third,we color z red in line 16. Fourth, because coloring z red may cause a violation of one of thered-black properties, we call RB-INSERT-FIXUP(T, z) in line 17 of RB-INSERT to restorethe red-black properties.RB-INSERT-FIXUP(T, z)1 while color[p[z]] = RED2do if p[z] = left[p[p[z]]]3then y ← right[p[p[z]]]4if color[y] = RED5then color[p[z]] ← BLACK6color[y] ← BLACK7color[p[p[z]]] ← RED891011z ← p[p[z]]else if z = right[p[z]]then z ← p[z]LEFT-ROTATE(T, z)▹ Case 1▹ Case 1▹ Case 1▹ Case 1▹ Case 2▹ Case 212color[p[z]] ← BLACK13color[p[p[z]]] ← RED1415RIGHT-ROTATE(T, p[p[z]])else (same as then clausewith "right" and "left" exchanged)16 color[root[T]] ← BLACK▹ Case 3▹ Case 3▹ Case 3To understand how RB-INSERT-FIXUP works, we shall break our examination of the codeinto three major steps.
First, we shall determine what violations of the red-black properties areintroduced in RB-INSERT when the node z is inserted and colored red. Second, we shallexamine the overall goal of the while loop in lines 1–15. Finally, we shall explore each of thethree cases[1] into which the while loop is broken and see how they accomplish the goal.Figure 13.4 shows how RB-INSERT-FIXUP operates on a sample red-black tree.Figure 13.4: The operation of RB-INSERT-FIXUP.
(a) A node z after insertion. Since z andits parent p[z] are both red, a violation of property 4 occurs. Since z's uncle y is red, case 1 inthe code can be applied. Nodes are recolored and the pointer z is moved up the tree, resultingin the tree shown in (b). Once again, z and its parent are both red, but z's uncle y is black.Since z is the right child of p[z], case 2 can be applied. A left rotation is performed, and thetree that results is shown in (c).
Now z is the left child of its parent, and case 3 can be applied.A right rotation yields the tree in (d), which is a legal red-black tree.Which of the red-black properties can be violated upon the call to RB-INSERT-FIXUP?Property 1 certainly continues to hold, as does property 3, since both children of the newlyinserted red node are the sentinel nil[T]. Property 5, which says that the number of blacknodes is the same on every path from a given node, is satisfied as well, because node zreplaces the (black) sentinel, and node z is red with sentinel children. Thus, the onlyproperties that might be violated are property 2, which requires the root to be black, andproperty 4, which says that a red node cannot have a red child.
Both possible violations aredue to z being colored red. Property 2 is violated if z is the root, and property 4 is violated ifz's parent is red. Figure 13.4(a) shows a violation of property 4 after the node z has beeninserted.The while loop in lines 1–15 maintains the following three-part invariant:At the start of each iteration of the loop,a.
Node z is red.b. If p[z] is the root, then p[z] is black.c. If there is a violation of the red-black properties, there is at most one violation, and itis of either property 2 or property 4. If there is a violation of property 2, it occursbecause z is the root and is red.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
