Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 57
Текст из файла (страница 57)
Nevertheless, this four-step method provides a goodfocus for your efforts in augmenting a data structure, and it is also a good way to organize thedocumentation of an augmented data structure.We followed these steps in Section 14.1 to design our order-statistic trees. For step 1, wechose red-black trees as the underlying data structure.
A clue to the suitability of red-blacktrees comes from their efficient support of other dynamic-set operations on a total order, suchas MINIMUM, MAXIMUM, SUCCESSOR, and PREDECESSOR.For step 2, we provided the size field, in which each node x stores the size of the subtreerooted at x.
Generally, the additional information makes operations more efficient. Forexample, we could have implemented OS-SELECT and OS-RANK using just the keys storedin the tree, but they would not have run in O(lg n) time. Sometimes, the additionalinformation is pointer information rather than data, as in Exercise 14.2-1.For step 3, we ensured that insertion and deletion could maintain the size fields while stillrunning in O(lg n) time. Ideally, only a few elements of the data structure should need to beupdated in order to maintain the additional information. For example, if we simply stored ineach node its rank in the tree, the OS-SELECT and OS-RANK procedures would run quickly,but inserting a new minimum element would cause a change to this information in every nodeof the tree.
When we store subtree sizes instead, inserting a new element causes informationto change in only O(lg n) nodes.For step 4, we developed the operations OS-SELECT and OS-RANK. After all, the need fornew operations is why we bother to augment a data structure in the first place. Occasionally,rather than developing new operations, we use the additional information to expedite existingones, as in Exercise 14.2-1.Augmenting Red-Black TreesWhen red-black trees underlie an augmented data structure, we can prove that certain kinds ofadditional information can always be efficiently maintained by insertion and deletion, therebymaking step 3 very easy. The proof of the following theorem is similar to the argument fromSection 14.1 that the size field can be maintained for order-statistic trees.Theorem 14.1: (Augmenting a Red-Black Tree)Let f be a field that augments a red-black tree T of n nodes, and suppose that the contents of ffor a node x can be computed using only the information in nodes x, left[x], and right[x],including f[left[x]] and f[right[x]].
Then, we can maintain the values of f in all nodes of Tduring insertion and deletion without asymptotically affecting the O(lg n) performance ofthese operations.Proof The main idea of the proof is that a change to an f field in a node x propagates only toancestors of x in the tree. That is, changing f[x] may require f[p[x]] to be updated, but nothingelse; updating f[p[x]] may require f[p[p[x]]] to be updated, but nothing else; and so on up thetree.
When f[root[T]] is updated, no other node depends on the new value, so the processterminates. Since the height of a red-black tree is O(lg n), changing an f field in a node costsO(lg n) time in updating nodes dependent on the change.Insertion of a node x into T consists of two phases. (See Section 13.3.) During the first phase,x is inserted as a child of an existing node p[x]. The value for f[x] can be computed in O(1)time since, by supposition, it depends only on information in the other fields of x itself and theinformation in x's children, but x's children are both the sentinel nil[T].
Once f[x] is computed,the change propagates up the tree. Thus, the total time for the first phase of insertion is O(lgn). During the second phase, the only structural changes to the tree come from rotations. Sinceonly two nodes change in a rotation, the total time for updating the f fields is O(lg n) perrotation. Since the number of rotations during insertion is at most two, the total time forinsertion is O(lg n).Like insertion, deletion has two phases. (See Section 13.4.) In the first phase, changes to thetree occur if the deleted node is replaced by its successor, and when either the deleted node orits successor is spliced out. Propagating the updates to f caused by these changes costs at mostO(lg n) since the changes modify the tree locally.
Fixing up the red-black tree during thesecond phase requires at most three rotations, and each rotation requires at most O(lg n) timeto propagate the updates to f . Thus, like insertion, the total time for deletion is O(lg n).In many cases, such as maintenance of the size fields in order-statistic trees, the cost ofupdating after a rotation is O(1), rather than the O(lg n) derived in the proof of Theorem 14.1.Exercise 14.2-4 gives an example.Exercises 14.2-1Show how the dynamic-set queries MINIMUM, MAXIMUM, SUCCESSOR, andPREDECESSOR can each be supported in O(1) worst-case time on an augmented orderstatistic tree. The asymptotic performance of other operations on order-statistic trees shouldnot be affected.
(Hint: Add pointers to nodes.)Exercises 14.2-2Can the black-heights of nodes in a red-black tree be maintained as fields in the nodes of thetree without affecting the asymptotic performance of any of the red-black tree operations?Show how, or argue why not.Exercises 14.2-3Can the depths of nodes in a red-black tree be efficiently maintained as fields in the nodes ofthe tree? Show how, or argue why not.Exercises 14.2-4: ⋆Let ⊗ be an associative binary operator, and let a be a field maintained in each node of a redblack tree.
Suppose that we want to include in each node x an additional field f such that f[x] =a[x1] ⊗ a[x2] ⊗ ··· ⊗ a[xm], where x1, x2,..., xm is the inorder listing of nodes in the subtreerooted at x. Show that the f fields can be properly updated in O(1) time after a rotation.Modify your argument slightly to show that the size fields in order-statistic trees can bemaintained in O(1) time per rotation.Exercises 14.2-5: ⋆We wish to augment red-black trees with an operation RB-ENUMERATE(x, a, b) that outputsall the keys k such that a ≤ k ≤ b in a red-black tree rooted at x. Describe how RBENUMERATE can be implemented in Θ(m +lg n) time, where m is the number of keys thatare output and n is the number of internal nodes in the tree. (Hint: There is no need to addnew fields to the red-black tree.)14.3 Interval TreesIn this section, we shall augment red-black trees to support operations on dynamic sets ofintervals.
A closed interval is an ordered pair of real numbers [t1, t2], with t1 ≤ t2. The interval[t1, t2] represents the set {t R : t1 ≤ t ≤ t2}. Open and half-open intervals omit both or one ofthe endpoints from the set, respectively. In this section, we shall assume that intervals areclosed; extending the results to open and half-open intervals is conceptually straightforward.Intervals are convenient for representing events that each occupy a continuous period of time.We might, for example, wish to query a database of time intervals to find out what eventsoccurred during a given interval. The data structure in this section provides an efficient meansfor maintaining such an interval database.We can represent an interval [t1, t2] as an object i, with fields low[i] = t1 (the low endpoint)and high[i] = t2(the high endpoint). We say that intervals i and i' overlap if i ∩ i' ≠ ø, that is, iflow[i] ≤ high[i'] and low[i'] ≤ high[i].
Any two intervals i and i' satisfy the intervaltrichotomy; that is, exactly one of the following three properties holds:a. i and i' overlap,b. i is to the left of i' (i.e., high[i]< low[i']),c. i is to the right of i' (i.e., high[i']< low[i]).Figure 14.3 shows the three possibilities.Figure 14.3: The interval trichotomy for two closed intervals i and i'.
(a) If i and i' overlap,there are four situations; in each, low[i] ≤ high[i'] and low[i'] ≤ high[i]. (b) The intervals donot overlap, and high[i]< low[i']. (c) The intervals do not overlap, and high[i']< low[i].An interval tree is a red-black tree that maintains a dynamic set of elements, with eachelement x containing an interval int[x]. Interval trees support the following operations.•••INTERVAL-INSERT(T, x) adds the element x, whose int field is assumed to containan interval, to the interval tree T.INTERVAL-DELETE(T, x) removes the element x from the interval tree T.INTERVAL-SEARCH(T, i) returns a pointer to an element x in the interval tree Tsuch that int[x] overlaps interval i, or the sentinel nil[T] if no such element is in the set.Figure 14.4 shows how an interval tree represents a set of intervals. We shall track the fourstep method from Section 14.2 as we review the design of an interval tree and the operationsthat run on it.Figure 14.4: An interval tree.
(a) A set of 10 intervals, shown sorted bottom to top by leftendpoint. (b) The interval tree that represents them. An inorder tree walk of the tree lists thenodes in sorted order by left endpoint.Step 1: Underlying Data StructureWe choose a red-black tree in which each node x contains an interval int[x] and the key of x isthe low endpoint, low[int[x]], of the interval. Thus, an inorder tree walk of the data structurelists the intervals in sorted order by low endpoint.Step 2: Additional InformationIn addition to the intervals themselves, each node x contains a value max[x], which is themaximum value of any interval endpoint stored in the subtree rooted at x.Step 3: Maintaining the InformationWe must verify that insertion and deletion can be performed in O(lg n) time on an intervaltree of n nodes. We can determine max[x] given interval int[x] and the max values of node x'schildren:max[x] = max(high[int[x]], max[left[x]], max[right[x]]).Thus, by Theorem 14.1, insertion and deletion run in O(lg n) time.
In fact, updating the maxfields after a rotation can be accomplished in O(1) time, as is shown in Exercises 14.2-4 and14.3-1.Step 4: Developing New OperationsThe only new operation we need is INTERVAL-SEARCH(T, i), which finds a node in tree Twhose interval overlaps interval i. If there is no interval that overlaps i in the tree, a pointer tothe sentinel nil[T] is returned.INTERVAL-SEARCH(T, i)1 x ← root[T]2 while x ≠ nil[T] and i does not overlap int[x]3do if left[x] ≠ nil[T] and max[left[x]] ≥ low[i]4then x ← left[x]5else x ← right[x]6 return xThe search for an interval that overlaps i starts with x at the root of the tree and proceedsdownward.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
