Skiplist跳表的通俗理解

import random

max_level = 10


class SkipList(object):
    def __init__(self):
        self.header = Node()

    def insert(self, data):
        p = self.header
        level = random.randint(1, max_level)
        path = [None] * level
        for i in range(level):
            path[i] = self.header.forward[i]

        for i in range(level - 1, -1, -1):
            while p.forward[i] is not None and p.forward[i].val < data:
                p = p.forward[i]
            path[i] = p

        if p.forward[0] is not None and p.forward[0].val == data:
            return

        newNode = Node()
        newNode.val = data
        for i in range(level):
            newNode.forward[i] = path[i].forward[i]
            path[i].forward[i] = newNode

    def delete(self, data):
        p = self.header
        path = [None] * max_level
        for i in range(max_level-1, -1, -1):
            while p.forward[i] is not None and p.forward[i].val < data:
                p = p.forward[i]
            path[i] = p

        if p.forward[0] is not None and p.forward[0].val == data:
            for i in range(max_level -1, -1, -1):
                if path[i].forward[i] is not None and path[i].forward[i].val == data :
                    path[i].forward[i] = path[i].forward[i].forward[i]
                else:
                    path[i].forward[i] = None


    def search(self, data):
        p = self.header
        for i in range(max_level, -1, -1):
            while len(p.forward) > i and p.forward[i] is not None and p.forward[i].val < data:
                p = p.forward[i]

        if p.forward[0] is not None and p.forward[0].val == data:
            return True
        return False

    def print(self):
        for i in range(max_level):
            p = self.header
            s = str(i) + "层 : "
            while p.forward[i] is not None:
                s = s + str(p.forward[i].val) + ","
                p = p.forward[i]
            print(s)


class Node(object):
    def __init__(self):
        self.val = 0
        self.forward = [None] * max_level


if __name__ == '__main__':
    skip_list = SkipList()
    skip_list.insert(4)
    skip_list.insert(2)
    skip_list.insert(6)
    skip_list.print()
    skip_list.delete(4)
    print("after delete 4")
    skip_list.print()

    ret = skip_list.search(2)
    print(2, "find", ret)
    ret = skip_list.search(4)
    print(4, "find", ret)
    skip_list.insert(3)
    skip_list.print()

    ret = skip_list.search(3)
    print(3, "find", ret)