- Example: list of keys
(values have been omitted for
brevity)
- 12, 17, 20, 25, 31, 38, 39, 44, 50, 55
Stored as an (doubly linked) ordered list:
- Performance comparision table:
Operation Ordered array implementation Ordered linked list implementation Insert (put(k,v)) O(n) O(n) Lookup (get(k)) O(log(n)) (bin search) O(n) Delete (remove(k)) O(n) O(n)
- Note:
- Insert and
delete are
O(n) using the
ordered array implementation
because we need to:
- move array elements to create an empty spot (for insert) or
- move array elements to close an empty spot (for delete)
- Insert,
lookup and
delete are
O(n) using the
ordered list implementation
because we need to:
- traverse the entire list to locate the appropriate list element to perform the operation....
- Insert and
delete are
O(n) using the
ordered array implementation
because we need to:
- We create a 2-dimensional grid
to mimic the
binary search process in
a linked list
Example: 2-dimensional grid structure
Note:
- The skip list data structure is
a dynamic structure:
- It can grow in height
- When a new empty layer
is added to the
skip list,
the layer initially contain these
2 special elements:
- −∞ (represents the smallest possible value)
- +∞ (represents the largest possible value)
- This 2-dimensional grid structure can help us speed up the search for a key
- The skip list data structure is
a dynamic structure:
- Example: search for the entry containing the key
50
-
50 ≥ 17
⇒
go
right
(from where p is currently)
-
50 < +∞
⇒
go
DOWN
(from where p is currently)
-
50 ≥ 25
⇒
go
right
(from where p is currently)
-
50 < 55
⇒
go
DOWN
(from where p is currently)
- And so on:
Note: the entry used to compare against the key is: p.right
Note: p is initially equal to head
-
50 ≥ 17
⇒
go
right
(from where p is currently)
- The ideal skip list that
will mimic the
binary search is
constructed as follows:
- At each layer, remove exactly half of the entries
Example:
(Remember that the top most layer is logical --- it does not exists.)
- Links traversed to locate
the key 50:
Note:
- Notice that the
search pattern
given by the
magenta colored links in the
skip list
is exactly the same as
in a binary search
Therefore:
- There are O(log(n)) magenta colored links in the search operation in the ideal skip list
- The height of the
ideal skip list is
log(n)
There are exactly 2 red colored search links in the skip list in each level
Therefore:
- There are 2 × (log(n) − 1) red colored search links (in any kind of skip list)
- Notice that the
search pattern
given by the
magenta colored links in the
skip list
is exactly the same as
in a binary search
- Running time complexity in the
ideal skip list:
- Searching for a key k in the ideal case is O(log(n)) (same as binary search)
- The ideal skip list can
never be realized because
the data structure is
dynamic
- Example:
Change:
- After inserting 33:
- Many (red) links needs to be
updated
(This will happen when enough entries are inserted - this example is exagerated to give you the eventual consequence....)
- After inserting 33:
- The typical procedue to
insert a new key into a
skip list is to
give the new key a
random height
- Example:
- Before insertion:
- After inserting key 42:
Note:
- As part of the
insert operation,
we will make a
column (see figure above)
for that key
- The height of the column will be random...
- As part of the
insert operation,
we will make a
column (see figure above)
for that key
- Before insertion:
- Obtaining a
random height:
- We will use a "random trial (experiment)" is used to obtain a random height
- Example random trial:
- Toss a coin continuously
until head come up
- The number of tosses for this experiment (trial) to end is a random number
- Toss a coin continuously
until head come up
- Simulating a coin toss
experiment:
public static void main(String[] args) { Random r = new Random(); double x; int n = 0; x = r.nextDouble(); // First toss n++; while ( x < 0.5 ) { x = r.nextDouble(); // Toss again... n++; } System.out.println("# tosses = " + n ); }
- Example Program:
(Demo above code)
- Prog file: click here
- Note:
- You need to wait until the next webpage
to see how this
random algorithm will be used in
the
implementation
of the Skip List
(There I will use this random trial procedure to create a column of random length in the put() method)
- You need to wait until the next webpage
to see how this
random algorithm will be used in
the
implementation
of the Skip List
- Skip list S for a Map M:
- Consists of a series of
lists:
{
S0, S1,, ..., Sh
}
where h = height of the skip list
- A list Sk:
- contains a ordered list
of a subset of the entries
of map M
- plus 2 special elements:
−∞ and
+∞
- −∞ is smaller than any key
- +∞ is larger than any key
(Used to denote the start and the end)
- contains a ordered list
of a subset of the entries
of map M
- The list S0 contains every entry of the map M plus the 2 special elements −∞ and +∞
- The list Sh
contains
only
the 2 special elements
−∞ and
+∞
- Important property:
- Sk+1 ⊆ Sk k = h−1, h−2, ..., 0
- Consists of a series of
lists:
{
S0, S1,, ..., Sh
}
- Example: a good skip list
(h = 5)
- Example: not a
skip list
Reason:
- S2 = { −∞ , 17, 25, 31, 55, +∞ }
- S3 =
{ −∞ , 17, 25, 39 55, +∞ }
- It violates
the property:
- S3 ⊆ S2
- Note:
- The property
- Sk+1 ⊆ Sk k = h−1, h−2, ..., 0
is satisfied when each column of keys is continuous
- Reason:
- The continuity of a "stack" will
ensure that when
a key k is
found in the higher layer (Sk+1),
the key k is
also found in
every layer below ((Sk)
- Therefore: Sk+1 ⊆ Sk
- The continuity of a "stack" will
ensure that when
a key k is
found in the higher layer (Sk+1),
the key k is
also found in
every layer below ((Sk)
- The property