LC 1206 [H] Design Skiplist - ALawliet/algorithms GitHub Wiki

https://www.youtube.com/watch?v=UGaOXaXAM5M&ab_channel=ShusenWang

number of calls is limited to 50000 and log(50000) (15.6 ~ 16) is the most reasonable for number of levels.

Each node has 2 pointers: "next" targets to the next node in the same level, "down" targets the "next" level node. "down" pointer must alwasy target node of the same value in the next level.

Initialize an array of levels, each level contain a first node of value -math.inf.
Be careful that these nodes should be initialized with their "down" pointer targeting to the next level -math.inf node.
Write a function to find the biggest node that is smaller than search target in all levels. If there is an exact match to the target, we still find its previous node. This is because erase operation requires previous node, rather than the exact matched node.
If you add a node in a level, all levels after that also need to be added, and nodes' "down" pointer must target to their next level counterpart. Levels before this level can be ignored.
If you erase a node, erase all such node in all levels.

class Node:
    def __init__(self,val):
        # normal LL 
        self.val = val
        self.next = None

        # skip list
        self.down = None

class Skiplist:
    # build the lists starting from the top and going down
    def __init__(self):
        self.levels = [] # a list of the starting sentinel nodes

        prev = None
        for level in range(16):
            node = Node(-math.inf) # sentinel/dummy node
            self.levels.append(node)
            if prev:
                prev.down = node
            prev = node
			
    def _iter(self, val):
        res = []
        level = self.levels[0] # start at the first level, the top level
        while level:
            while level.next and level.next.val < val: # we can keep going right if the value is bigger
                level = level.next
            # we exhausted the level, now we need to go down
            res.append(level)
            level = level.down
        return res
		
    def search(self, target: int) -> bool:
        last = self._iter(target)[-1] # the last level that we checked
        return last.next and last.next.val == target # we're always checking next because we started at the sentinel 
		
    def add(self, num: int) -> None:
        res = self._iter(num)
        prev = None
        for level in range(len(res) - 1, -1, -1): # add starting from the bottom
            node = Node(num) # we reuse the same num when we grow the level
            node.next, node.down = res[level].next, prev
            res[level].next = node
            prev = node
            rand = random.random() # a random value from 0 to 1
            if rand > 0.5: # flip a coin
                break
				
    def erase(self, num: int) -> bool:
        found = False
        res = self._iter(num)
        for level in range(len(res)):
            if res[level].next and res[level].next.val == num: # same as search
                res[level].next = res[level].next.next # skip over it like usual when deleting from a linked list
                found = True
        return found

class Node:
    __slots__ = 'val', 'levels'
    def __init__(self, val, levels):
        self.val = val
        self.levels = [None] * levels

class Skiplist(object):
    def __init__(self):
        self.head = Node(-1, 16) 
    
    def _iter(self, num):
        cur = self.head
        for level in range(15, -1, -1):
            while True:
                future = cur.levels[level]
                if future and future.val < num:
                    cur = future
                else:
                    break
            yield cur, level

    def search(self, target):
        for prev, level in self._iter(target):
            pass
        cur = prev.levels[0]
        return cur and cur.val == target

    def add(self, num):
        nodelvls = min(16, 1 + int(math.log2(1.0 / random.random())))
        node = Node(num, nodelvls)
        
        for cur, level in self._iter(num):
            if level < nodelvls:
                future = cur.levels[level]
                cur.levels[level] = node
                node.levels[level] = future

    def erase(self, num):
        ans = False
        for cur, level in self._iter(num):
            future = cur.levels[level]
            if future and future.val == num:
                ans = True
                cur.levels[level] = future.levels[level]
        return ans