数据结构 Skip List 实现了二分查找

• 数组可以用下标进行索引。
• 一个排序的数组可以用二分法查找
• 二分法需要计算「中间节点」的下标
• 链表不能用下标进行索引
• 因此链表不能直接使用二分法
• 变通的方法是二分查找树，即二叉树
• 插入元素时保持树的平衡很重要
• Skip List 实质上也是实现了二分查找
• 逐层抽样出「中间节点」

Node 节点

// 普通的 List Node
struct SkipNode {
  const char *key;
  Node *next[1];
}

Skip List 的 Node 需要多个 next 指针，分别用于不同的 level 。

// Skip List Node
struct SkipNode {
  const char *key;
  Node *next[1];
}

实际使用时 next 字段需要动态分配大小。

Skip List Search

具体到某个特定的 level, 是一个线性的 List Search，找到目标值所在的区间。

SkipNode * skiplist_search(
  const char *key,
  int level,
  SkipNode **head,
  SkipNode **tail
){
  SkipNode *node, *prev;

  for(node=*head, prev=NULL; node!=*tail; prev=node , node=node->next[level]){
    int rc = strcmp(key, node->key);
    if(rc>0){
      continue;
    } else if(rc==0){        // target found
      return node;
    } else if(rc<0){         // range found: (prev, node)
      *head = prev;
      *tail = node;
      return NULL;
    }
  }
                             // target miss
  *head = NULL;
  return NULL;
}

从最顶层开始，逐层向下逼近搜索结果。

SkipNode * skiplist_find(const char *key, SkipNode *head){
  const Node *sub_head = head;
  const Node *sub_tail = NULL;

  int level = skiplist_level(head);
  while(level--){
    int found = 0;
    Node *target = skiplist_search(key, level, &sub_head, &sub_tail);
    if(target!=NULL){
       return target;
    } else if(sub_head==NULL){
       break;
    }
  }
  return NULL;
}

需要知道 Skip List 的层数。一个“取巧”的办法是在 head 节点里间接地通过 next 数组的大小来反映。

int skiplist_level(SkipNode *head){
   int level = 0;
   while(head->next[level] != NULL) levle++;
   return level;
}

实际上就是下面这种技巧的应用。

const char *string_list[] = {
   "abc",
   "def",
   NULL
}