Documents

03-treaps.pdf

Description
Description:
Categories
Published
of 14
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.
Share
Transcript
   Algorithms Lecture : Treaps and Skip Lists [Sp’] I thought the following four [rules] would be enough, provided that I made a firm and constant  resolution not to fail even once in the observance of them. The first was never to accept anything as true if I had not evident knowledge of its being so.... The second, to divideeach problem I examined into as many parts as was feasible, and as was requisite for its better solution. The third, to direct my thoughts in an orderly way...establishing an order inthought even when the objects had no natural priority one to another. And the last, to make throughout such complete enumerations and such general surveys that I might be sure of  leaving nothing out. — René Descartes,  Discours de la Méthode  (1637) There are those who think that life has nothing left to chance A host of holy horrors to direct our aimless dance — Rush, “Freewill”,  Permanent Waves  (1980), lyrics by Neal Peart What is luck?Luck is probability taken personally.It is the excitement of bad math. — Penn Jillette (2001), quoting Chip Denman (1998)  Randomized Binary Search Trees In this lecture, we consider two randomized alternatives to balanced binary search tree structuressuch as AVL trees, red-black trees, B-trees, or splay trees, which are arguably simpler than any of  these deterministic structures. . Treaps .. Definitions  A   treap  is a binary tree in which every node has both a  search key   and a  priority  , where the inorder sequence of search keys is sorted and each node’s priority is smaller than the priorities of  its children.   In other words, a treap is simultaneously a binary search tree for the search keys and a (min-)heap for the priorities. In our examples, we will use letters for the search keys and numbers for the priorities. M 1 H 2 G 7 A 9 T 3 R 5 O 6 I 4 L 8 A treap. Letters are search keys; numbers are priorities. I’ll assume from now on that all the keys and priorities are distinct. Under this assumption,  we can easily prove by induction that the structure of a treap is completely determined by the  Sometimes I hate English. Normally, ‘higher priority’ means ‘more important’, but ‘first priority’ is also more important than ‘second priority’. Maybe ‘posteriority’ would be better; one student suggested ‘unimportance’. ©  Copyright 2018 Jeff Erickson. This work is licensed under a Creative Commons License (http://creativecommons.org/licenses/by-nc-sa/4.0/). Free distribution is strongly encouraged; commercial distribution is expressly forbidden.See http://jeffe.cs.illinois.edu/teaching/algorithms/ for the most recent revision.    Algorithms Lecture : Treaps and Skip Lists [Sp’] search keys and priorities of its nodes. Since it’s a heap, the node  v  with highest priority must bethe root. Since it’s also a binary search tree, any node  u  with  key  ( u ) < key  (  v )  must be in the left subtree, and any node  w  with  key  ( w ) > key  (  v )  must be in the right subtree. Finally, since the subtrees are treaps, by induction, their structures are completely determined. The base case is the trivial empty treap.  Another way to describe the structure is that a treap is exactly the binary search tree thatresults by inserting the nodes one at a time into an initially empty tree, in order of increasingpriority, using the standard textbook insertion algorithm. This characterization is also easy to prove by induction.  A third description interprets the keys and priorities as the coordinates of a set of points in the plane. The root corresponds to a  T  whose joint lies on the topmost point. The  T  splits theplane into three parts. The top part is (by definition) empty; the left and right parts are splitrecursively. This interpretation has some interesting applications in computational geometry,  which (unfortunately) we won’t have time to talk about. 987654321 A G H I L M O R T A geometric interpretation of the same treap. Treaps were first discovered by Jean Vuillemin in , but he called them  Cartesian trees .  The word ‘treap’ was first used by Edward McCreight around  to describe a slightly differentdata structure, but he later switched to the more prosaic name  priority search trees .   Treaps wererediscovered and used to build randomized search trees by Cecilia Aragon and Raimund Seidel in.   A different kind of randomized binary search tree, which uses random rebalancing insteadof random priorities, was later discovered and analyzed by Conrado Martínez and Salvador Roura in .  .. Treap Operations The search algorithm is the usual one for binary search trees. The time for a successful search isproportional to the depth of the node. The time for an unsuccessful search is proportional to the depth of either its successor or its predecessor. To insert a new node  z , we start by using the standard binary search tree insertion algorithmto insert it at the bottom of the tree. At the point, the search keys still form a search tree, but the  J. Vuillemin, A unifying look at data structures.  Commun. ACM   :–, .  E. M. McCreight. Priority search trees.  SIAM J. Comput.  ():–, .  R. Seidel and C. R. Aragon. Randomized search trees.  Algorithmica  :–, .  C. Martínez and S. Roura. Randomized binary search trees.  J. ACM   ():-, . The results in this paperare virtually identical (including the constant factors!) to the corresponding results for treaps, although the analysis techniques are quite different.    Algorithms Lecture : Treaps and Skip Lists [Sp’] ã  Insert/Delete:  Inserting a new node with key   k  takes either  O ( depth (  v + ))  time or O ( depth (  v − ))  time, where  v + and  v −  are the predecessor and successor of the new node. Deletion is just insertion in reverse. ã  Split/Join:  Splittingatreapatpivotvalue  k  takeseither O ( depth (  v + )) timeor O ( depth (  v − )) time, since it costs the same as inserting a new dummy root with search key   k  and priority  −∞ . Merging is just splitting in reverse. In the worst case, the depth of an  n -node treap is  Θ ( n ) , so each of these operations has a  worst-case running time of  Θ ( n ) . .. Random Priorities  A   randomized treap  is a treap in which the priorities are  independently and uniformly distributed continuous random variables . Whenever we insert a new search key into the treap, we generate arandom real number between (say)  0  and  1  and use that number as the priority of the new node. The only reason we’re using real numbers is so that the probability of two nodes having the same priority is zero, since equal priorities make the analysis slightly messier. (In practice, we could just choose random integers from a large range like  0  to  2 31 − 1  and break ties arbitrarily; occasional ties have almost no practical effect on the performance of the data structure.) Also, since the priorities are independent, each node is equally likely to have the smallest priority. The cost of all the operations we discussed—search, insert, delete, split, join—is proportional to the depth of some node in the tree. Here we’ll see that the  expected  depth of   any   nodeis  O ( log n ) , which implies that the expected running time for any of those operations is also O ( log n ) . Let  x  k  denote the node with the  k th smallest search key. To simplify notation, let us write i  ↑ k  (read “ i  above  k ”) to mean that  x  i  is a proper ancestor of   x  k . Since the depth of   v  is just the number of proper ancestors of   v , we have the following identity: depth (  x  k ) = n  i = 1 [ i  ↑ k ] . (Again, we’re using Iverson bracket notation.) Now we can express the  expected  depth of a node in terms of these indicator variables as follows. E [ depth (  x  k )] = n  i = 1  E   [ i  ↑ k ]  = n  i = 1 Pr [ i  ↑ k ] (Just as in our analysis of matching nuts and bolts, we’re using linearity of expectation and the fact that  E [  X  ] =  Pr [  X   =  1 ]  for any zero-one variable  X  ; in this case,  X   = [ i  ↑ k ] .) So to computethe expected depth of a node, we just have to compute the probability that some node is a proper ancestor of some other node. Fortunately, we can do this easily once we prove a simple structural lemma. Let  X  ( i , k )  denoteeither the subset of treap nodes  {  x  i ,  x  i + 1 ,...,  x  k }  or the subset  {  x  k ,  x  k + 1 ,...,  x  i } , depending on  whether  i  <  k  or  i  >  k . The order of the arguments is unimportant; the subsets  X  ( i , k )  and  X  ( k , i )  are identical. The subset  X  ( 1, n ) =  X  ( n ,1 )  contains all  n  nodes in the treap. Lemma .  For all   i   =  k , we have   i  ↑ k  if and only if   x  i  has the smallest priority among all nodes  in  X  ( i , k ) . 
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
SAVE OUR EARTH

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!

x