Skip List

 22nd January 2021 at 2:17pm

Skip list（跳表）是一种以概率论为基础的线性数据结构。它可以说是有序链表的增强版。长得像这样：

支持：插入新数据、搜索某一数据、删除某一数据。

特点：

  • 多层结构。每一层都是一个有序的链表。越上层数据越稀疏。最下层包含全部数据
  • 对比有序链表：因为稀疏的上层数据，使得搜索速度变快了，因此插入、删除操作也变快了
  • 仍然保留有序链表插入、删除新数据的开销小、不用像数组一样挪动全部数据的特点

理解 skip list 的关键点在于理解它是 如何生成新的 level 的。每当插入数据时，最下层（称之第一层）是一定必须插入的，之后第二层有 12\frac{1}{2} 概率要插入，第三层有 (12)2(\frac{1}{2})^2，第四层则是 (12)3(\frac{1}{2})^3，依此类推。一旦有一层不再插入，则整个插入结束。因此假如现在只有 3 层，但是插入一个新数据时使得第 4 层也有了数据，就需要建新的一层出来。

编码时可用编程语言提供的随机库（如 Python 标准库中的 random）来做概率判断。注意的是：在判断每一层是否应该插入时，要注意概率判断时的累积问题（看下面代码实现中 random.getrandbits(1) 处的注释）。

花花酱的 Python 语言实现：

import random
 
class Node:
  def __init__(self, val=-1, right=None, down=None):
    self.val = val
    self.right = right
    self.down = down
    
class Skiplist:
  def __init__(self):
    self.head = Node() # Dummy head
 
  def search(self, target: int) -> bool:
    node = self.head
    while node:
      # Move to the right in the current level
      while node.right and node.right.val < target:
        node = node.right
      if node.right and node.right.val == target:
        return True
      # Move to the the next level
      node = node.down
    return False
 
  def add(self, num: int) -> None:
    nodes = []
    node = self.head
    while node:
      # Move to the right in the current level
      while node.right and node.right.val < num:
        node = node.right
      nodes.append(node)
      # Move to the next level
      node = node.down
    
    insert = True
    down = None
    while insert and nodes:
      node = nodes.pop()
      node.right = Node(num, node.right, down)
      down = node.right
      # 特别注意这一行：因为概率是会累积的，判断每一层是否要插入时，
      # 只需要有 50% 概率就行（也就是 random.getrandbits(1) 的意义）。
      insert = (random.getrandbits(1) == 0)      
    
    # Create a new level with a dummy head.
    # right = None
    # down = current head
    if insert:
      self.head = Node(-1, None, self.head)
 
  def erase(self, num: int) -> bool:
    node = self.head
    found = False
    while node:
      # Move to the right in the current level
      while node.right and node.right.val < num:
        node = node.right
      # Find the target node
      if node.right and node.right.val == num:
        # Delete by skipping
        node.right = node.right.right
        found = True
      # Move to the next level
      node = node.down      
    return found
        
# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)

参考