Skip List原理和实现

Implement skip list in python

import random

class SkipNode:
    def __init__(self, key=None, value=None, level=0):
        self.key = key
        self.value = value
        self.forward = [None] * level
        
class SkipList:
    def __init__(self, max_level=16):
        self.head = SkipNode()
        self.max_level = max_level
        self.level = 0
    
    def random_level(self):
        level = 1
        while random.random() < 0.5 and level < self.max_level:
            level += 1
        return level
    
    def search(self, key):
        node = self.head
        for i in range(self.level-1, -1, -1):
            while node.forward[i] and node.forward[i].key < key:
                node = node.forward[i]
        if node.forward[0] and node.forward[0].key == key:
            return node.forward[0].value
        return None
    
    def insert(self, key, value):
        update = [None] * self.max_level
        node = self.head
        for i in range(self.level-1, -1, -1):
            while node.forward[i] and node.forward[i].key < key:
                node = node.forward[i]
            update[i] = node
        node = node.forward[0]
        if node and node.key == key:
            node.value = value
        else:
            level = self.random_level()
            if level > self.level:
                for i in range(self.level, level):
                    update[i] = self.head
                self.level = level
            node = SkipNode(key, value, level)
            for i in range(level):
                node.forward[i] = update[i].forward[i]
                update[i].forward[i] = node
    
    def delete(self, key):
        update = [None] * self.max_level
        node = self.head
        for i in range(self.level-1, -1, -1):
            while node.forward[i] and node.forward[i].key < key:
                node = node.forward[i]
            update[i] = node
        node = node.forward[0]
        if node and node.key == key:
            for i in range(self.level):
                if update[i].forward[i] != node:
                    break
                update[i].forward[i] = node.forward[i]
            while self.level > 1 and not self.head.forward[self.level-1]:
                self.level -= 1
        else:
            raise ValueError('Key not found')