Algorithms-1 11

Randomized skip-list

A randomized skip-list is a data structure that supports the following operations

• Adding an element to the list
• Searching for an element in the list
• Removing an existing element from the list

All operations are expected to be executed in time or are executed in with a relatively high probability. Space complexity is expected to be where is the number of elements that the list contains.

• The data structure is built of layers or levels,
• Each level is a sorted doubly-linked list that, in addition to the actual elements, contains to check if an element is not present when searching
• contains all elements in the list and
• In addition, each element in the list contains a pointer to its copy in the , except for

Adding an element

• Add an element to , maintaining sorted order (using search)
• Flip a coin, if heads then the element is copied to the next level
• Repeat coin flips and “promotions” until tails

Searching for an element

• Search begins at the highest level on its left end, searching for
• Linear search is done until the largest
  • If then we found the element
  • Otherwise, continue from on the level
• Best case scenario is
• Worst case scenario is

Removing an element

• First search for an element
• Then remove it from all levels

Analysis of the data structure

Runtime of operations

Search

Let us now prove that search is performed in time with relatively high probability

Adding an element

• First, search is performed in time with relatively high probability
• Second, insert () is performed in at most each level, which is, with relatively high probability, at most levels

Removing an element

• First, search is performed in time with relatively high probability
• Second, deletion () is performed in at most each level, which is, with relatively high probability, at most levels

---

Quick-Select

Quick-select is a randomized algorithm for finding -th smallest element in the array of elements

How do we analyze this algorithm?