1206. Design Skiplist - cocoder39/coco39_LC GitHub Wiki

1206. Design Skiplist

skip list:

• the bottom layer is an ordered linked list
• The probability of an element being at level i is p^i (p = 0.5 usually)
• the number of level is then log n (suppose n elements at the bottom layer, each layer gets cut by half)
• space complexity is O(n + n/2 + n/4 + ...) = O(n) (等比数列)
• total number of nodes across levels is O(n). Due to the probabilistic promotion of each node, nodes are uniformly distributed across each level. As a result, the number of nodes to check at each level is constant. the total time complexity for add, search, and deletion is O(log N) as they could go over all Log N levels

class Node:
    def __init__(self, val=-1, right=None, down=None):
        self.val = val
        self.right = right
        self.down = down

class Skiplist:
    def __init__(self):
        self.head = Node()

    def search(self, target: int) -> bool:
        cur = self.head
        while cur:
            while cur.right and cur.right.val < target:
                cur = cur.right
            if cur.right and cur.right.val == target:
                return True
            cur = cur.down
        return False

    def add(self, num: int) -> None:
        nodes = []
        cur = self.head
        while cur:
            while cur.right and cur.right.val < num:
                cur = cur.right
            nodes.append(cur)
            cur = cur.down
        
        insert = True
        down = None
        while insert and nodes:
            cur = nodes.pop()
            cur.right = Node(num, cur.right, down)
            down = cur.right
            insert = (random.random() < 0.5)
        
        if insert:
            self.head = Node(-1, None, self.head)

    def erase(self, num: int) -> bool:
        cur = self.head
        found = False
        while cur:
            while cur.right and cur.right.val < num:
                cur = cur.right
            if cur.right and cur.right.val == num:
                found = True
                cur.right = cur.right.right
            cur = cur.down
        return found