Description

Description:

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 ﬁrm and constant
resolution not to fail even once in the observance of them. The ﬁrst 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
.. Deﬁnitions
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 ‘ﬁrst 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 deﬁnition) 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 ﬁrst discovered by Jean Vuillemin in , but he called them
Cartesian trees
.
The word ‘treap’ was ﬁrst used by Edward McCreight around to describe a slightly diﬀerentdata 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 diﬀerent 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 diﬀerent.
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 eﬀect 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
)
.

Search

Similar documents

Tags

Related Search

Massive Sequencing and Microarray PdfMaterial Caracterization X ray (SAXS WAXS PDFPeransertamasyarakat.pdfTypes of Construction Contracts Pdfpdf Filsafat dari persfektif kristianiDownload PDFDesain UML Sistem Informasi Absensi.pdf16-Aksoy-Halifelik.pdf2013-jadi-buku-filsafat-ilmu.pdfEngineering Surveying, 5th Ed 0750649879.pdf

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