Skip lists

A skip list (William Pugh, 1990) reaches the same O(log n) search time as a balanced tree with no rotations and no colours. It stacks a few sorted linked lists on top of each other and uses coin flips to decide which keys go in the upper lists.

Linked lists with levels that skip ahead

Searching a sorted linked list is slow: you can only move one node at a time, so finding a key costs O(n). Now add a second list above it that holds every other key, with each upper node linked to the node below it holding the same key. Search the upper list first, and go down only near the end. That roughly halves the work. Add a third list holding every fourth key, and so on.

Each of these lists is a level. Level 0 holds every key. Each key has a tower of nodes, one on each level from 0 up to its own height. In code, a node holds its key and a list next of links, one per level of its tower: node.next[i] is the next node on level i. A head node with a link on every level starts all the lists.

class SkipNode:
    def __init__(self, key, height):
        self.key = key
        self.next = [None] * height  # one link per level

class SkipList:
    MAX = 20  # enough levels for about a million keys
    def __init__(self):
        self.head = SkipNode(None, self.MAX)

Search

Start at the head, on the top level. On each level, move right while the next key is smaller than the key you want. When the next key is too big, or there is none, go down one level and carry on from the same node. On level 0, the next node holds the key if it is in the list. Step through the first variant.

def contains(self, key):
    node = self.head
    for level in range(self.MAX - 1, -1, -1):
        while (node.next[level] is not None
               and node.next[level].key < key):
            node = node.next[level]
    node = node.next[0]
    return node is not None and node.key == key

Insert with coin flips

To insert a key, search for it as above, and on each level remember the last node visited: the node whose link will point to the new node on that level. Then choose the new key’s height by flipping a coin: it gets level 0, and on each heads it also gets the next level up, until the first tails. Finally, on each of its levels, link it in after the remembered node, as in a linked-list insert. Step through the second variant.

import random

def random_height(self):
    h = 1
    while h < self.MAX and random.random() < 0.5:  # heads
        h += 1
    return h

Deleting works the same way: search, remembering the last node on each level, then on each level where the next node holds the key, link around it. No other node changes. Nothing ever needs rebalancing, because the heights were chosen at random and do not depend on the order of the inserts.

Expected cost

A key reaches level 1 with chance 1/2, level 2 with chance 1/4, and level i with chance 1/2ⁱ (i halves multiplied together). So about n/2 keys are on level 1, n/4 on level 2, and the top level that is not empty is near log₂ n. The towers have an expected height of 2, so the whole list uses about 2n links: O(n) space.

For the search, trace its path backwards, from the end on level 0 back to the head. At each node, the path came either from the left (on the same level) or from above. A node is entered from above exactly when its tower continues upwards, which happens with chance 1/2. So on each level the backward path takes, on average, 1 step left before it goes up. With about log₂ n levels, a search looks at about 2 log₂ n nodes on average.

These are expected costs: averages over the coin flips, for any input. Unlike a plain search tree, no input order is bad. Very unlucky flips could still make one search slow, but the chance of a search taking much longer than O(log n) falls very fast; for a list of a million keys it is far too small to matter.

In Python

Python has no skip list in its standard library. They appear in other systems: Redis keeps its sorted sets in skip lists, and Java’s ConcurrentSkipListMap uses one because many threads can change different parts of a skip list at the same time more easily than a tree that rotates.