企业官网建设流程全解析

"""
跳表 (Skip List) — 概率平衡的多层索引链表
搜索/插入/删除 O(log n)，Redis ZSet 底层使用
"""

import random


class 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_lvl=16, p=0.5):
self.max = max_lvl; self.p = p
self.head = Node(float('-inf'), None, max_lvl)
self._lvl = 0

def _rl(self):
l = 0
while random.random() < self.p and l < self.max: l += 1
return l

def search(self, k):
c = self.head
for 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 None

def insert(self, k, v):
up = [None] * (self.max + 1); c = self.head
for i in range(self._lvl, -1, -1):
while c.fwd[i] and c.fwd[i].key < k: c = c.fwd[i]
up[i] = c
c = c.fwd[0]
if c and c.key == k: c.val = v; return
l = self._rl()
if l > self._lvl:
for i in range(self._lvl + 1, l + 1): up[i] = self.head
self._lvl = l
n = Node(k, v, l)
for i in range(l + 1):
n.fwd[i] = up[i].fwd[i]; up[i].fwd[i] = n

def delete(self, k):
up = [None] * (self.max + 1); c = self.head
for i in range(self._lvl, -1, -1):
while c.fwd[i] and c.fwd[i].key < k: c = c.fwd[i]
up[i] = c
c = c.fwd[0]
if not c or c.key != k: return False
for i in range(self._lvl + 1):
if up[i].fwd[i] is not c: break
up[i].fwd[i] = c.fwd[i]
while self._lvl > 0 and self.head.fwd[self._lvl] is None:
self._lvl -= 1
return True

def __contains__(self, k): return self.search(k) is not None

def __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(f"L{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()