-
Notifications
You must be signed in to change notification settings - Fork 0
LC 1206 [H] Design Skiplist
Code with Senpai edited this page May 11, 2022
·
5 revisions
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
footer