跳表 (Skip List) — 概率平衡的多层索引链表搜索/插入/删除 O(log n)Redis ZSet 底层使用import randomclass Node:__slots__ (key, val, fwd)def __init__(self, k, v, lvl):self.key k; self.val v; self.fwd [None] * (lvl 1)class SkipList:def __init__(self, max_lvl16, p0.5):self.max max_lvl; self.p pself.head Node(float(-inf), None, max_lvl)self._lvl 0def _rl(self):l 0while random.random() self.p and l self.max: l 1return ldef search(self, k):c self.headfor i in range(self._lvl, -1, -1):while c.fwd[i] and c.fwd[i].key k: c c.fwd[i]c c.fwd[0]return c.val if c and c.key k else Nonedef insert(self, k, v):up [None] * (self.max 1); c self.headfor i in range(self._lvl, -1, -1):while c.fwd[i] and c.fwd[i].key k: c c.fwd[i]up[i] cc c.fwd[0]if c and c.key k: c.val v; returnl self._rl()if l self._lvl:for i in range(self._lvl 1, l 1): up[i] self.headself._lvl ln Node(k, v, l)for i in range(l 1):n.fwd[i] up[i].fwd[i]; up[i].fwd[i] ndef delete(self, k):up [None] * (self.max 1); c self.headfor i in range(self._lvl, -1, -1):while c.fwd[i] and c.fwd[i].key k: c c.fwd[i]up[i] cc c.fwd[0]if not c or c.key ! k: return Falsefor i in range(self._lvl 1):if up[i].fwd[i] is not c: breakup[i].fwd[i] c.fwd[i]while self._lvl 0 and self.head.fwd[self._lvl] is None:self._lvl - 1return Truedef __contains__(self, k): return self.search(k) is not Nonedef __repr__(self):lines []for i in range(self._lvl, -1, -1):c self.head.fwd[i]; vs []while c: vs.append(str(c.key)); c c.fwd[i]lines.append(fL{i}: {→.join(vs) if vs else 空})return \n.join(lines)def demo():s SkipList(4, 0.5)for k, v in [(3, 三), (1, 一), (7, 七), (5, 五), (9, 九)]:s.insert(k, v)print(s)print(f查5: {s.search(5)}, 查4: {s.search(4)})s.delete(5)print(f删5后查: {s.search(5)})s.insert(7, 柒); print(f更7: {s.search(7)})if __name__ __main__:demo()
Python跳表实现
跳表 (Skip List) — 概率平衡的多层索引链表搜索/插入/删除 O(log n)Redis ZSet 底层使用import randomclass Node:__slots__ (key, val, fwd)def __init__(self, k, v, lvl):self.key k; self.val v; self.fwd [None] * (lvl 1)class SkipList:def __init__(self, max_lvl16, p0.5):self.max max_lvl; self.p pself.head Node(float(-inf), None, max_lvl)self._lvl 0def _rl(self):l 0while random.random() self.p and l self.max: l 1return ldef search(self, k):c self.headfor i in range(self._lvl, -1, -1):while c.fwd[i] and c.fwd[i].key k: c c.fwd[i]c c.fwd[0]return c.val if c and c.key k else Nonedef insert(self, k, v):up [None] * (self.max 1); c self.headfor i in range(self._lvl, -1, -1):while c.fwd[i] and c.fwd[i].key k: c c.fwd[i]up[i] cc c.fwd[0]if c and c.key k: c.val v; returnl self._rl()if l self._lvl:for i in range(self._lvl 1, l 1): up[i] self.headself._lvl ln Node(k, v, l)for i in range(l 1):n.fwd[i] up[i].fwd[i]; up[i].fwd[i] ndef delete(self, k):up [None] * (self.max 1); c self.headfor i in range(self._lvl, -1, -1):while c.fwd[i] and c.fwd[i].key k: c c.fwd[i]up[i] cc c.fwd[0]if not c or c.key ! k: return Falsefor i in range(self._lvl 1):if up[i].fwd[i] is not c: breakup[i].fwd[i] c.fwd[i]while self._lvl 0 and self.head.fwd[self._lvl] is None:self._lvl - 1return Truedef __contains__(self, k): return self.search(k) is not Nonedef __repr__(self):lines []for i in range(self._lvl, -1, -1):c self.head.fwd[i]; vs []while c: vs.append(str(c.key)); c c.fwd[i]lines.append(fL{i}: {→.join(vs) if vs else 空})return \n.join(lines)def demo():s SkipList(4, 0.5)for k, v in [(3, 三), (1, 一), (7, 七), (5, 五), (9, 九)]:s.insert(k, v)print(s)print(f查5: {s.search(5)}, 查4: {s.search(4)})s.delete(5)print(f删5后查: {s.search(5)})s.insert(7, 柒); print(f更7: {s.search(7)})if __name__ __main__:demo()
