Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 56
Текст из файла (страница 56)
The procedure OSSELECT(x, i) returns a pointer to the node containing the ith smallest key in the subtreerooted at x. To find the ith smallest key in an order-statistic tree T , we call OSSELECT(root[T], i).OS-SELECT(x, i)1 r ← size[left[x]]+12 if i = r3then return x4 elseif i< r5then return OS-SELECT(left[x], i)6 else return OS-SELECT(right[x], i – r)The idea behind OS-SELECT is similar to that of the selection algorithms in Chapter 9. Thevalue of size[left[x]] is the number of nodes that come before x in an inorder tree walk of thesubtree rooted at x.
Thus, size[left[x]] + 1 is the rank of x within the subtree rooted at x.In line 1 of OS-SELECT, we compute r, the rank of node x within the subtree rooted at x. If i= r, then node x is the ith smallest element, so we return x in line 3. If i< r, then the ithsmallest element is in x's left subtree, so we recurse on left[x] in line 5. If i > r, then the ithsmallest element is in x's right subtree. Since there are r elements in the subtree rooted at xthat come before x's right subtree in an inorder tree walk, the ith smallest element in thesubtree rooted at x is the (i – r)th smallest element in the subtree rooted at right[x]. Thiselement is determined recursively in line 6.To see how OS-SELECT operates, consider a search for the 17th smallest element in theorder-statistic tree of Figure 14.1.
We begin with x as the root, whose key is 26, and with i =17. Since the size of 26's left subtree is 12, its rank is 13. Thus, we know that the node withrank 17 is the 17 - 13 = 4th smallest element in 26's right subtree. After the recursive call, x isthe node with key 41, and i = 4. Since the size of 41's left subtree is 5, its rank within itssubtree is 6. Thus, we know that the node with rank 4 is the 4th smallest element in 41's leftsubtree. After the recursive call, x is the node with key 30, and its rank within its subtree is 2.Thus, we recurse once again to find the 4 × 2 = 2nd smallest element in the subtree rooted atthe node with key 38. We now find that its left subtree has size 1, which means it is thesecond smallest element.
Thus, a pointer to the node with key 38 is returned by the procedure.Because each recursive call goes down one level in the order-statistic tree, the total time forOS-SELECT is at worst proportional to the height of the tree. Since the tree is a red-blacktree, its height is O(lg n), where n is the number of nodes. Thus, the running time of OSSELECT is O(lg n) for a dynamic set of n elements.Determining the rank of an elementGiven a pointer to a node x in an order-statistic tree T, the procedure OS-RANK returns theposition of x in the linear order determined by an inorder tree walk of T.OS-RANK(T, x)1 r ← size[left[x]] + 12 y ← x3 while y ≠ root[T]4do if y = right[p[y]]5then r ← r + size[left[p[y]]] + 16y ← p[y]7 return rThe procedure works as follows. The rank of x can be viewed as the number of nodespreceding x in an inorder tree walk, plus 1 for x itself.
OS-RANK maintains the followingloop invariant:•At the start of each iteration of the while loop of lines 3–6, r is the rank of key[x] inthe subtree rooted at node y.We use this loop invariant to show that OS-RANK works correctly as follows:•••Initialization: Prior to the first iteration, line 1 sets r to be the rank of key[x] withinthe subtree rooted at x.
Setting y ← x in line 2 makes the invariant true the first timethe test in line 3 executes.Maintenance: At the end of each iteration of the while loop, we set y ← p[y]. Thuswe must show that if r is the rank of key[x] in the subtree rooted at y at the start of theloop body, then r is the rank of key[x] in the subtree rooted at p[y] at the end of theloop body. In each iteration of the while loop, we consider the subtree rooted at p[y].We have already counted the number of nodes in the subtree rooted at node y thatprecede x in an inorder walk, so we must add the nodes in the subtree rooted at y'ssibling that precede x in an inorder walk, plus 1 for p[y] if it, too, precedes x.
If y is aleft child, then neither p[y] nor any node in p[y]'s right subtree precedes x, so we leaver alone. Otherwise, y is a right child and all the nodes in p[y]'s left subtree precede x,as does p[y] itself. Thus, in line 5, we add size[left[p[y]]] + 1 to the current value of r.Termination: The loop terminates when y = root[T], so that the subtree rooted at y isthe entire tree. Thus, the value of r is the rank of key[x] in the entire tree.As an example, when we run OS-RANK on the order-statistic tree of Figure 14.1 to find therank of the node with key 38, we get the following sequence of values of key[y] and r at thetop of the while loop:iteration key[y] r12343830412624417The rank 17 is returned.Since each iteration of the while loop takes O(1) time, and y goes up one level in the tree witheach iteration, the running time of OS-RANK is at worst proportional to the height of the tree:O(lg n) on an n-node order-statistic tree.Maintaining subtree sizesGiven the size field in each node, OS-SELECT and OS-RANK can quickly compute orderstatistic information.
But unless these fields can be efficiently maintained by the basicmodifying operations on red-black trees, our work will have been for naught. We shall nowshow that subtree sizes can be maintained for both insertion and deletion without affecting theasymptotic running time of either operation.We noted in Section 13.3 that insertion into a red-black tree consists of two phases. The firstphase goes down the tree from the root, inserting the new node as a child of an existing node.The second phase goes up the tree, changing colors and ultimately performing rotations tomaintain the red-black properties.To maintain the subtree sizes in the first phase, we simply increment size[x] for each node xon the path traversed from the root down toward the leaves.
The new node added gets a size of1. Since there are O(lg n) nodes on the traversed path, the additional cost of maintaining thesize fields is O(lg n).In the second phase, the only structural changes to the underlying red-black tree are caused byrotations, of which there are at most two. Moreover, a rotation is a local operation: only twonodes have their size fields invalidated. The link around which the rotation is performed isincident on these two nodes.
Referring to the code for LEFT-ROTATE(T, x) in Section 13.2,we add the following lines:12 size[y] ← size[x]13 size[x] ← size[left[x]] + size[right[x]] + 1Figure 14.2 illustrates how the fields are updated. The change to RIGHT-ROTATE issymmetric.Figure 14.2: Updating subtree sizes during rotations. The link around which the rotation isperformed is incident on the two nodes whose size fields need to be updated. The updates arelocal, requiring only the size information stored in x, y, and the roots of the subtrees shown astriangles.Since at most two rotations are performed during insertion into a red-black tree, only O(1)additional time is spent updating size fields in the second phase.
Thus, the total time forinsertion into an n-node order-statistic tree is O(lg n), which is asymptotically the same as foran ordinary red-black tree.Deletion from a red-black tree also consists of two phases: the first operates on the underlyingsearch tree, and the second causes at most three rotations and otherwise performs no structuralchanges. (See Section 13.4.) The first phase splices out one node y. To update the subtreesizes, we simply traverse a path from node y up to the root, decrementing the size field of eachnode on the path. Since this path has length O(lg n) in an n-node red-black tree, the additionaltime spent maintaining size fields in the first phase is O(lg n).
The O(1) rotations in thesecond phase of deletion can be handled in the same manner as for insertion. Thus, bothinsertion and deletion, including the maintenance of the size fields, take O(lg n) time for an nnode order-statistic tree.Exercises 14.1-1Show how OS-SELECT(T, 10) operates on the red-black tree T of Figure 14.1.Exercises 14.1-2Show how OS-RANK(T, x) operates on the red-black tree T of Figure 14.1 and the node xwith key[x] = 35.Exercises 14.1-3Write a nonrecursive version of OS-SELECT.Exercises 14.1-4Write a recursive procedure OS-KEY-RANK(T, k) that takes as input an order-statistic tree Tand a key k and returns the rank of k in the dynamic set represented by T . Assume that thekeys of T are distinct.Exercises 14.1-5Given an element x in an n-node order-statistic tree and a natural number i, how can the ithsuccessor of x in the linear order of the tree be determined in O(lg n) time?Exercises 14.1-6Observe that whenever the size field of a node is referenced in either OS-SELECT or OSRANK, it is used only to compute the rank of the node in the subtree rooted at that node.Accordingly, suppose we store in each node its rank in the subtree of which it is the root.Show how this information can be maintained during insertion and deletion.
(Remember thatthese two operations can cause rotations.)Exercises 14.1-7Show how to use an order-statistic tree to count the number of inversions (see Problem 2-4) inan array of size n in time O(n lg n).Exercises 14.1-8: ⋆Consider n chords on a circle, each defined by its endpoints. Describe an O(n lg n)-timealgorithm for determining the number of pairs of chords that intersect inside the circle. (Forexample, if the n chords are all diameters that meet at the center, then the correct answer is.) Assume that no two chords share an endpoint.14.2 How to Augment a Data StructureThe process of augmenting a basic data structure to support additional functionality occursquite frequently in algorithm design.
It will be used again in the next section to design a datastructure that supports operations on intervals. In this section, we shall examine the stepsinvolved in such augmentation. We shall also prove a theorem that allows us to augment redblack trees easily in many cases.Augmenting a data structure can be broken into four steps:1. choosing an underlying data structure,2. determining additional information to be maintained in the underlying data structure,3. verifying that the additional information can be maintained for the basic modifyingoperations on the underlying data structure, and4.
developing new operations.As with any prescriptive design method, you should not blindly follow the steps in the ordergiven. Most design work contains an element of trial and error, and progress on all stepsusually proceeds in parallel. There is no point, for example, in determining additionalinformation and developing new operations (steps 2 and 4) if we will not be able to maintainthe additional information efficiently.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
