想要“有序 + 增删查O(logn)”，第一反应是红黑树或AVL。但它们的白板实现是公认的噩梦：旋转、变色、叔叔节点、RR/LL/LR/RL四种情形……30分钟根本写不完。

跳表（Skip List）给出了另一个答案：给有序链表加多层“稀疏索引”，谁上几层由抛硬币决定。代码不到100行，平均O(logn)，还天然支持O(logn + k)的范围查询。

今天我们就手写它，并回答那个经典面试题：“为什么Redis的有序集合用跳表，不用红黑树？”

📦 题目速览 LeetCode 1206（30秒读懂）

设计一个跳表，支持：

• search(target)：存在返回true
• add(num)：插入元素（允许重复）
• erase(num)：删除一个值为num的元素，成功返回true

示例：

add(1), add(2), add(3) search(0) → false add(4) search(3) → true erase(0) → false

约束：值 ≤ 2e4，调用次数 ≤ 5e4，要求平均O(logn)。

🧠 核心思路：多层稀疏索引 + 随机化晋升

有序链表的致命伤

查找只能从头遍历，O(n)。二分？链表没有随机访问，取不到中间节点。

灵感：给链表加“快速通道”

建多条链表：

• 第0层：包含所有元素，完整有序链表（数据全在这层）
• 第k层：是第k-1层的稀疏子集（约一半节点晋升）

搜索时：从最高层开始，能往右走就往右走，不能就下降一层。像地铁先坐快线跳过一堆站，再换普通线精确定位——本质是链表的“二分查找”。

谁该晋升？——抛硬币！

如果晋升规则固定（如每隔一个晋升），插入删除后全错位。

跳表的做法：彻底放弃严格维护，改用概率。

插入新节点时，先在第0层出现，然后反复抛硬币——正面晋升一层继续抛，反面停。p通常取0.5。

每个节点层数服从几何分布：50%有1层，25%有2层……期望空间开销只有2个指针/节点。

妙处：插入删除完全不用动其它节点的层数。

凭什么平均O(logn)？

第k层约n·p^k个节点。期望层数 ≈log_{1/p}(n)。

搜索路径反向看：每上升一层+向左一步的期望代价是常数，总层数期望O(logn)，所以总期望代价O(logn)。

注意是期望，最坏O(n)但概率指数衰减，工程可接受。

跳表 vs 红黑树

🖼️ 图解算法（手把手走一遍）

假设存了1~9，按运气晋升后：

第 3 层： H ─────────────────────────────────▶ 7 ─────────────▶ nil 第 2 层： H ────────────────▶ 3 ─────────────▶ 7 ─────────────▶ nil 第 1 层： H ───────▶ 1 ─────▶ 3 ─────▶ 5 ────▶ 7 ─────▶ 9 ────▶ nil 第 0 层： H ──▶ 1 ──▶ 2 ──▶ 3 ──▶ 4 ──▶ 5 ──▶ 6 ──▶ 7 ──▶ 8 ──▶ 9 ──▶ nil

节点7出现在4层，是同一个对象，只是挂了4根forward指针。

走一遍search(7)：

规律：每层往右走到“再走一步就 >= target”为止，然后下降一层；降到第0层后检查正前方是否等于target。路径像一条从左上到右下的阶梯。

💻 代码实现（Python + Java）

Python版

importrandom MAX_LEVEL=32P=0.5classNode:__slots__=('val','forward')def__init__(self,val,level):self.val=val self.forward=[None]*levelclassSkiplist:def__init__(self):self.head=Node(-1,MAX_LEVEL)# 头哨兵self.level=1def_random_level(self):lv=1whilerandom.random()<Pandlv<MAX_LEVEL:lv+=1returnlvdefsearch(self,target:int)->bool:cur=self.headforiinrange(self.level-1,-1,-1):whilecur.forward[i]andcur.forward[i].val<target:cur=cur.forward[i]cur=cur.forward[0]returncurisnotNoneandcur.val==targetdefadd(self,num:int)->None:update=[None]*MAX_LEVEL cur=self.headforiinrange(self.level-1,-1,-1):whilecur.forward[i]andcur.forward[i].val<num:cur=cur.forward[i]update[i]=cur lv=self._random_level()iflv>self.level:foriinrange(self.level,lv):update[i]=self.head self.level=lv node=Node(num,lv)foriinrange(lv):node.forward[i]=update[i].forward[i]update[i].forward[i]=nodedeferase(self,num:int)->bool:update=[None]*MAX_LEVEL cur=self.headforiinrange(self.level-1,-1,-1):whilecur.forward[i]andcur.forward[i].val<num:cur=cur.forward[i]update[i]=cur target=cur.forward[0]iftargetisNoneortarget.val!=num:returnFalseforiinrange(self.level):ifupdate[i].forward[i]isnottarget:breakupdate[i].forward[i]=target.forward[i]whileself.level>1andself.head.forward[self.level-1]isNone:self.level-=1returnTrue

Java 版

importjava.util.Random;classSkiplist{privatestaticfinalintMAX_LEVEL=32;privatestaticfinaldoubleP=0.5;privatefinalRandomrnd=newRandom();staticclassNode{intval;Node[]forward;Node(intval,intlevel){this.val=val;this.forward=newNode[level];}}privatefinalNodehead=newNode(-1,MAX_LEVEL);privateintlevel=1;privateintrandomLevel(){intlv=1;while(rnd.nextDouble()<P&&lv<MAX_LEVEL)lv++;returnlv;}publicbooleansearch(inttarget){Nodecur=head;for(inti=level-1;i>=0;i--){while(cur.forward[i]!=null&&cur.forward[i].val<target)cur=cur.forward[i];}cur=cur.forward[0];returncur!=null&&cur.val==target;}publicvoidadd(intnum){Node[]update=newNode[MAX_LEVEL];Nodecur=head;for(inti=level-1;i>=0;i--){while(cur.forward[i]!=null&&cur.forward[i].val<num)cur=cur.forward[i];update[i]=cur;}intlv=randomLevel();if(lv>level){for(inti=level;i<lv;i++)update[i]=head;level=lv;}Nodenode=newNode(num,lv);for(inti=0;i<lv;i++){node.forward[i]=update[i].forward[i];update[i].forward[i]=node;}}publicbooleanerase(intnum){Node[]update=newNode[MAX_LEVEL];Nodecur=head;for(inti=level-1;i>=0;i--){while(cur.forward[i]!=null&&cur.forward[i].val<num)cur=cur.forward[i];update[i]=cur;}Nodetarget=cur.forward[0];if(target==null||target.val!=num)returnfalse;for(inti=0;i<level;i++){if(update[i].forward[i]!=target)break;update[i].forward[i]=target.forward[i];}while(level>1&&head.forward[level-1]==null)level--;returntrue;}}

⚠️防坑提醒（必看）：

• update[i]必须在同一趟从高到低遍历中一次性收集，不能每层单独遍历。
• 插入时若lv > self.level，多出来的层前驱是头哨兵。
• erase里if update[i].forward[i] is not target: break防止越界。
• 允许重复值，比较用<而非<=。

⏱️ 复杂度分析（面试必问）

期望层数1/(1-p) = 2个指针/节点。p 调小可省内存但搜索变慢——这是平衡树给不了的旋钮。

🚀 举一反三：4道高频变体与延伸

💬 面试追问模拟（提前准备，惊艳全场）

Q1：为什么Redis用跳表而不是红黑树？

四条理由：
①范围查询天然强：ZRANGE一次O(logn)定位起点，沿底层走k步，红黑树需中序遍历；
②实现简单：跳表60行，红黑树删除十几种情形；
③可通过p调参权衡内存与性能；
④ 性能同阶，无劣势。补充：Redis是dict + skiplist双结构，dict负责ZSCOREO(1)定点查，跳表负责ZRANGE/ZRANK。

Q2：跳表层数上限怎么定？

MAX_LEVEL = log_{1/p}(N)。常见取32（Redis就是32），p=0.5可撑2^32元素；Redis p=0.25，32层撑2^64。

Q3：什么场景选平衡树而不是跳表？

① 需要严格最坏保证（实时系统）；
② 内存极度敏感（跳表每节点指针数可变，分配较碎）；
③ 需要树形语义（子树聚合、Rank Tree）。反过来，范围遍历、并发无锁改造、实现速度优先时跳表完胜。

Q4：删除时为什么用update[]而不能从高层顺序删？

必须从低层往高层改，或先收集所有前驱再统一改。一边找一边改会让高层前驱被跳过，留下僵尸节点。

🧩 实战小技巧（刷题党必备）

• 口诀：从高往低走，能右则右；不能则降，底层验等。
• 模板：跳表 = 头哨兵 + 随机层数 + update数组 + 逐层插入/删除。
• 防坑：update数组一趟收集；删除后收缩level。

📈 实际应用场景（不止是刷题）

• Redis 有序集合：排行榜、延迟队列、滑动窗口限流
• LevelDB/RocksDB MemTable：内存索引
• Java ConcurrentSkipListMap：并发有序映射
• Elasticsearch倒排索引：部分跳表加速

🎁 今日思考题

把晋升概率p从0.5调到0.25，内存和查询速度分别怎么变？
提示：内存降约1.33指针/节点，搜索步数变多。

动手题：给今天的Skiplist加一个range(start, end)方法，你会发现比平衡树好写到难以置信。