Skip List

README.md

https://cw.fel.cvut.cz/old/_media/courses/a4b36acm/maraton2015skiplist.pdf

skip_list.py

import random


class SkipListNode:
    def __init__(self, key, data, height):
        self.key = key
        self.data = data
        self.height = height
        self.forward = [None for _ in range(height + 1)]


class SkipList:
    def __init__(self, p=0.25):
        self.p = p
        self.level = 1
        self.max_level = 16
        self.header = make_node(self.max_level, -float('inf'), None)
        sentinel = make_node(self.max_level, float('inf'), None)
        for i in range(1, self.max_level + 1):
            self.header.forward[i] = sentinel


def make_node(height, key, data):
    return SkipListNode(key, data, height)


def print_list(lst):
    ans = []
    node = lst.header
    while node:
        ans.append(node.key)
        node = node.forward[1]
    print(ans)


def random_level(lst):
    new_level = 1
    while random.random() < lst.p:
        new_level += 1
    return min(new_level, lst.max_level)


def search(lst, key):
    x = lst.header
    for i in range(lst.level, 0, -1):
        while x.forward[i].key < key:
            x = x.forward[i]

    x = x.forward[1]
    if x.key == key:
        return x
    return None


def insert(lst, key, data):
    x = lst.header
    update = {}
    for i in range(lst.level, 0, -1):
        while x.forward[i].key < key:
            x = x.forward[i]
        update[i] = x

    new_level = random_level(lst)
    if new_level > lst.level:
        new_level = lst.level + 1
        lst.level = new_level
        update[new_level] = lst.header
    x = make_node(new_level, key, data)
    for i in range(1, new_level + 1):
        x.forward[i] = update[i].forward[i]
        update[i].forward[i] = x


def delete(lst, key):
    x = lst.header
    update = {}
    for i in range(lst.level, 0, -1):
        while x.forward[i].key < key:
            x = x.forward[i]
        update[i] = x

    x = x.forward[i]
    if x.key != key:
        return False
    for i in range(1, lst.level + 1):
        if update[i].forward[i] != x:
            break
        update[i].forward[i] = x.forward[i]
    return True