Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 55
Текст из файла (страница 55)
Each node x is labeled with key[x] : Priority[x]. For example, the roothas key G and priority 4.(This combination of properties is why the tree is called a "treap;" it has features of both abinary search tree and a heap.)It helps to think of treaps in the following way. Suppose that we insert nodes x1, x2, ..., xn, withassociated keys, into a treap. Then the resulting treap is the tree that would have been formedif the nodes had been inserted into a normal binary search tree in the order given by their(randomly chosen) priorities, i.e., priority[xi] < priority[xj] means that xi was inserted beforex j.a. Show that given a set of nodes x1, x2, ..., xn, with associated keys and priorities (alldistinct), there is a unique treap associated with these nodes.b.
Show that the expected height of a treap is Θ(lg n), and hence the time to search for avalue in the treap is Θ(lg n).Let us see how to insert a new node into an existing treap. The first thing we do is assign tothe new node a random priority. Then we call the insertion algorithm, which we call TREAPINSERT, whose operation is illustrated in Figure 13.10.Figure 13.10: The operation of TREAP-INSERT. (a) The original treap, prior to insertion. (b)The treap after inserting a node with key C and priority 25. (c)–(d) Intermediate stages wheninserting a node with key D and priority 9. (e) The treap after the insertion of parts (c) and (d)is done. (f) The treap after inserting a node with key F and priority 2.c.
Explain how TREAP-INSERT works. Explain the idea in English and givepseudocode. (Hint: Execute the usual binary-search-tree insertion procedure and thenperform rotations to restore the min-heap order property.)d. Show that the expected running time of TREAP-INSERT is Θ(lg n).TREAP-INSERT performs a search and then a sequence of rotations. Although these twooperations have the same expected running time, they have different costs in practice. Asearch reads information from the treap without modifying it. In contrast, a rotation changesparent and child pointers within the treap.
On most computers, read operations are muchfaster than write operations. Thus we would like TREAP-INSERT to perform few rotations.We will show that the expected number of rotations performed is bounded by a constant.In order to do so, we will need some definitions, which are illustrated in Figure 13.11. The leftspine of a binary search tree T is the path from the root to the node with the smallest key. Inother words, the left spine is the path from the root that consists of only left edges.Symmetrically, the right spine of T is the path from the root consisting of only right edges.The length of a spine is the number of nodes it contains.Figure 13.11: Spines of a binary search tree.
The left spine is shaded in (a), and the right spineis shaded in (b).e. Consider the treap T immediately after x is inserted using TREAP-INSERT. Let C bethe length of the right spine of the left subtree of x. Let D be the length of the left spineof the right subtree of x. Prove that the total number of rotations that were performedduring the insertion of x is equal to C + D.We will now calculate the expected values of C and D.
Without loss of generality, we assumethat the keys are 1, 2, ..., n, since we are comparing them only to one another.For nodes x and y, where y ≠ x, let k = key[x] and i = key[y]. We define indicator randomvariablesXi,k = I {y is in the right spine of the left subtree of x (in T)}.f. Show that Xi,k = 1 if and only if priority[y] > priority[x], key[y] < key[x], and, for everyz such that key[y] < key[z] < key[x], we have priority[y] < priority[z].g. Show thath.
Show thati. Use a symmetry argument to show thatj. Conclude that the expected number of rotations performed when inserting a node intoa treap is less than 2.[2]As in RB-INSERT-FIXUP, the cases in RB-DELETE-FIXUP are not mutually exclusive.Chapter notesThe idea of balancing a search tree is due to Adel'son-Vel'ski i and Landis [2], whointroduced a class of balanced search trees called "AVL trees" in 1962, described in Problem13-3.
Another class of search trees, called "2-3 trees," was introduced by J. E. Hopcroft(unpublished) in 1970. Balance is maintained in a 2-3 tree by manipulating the degrees ofnodes in the tree. A generalization of 2-3 trees introduced by Bayer and McCreight [32],called B-trees, is the topic of Chapter 18.Red-black trees were invented by Bayer [31] under the name "symmetric binary B-trees."Guibas and Sedgewick [135] studied their properties at length and introduced the red/blackcolor convention. Andersson [15] gives a simpler-to-code variant of red-black trees.
Weiss[311] calls this variant AA-trees. An AA-tree is similar to a red-black tree except that leftchildren may never be red.Treaps were proposed by Seidel and Aragon [271]. They are the default implementation of adictionary in LEDA, which is a well-implemented collection of data structures andalgorithms.There are many other variations on balanced binary trees, including weight-balanced trees[230], k-neighbor trees [213], and scapegoat trees [108].
Perhaps the most intriguing are the"splay trees" introduced by Sleator and Tarjan [281], which are "self-adjusting." (A gooddescription of splay trees is given by Tarjan [292].) Splay trees maintain balance without anyexplicit balance condition such as color. Instead, "splay operations" (which involve rotations)are performed within the tree every time an access is made. The amortized cost (see Chapter17) of each operation on an n-node tree is O(lg n).Skip lists [251] are an alternative to balanced binary trees. A skip list is a linked list that isaugmented with a number of additional pointers. Each dictionary operation runs in expectedtime O(lg n) on a skip list of n items.Chapter 14: Augmenting Data StructuresThere are some engineering situations that require no more than a "textbook" data structure—such as a doubly linked list, a hash table, or a binary search tree—but many others require adash of creativity.
Only in rare situations will you need to create an entirely new type of datastructure, though. More often, it will suffice to augment a textbook data structure by storingadditional information in it. You can then program new operations for the data structure tosupport the desired application. Augmenting a data structure is not always straightforward,however, since the added information must be updated and maintained by the ordinaryoperations on the data structure.This chapter discusses two data structures that are constructed by augmenting red-black trees.Section 14.1 describes a data structure that supports general order-statistic operations on adynamic set.
We can then quickly find the ith smallest number in a set or the rank of a givenelement in the total ordering of the set. Section 14.2 abstracts the process of augmenting adata structure and provides a theorem that can simplify the augmentation of red-black trees.Section 14.3 uses this theorem to help design a data structure for maintaining a dynamic set ofintervals, such as time intervals. Given a query interval, we can then quickly find an intervalin the set that overlaps it.14.1 Dynamic order statisticsChapter 9 introduced the notion of an order statistic. Specifically, the ith order statistic of a setof n elements, where i {1, 2,..., n}, is simply the element in the set with the ith smallest key.We saw that any order statistic could be retrieved in O(n) time from an unordered set. In thissection, we shall see how red-black trees can be modified so that any order statistic can bedetermined in O(lg n) time.
We shall also see how the rank of an element—its position in thelinear order of the set—can likewise be determined in O(lg n) time.A data structure that can support fast order-statistic operations is shown in Figure 14.1. Anorder-statistic tree T is simply a red-black tree with additional information stored in eachnode. Besides the usual red-black tree fields key[x], color[x], p[x], left[x], and right[x] in anode x, we have another field size[x]. This field contains the number of (internal) nodes in thesubtree rooted at x (including x itself), that is, the size of the subtree.
If we define thesentinel's size to be 0, that is, we set size[nil[T]] to be 0, then we have the identitysize[x] = size[left[x]] + size[right[x]] + 1.Figure 14.1: An order-statistic tree, which is an augmented red-black tree. Shaded nodes arered, and darkened nodes are black. In addition to its usual fields, each node x has a fieldsize[x], which is the number of nodes in the subtree rooted at x.We do not require keys to be distinct in an order-statistic tree. (For example, the tree in Figure14.1 has two keys with value 14 and two keys with value 21.) In the presence of equal keys,the above notion of rank is not well defined. We remove this ambiguity for an order-statistictree by defining the rank of an element as the position at which it would be printed in aninorder walk of the tree. In Figure 14.1, for example, the key 14 stored in a black node hasrank 5, and the key 14 stored in a red node has rank 6.Retrieving an element with a given rankBefore we show how to maintain this size information during insertion and deletion, let usexamine the implementation of two order-statistic queries that use this additional information.We begin with an operation that retrieves an element with a given rank.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
