Transcript gal

Randomized Skip List


Skip List
Or, In Hebrew: ‫רשימות דילוג‬
3/22/2017
Randomized Algorithms - Treaps
1
Outline
3/22/2017

Motivation for the skipping

Skip List definitions and description

Analyzing performance

The role of randomness
Randomized Algorithms - Treaps
2
Outline
3/22/2017

Motivation for the skipping

Skip List definitions and description

Analyzing performance

The role of randomness
Randomized Algorithms - Treaps
3
Starting from scratch

Initial goal just search, no updates (insert, delete).

Simplest Data Structure?

linked list!

Search? O(n)!
Can we do it faster?
yes we can!
3/22/2017
Randomized Algorithms – Skip List
4
Developing the skip list

Let’s add an express lane.

Can quickly jump from express stop to next express stop, or
from any stop to next normal stop.

To search, first search in the express layer until about to go to
far, then go down and search in the local layer.
3/22/2017
Randomized Algorithms – Skip List
5
Search cost

What is the search cost?
3/22/2017
Randomized Algorithms – Skip List
6
Search cost – Cont.

This is minimized when:
3/22/2017
Randomized Algorithms – Skip List
7
Discovering skip lists

If we keep adding linked list layers we get:
3/22/2017
Randomized Algorithms – Skip List
8
Outline
3/22/2017

Motivation for the skipping

Skip List definitions and description

Analyzing performance

The role of randomness
Randomized Algorithms - Treaps
9
Initial definitions

Let S be a totally ordered set of n elements.

A leveling with r levels of S, is a sequence of nested subsets

(called levels) :
L
where
and
r
 Lr 1  ...  L2  L1
Given a leveling for S, the level of any element x in s is defined as:
3/22/2017
Randomized Algorithms - Treaps
10
Skip List Description

Given any leveling of the set S, we define the skip list corresponding
to this structure like this:
 The level
is stored in a sorted link list.
 Each node x in this linked list has a pile of
nodes above it.
 There are horizontal and vertical pointers between nodes.
 For convenience, we assume that two special elements
and
belong to each of the levels.
3/22/2017
Randomized Algorithms - Treaps
11
Skip List Example

For example, for this leveling:
L  {2,5,11,15,20,23,31,32,35,45,47}
L  {2,15,23,35,45}
L  {2,15,35}
1
2
3

This is the skip list corresponding to it:
3/22/2017
Randomized Algorithms - Treaps
12
Skip list as binary tree
 An interval level I, is the set of elements
of S,
spanned by a specific horizontal pointer at level i.
 For example,
for the previous skip list, this is the
interval at level 2:
3/22/2017
Randomized Algorithms - Treaps
13
Skip list as binary tree
 The interval
partition structure is more conveniently
viewed as a tree, where each node corresponds to
an interval.
 If an interval J at level i+1 contains as a subsets an
interval I at level i, then node J is the parent of node
I in the tree.
 For interval I at level i+1, C(I) denotes the number of
children of Interval I at level i.
3/22/2017
Randomized Algorithms - Treaps
14
Searching skip lists

Consider an element y, that is not necessarily
an member of S, and assume we want to
search for it in skip list s.

Let
be the interval at level j that contains
y.
3/22/2017
Randomized Algorithms - Treaps
15
Searching skip lists – Cont.

We can now view the nested sequence of
intervals
as a root-leaf path in the tree representation
of the skip list.
3/22/2017
Randomized Algorithms - Treaps
16
Random skip list
To complete the description of the skip list, we have to
specify the choice of the leveling that underlies it.
 The basic idea is to chose a random leveling, thereby
defining a random skip list.
 A random leveling is defined as follows:
given the choice of level
the level
is defined by independently choosing to
retain each element
with probability ½.

3/22/2017
Randomized Algorithms - Treaps
17
Outline
3/22/2017

Motivation for the skipping

Skip List definitions and description

Analyzing performance

The role of randomness
Randomized Algorithms - Treaps
18
Search cost

What is the expected time to find an element in a random skip
list?

We will show it is O(logn) with high probability.

What is the expected space of a random skip list?

O(n). Why?
3/22/2017
Randomized Algorithms - Treaps
19
Random procedure

An alternative view of the random construction is as follows:
 Let l(x) for every
be independent random variable, with
geometric distribution.
 Let r be one more than the maximum of these random variables.
 Place x in each of the levels,

.…..
.
As with random priorities in treaps, a random level is
chosen once for every element in it’s insertion.
3/22/2017
Randomized Algorithms - Treaps
20
The expected number of levels

Lemma: the number of levels r in a random leveling of a set S
of size n is O(logn) with high probability.

Proof: look at the board!

Does it mean that the E[r]=O(logn)? Why?
Is it enough?
No!
3/22/2017
Randomized Algorithms - Treaps
21
The search path length

The last result implies that the tree representing the skip list
has height o(logn) with high probability.

Unfortunately, since the tree need not be binary, it does not
immediately follows that the search time is similarly bounded.

The implementation of Find(x,s) corresponds to walking down
the path
3/22/2017
Randomized Algorithms - Treaps
22
The search path length – Cont.

Walking down the path
is as follows:
 At level j, starting at the node
, use a vertical pointer to
descend to the leftmost child of the current interval;


then using the horizontal pointers, move rightward till the node
The cost of FIND(x,s) proportional to the number of levels as
well as the number of intervals visited at each level.
3/22/2017
Randomized Algorithms - Treaps
23
The search path length is O(logn)

Lemma 2: Let y be any element and consider the
search path
followed by FIND(y, S) in a random skip list for the set
S of size n, then:
 A.
r
 (1  C( I
j 1
j
( y)))
is the length of the search path.
r
 B. E[ (1  C ( I j ( y)))]  O(log n)
j 1
3/22/2017
Randomized Algorithms - Treaps
24
Proof of Lemma 2

Proof of A: the number of nodes visited at level j does
not exceed the number of children of the interval
therefore in each level, you walk through
r
elements and in total  (1  C(I
j 1
j
( y)))
1  C( I j ( y))
.
Proof of B: look at the board!
 This result shows that the expected time of search is
o(logn).

3/22/2017
Randomized Algorithms - Treaps
25
Insert and delete in skip list
Insert and delete operation can be done both in o(logn)
expected time also.
 To insert an element y:

 a random level l(y) (may exceed r) should be chosen for y
as described earlier.
 Then a search operation should find the search path of y
 Then update the correct intervals, and add pointers.

3/22/2017
Delete operation is just the converse of insert.
Randomized Algorithms - Treaps
26
Outline
3/22/2017

Motivation for the skipping

Skip List definitions and description

Analyzing performance

The role of randomness
Randomized Algorithms - Treaps
27
The role of randomness

What is the role of the randomness in skip lists?

The random leveling of S enables us to avoid
complicated “balancing” operations.

This simplifies our algorithm and decreases the
overhead.
3/22/2017
Randomized Algorithms - Treaps
28
The role of randomness - cont.

It also saves us the need to “remember” the
state of the node or the system.

Unlike binary search trees, skip lists behavior is
indifferent to the input distribution.
3/22/2017
Randomized Algorithms - Treaps
29