概述

Skip list(也称跳表)是一种随机化数据结构,基于并联的链表,其效率可比拟二叉查找树(对于大多数操作需要O(log n)平均时间)。

基本上,Skip list是对有序的链表增加上附加的前进链接,增加是以随机化的方式进行的,所以在列表中的查找可以快速的跳过部分列表,因此得名。所有操作都以对数随机化的时间进行。一个基本的Skip list结构如下:

SkipList

Skip list有如下特征:

  • 总体结构类似有序链表,只是在其中的某些节点Ni上增加了更多的索引(单链表每个节点只有一个指向后继节点的索引),且Ni的索引数随机(某个范围内);

算法

初始化

skip list本质上仍然是一个链表,其结构与普通单链表一致。每个skip list都有一个表头节点,每个表头节点都有MaxLevel个索引,指向后继节点。且表头节点的值为极大。

查找

在Skip list中查找一个节点算法类似单链表的查找过程,比较简单。下图演示了key=17节点查找过程:

SkipList

在这里,我们假设每个节点Node的后继节点索引为forward[N] (N为Node的level),查找从链表头head节点开始,整个过程用伪代码的形式表示如下:

Search(list, searchKey)
// 从链表表头节点开始
// 从上至下沿着leve判断该节点的每个后继节点的值与目标值大小关系
// 如果小于,沿着该level往后继续走到下一个节点
x := list→header
for i := list→level downto 1 do
    while x→forward[i]→key < searchKey do 
        x := x→forward[i]
    if x->key = searchKey then return x->value

// 走到最底层了,如果相等则存在,否则就不存在
x := x→forward[1]
if x→key = searchKey then return x→value
else return failure

以上图为例,查找一个已存在节点17的过程如下:

  1. 从head开始,head的level为4,判断head->forward[3]->key(6) < 17,此时x变为head->forward[3],x成为节点6;
  2. 节点6的level为4,判断x->forward[3]为NIL,因此level降低到2,判断x->forward[2]->key(25) > 17,继续降低level到1,判断x->forward[1]->key(9) < 17,此时x变为x->forward[1],x成为节点9;
  3. 节点9的level为2,判断x->forward[1]->key为17,因此找到节点,直接返回。

如果查找一个不存在的节点18,过程变为:

  1. 同上面1;
  2. 同上面2;
  3. 节点9的level为2,判断x->forward[1]->key为17,小于18,因此,x变为x->forward[1],变为17;
  4. 节点17的level为2,判断x->forward[1]->key为25,大于18,因此,level降低为0,判断x->forward[0]->key为19,大于18,此时level已经到底,无法再往下降,跳出循环;
  5. 判断x->forward[0]->key为19,不等于18,因此返回结果”节点不存在”。

插入

向skip list中插入一个节点,首先得查找节点是否存在,然后更新查找路径上的所有节点的后缀索引。具体过程用伪代码表示:

Insert(list, searchKey, newValue) 
{
    local update[1..MaxLevel]
    x := list→header
    for i := list→level downto 1 do
        while x->forward != NIL && x→forward[i]→key < searchKey do
            x := x→forward[i]
        update[i] := x
    x := x→forward[1]
    // key已存在,原地更新即可
    if x→key = searchKey then 
        x→value := newValue 
    else
    // key 不存在,生成一个新Node并为其随机生成level
        l := randomLevel()
        // 如果新node的level超过list的当前最大节点level
        // 先将
        if l > list→level then
            for i := list→level + 1 to l do 
                update[i] := list→header
            list→level := l
        x := makeNode(lvl, searchKey, value)
        // 更新搜索路径上的节点的索引
        for i := 1 to l do
            x→forward[i] := update[i]→forward[i]
            update[i]→forward[i] := x
}

SkipList

我们以此图为例,list->leve=4,如果要插入节点17,首先确定搜索路径:

  1. update[3] = node(6);
  2. update[2] = node(6);
  3. update[1] = node(9);
  4. update[0] = node(12)

创建新节点node(17),并为其生成level(随机),该level可能值为[1, MaxLevel],此时需要对比,如果level < list->level,需要先将突出的部分从header指向它,如下图所示:

SkipList

这里新生成的节点node(17)的level为5,超过了list当前的最大level,于是将update[4]设置为header,后续直接将node(17)作为header的后继。

接下来便是设置搜索路径上每个节点的后继关系了,如下图所示:

SkipList

为节点随机生成level的算法如下:

randomLevel()
{
    level := 1
    // random() that returns a random value in [0...1)
     while random() < p and level < MaxLevel do
        level := level + 1 
    return level
}

删除

从skip list中删除一个节点,首先获得节点的查找路径,然后更新查找路径上的所有节点的后缀索引。具体过程用伪代码表示:

Delete(list, searchKey)
{
    local update[1..MaxLevel]
    x := list→header
    // 获得待删除节点的查找路径
    for i := list→level downto 1 do
        while x→forward[i]→key < searchKey do 
            x := x→forward[i]
        update[i] := x
    x := x→forward[1]
    // 如果目标节点存在,更新查找路径上节点的后缀索引
    if x→key = searchKey then
        for i := 1 to list→level do
            if update[i]→forward[i] == x then 
                update[i]→forward[i] := x→forward[i]

        free(x)
        // 更新list->level(删除x可能导致list->level下降)
        while list→level > 1 and list→header→forward[list→level] = NIL do
            list→level := list→level – 1
}

由于过程比较简单,我们这里就不画图分析。

分析

我们主要从时间和空间复杂度方面来计算Skip list的效率。

空间效率

skip list的空间消耗主要体现在每个节点的level个后缀索引上,于是我们得计算节点的平均level数,因为每个节点的level数是按照一定概率随机生成,参考上面的生成算法,则我们可以得出如下公式:

则节点平均level数为

简单计算可得:

时间效率

skip list的时间消耗主要在以下几个部分:

  • 搜索节点,对于任何操作都必不可少;
  • 更新索引,只在插入或者删除中出现。

其中搜索节点又是时间消耗的重点所在,因为更新索引只与list的最大level相关,是一个常量,与节点数无关。因此,计算时间效率关键在于计算平均搜索路径的长度。

我们假设对于节点node的搜索路径为

其中pi的定义为

node(x): pi所在节点;
level(i): pi位于节点的第level(i)层

例如,下图节点17的查找路径为

SkipList

说明:这里假设层级从1开始计数

对于如何计算层高为k的skip list的平均搜索路径长度着实消耗了我不少的脑细胞,因为论文中真的只是一笔带过。计算方法如下:

其中C(k)表示在搜索路径上从level为k的节点上至终点的路径长度。如何理解这个公式?
我们结合上面的查找过程发现,在skip list的任意一个节点,无非有两条路径可走,如下面的情况b和c:

SkipList

  • 如果是情况b,那么我们搜索路径长度增加1,但是搜索level并没有下降;
  • 如果是情况c,那么我们搜索路径长度增加1,且搜索level也下降1;

而最大难题就是计算每种情况发生的概率,我们可以倒着推:从搜索路径的终点向起点开始反向推倒,因为路径就是这个路径,正推反推长度都不变:

于是对任意一个节点,其搜索路径上的前向节点要么是自己(搜索高度下降,这就是情况c),要么是来自其前向节点(搜索高度不变,对应情况b),如下图所示:

SkipList

例如图中的node(9),其搜索路径中的子路径包含

[node(6):2] -> [node(9):2] 即是路径加长,但是层高不变;
[node(9):2] -> [node(9):1] 即是路径加长,而且层高下降;
[node(9):2] -> [node(9):1]这条路径,意味着node(9)的level至少比索引node(9):1所在的高度高(否则搜索路径上node(9):1的前驱就是node(9)的某个前驱节点,比如node(6)),根据前面的层高选择公式,这个概率p为:高度至少为x的node,它的层高大于x的概率。根据层高选择公式,即为:下次while()循环时,random()的结果<p,这个概率就是p。
因此,得出如下结论:

  • 搜索路径上的某个端点来自同一个节点的概率为p(搜索高度下降1);
  • 搜索路径上的某个端点来自前一个节点的概率为1-p(搜索高度不变)。

这就证明了前面的公式:查找一个层高为k的skip list其时间复杂度为k/p
接下来就是考虑拥有n个节点的skip list其level计算规则。

首先确定skip list的高度期望值h。给定数据项存储在第i层的某个位置的概率等于在上面的选择算法中前i-1次random()都位于(0, p)范围,而最后一次选择(p, 1)范围。即

因此,第i层至少有一个数据项的概率最多为

则skip list的层数大于i的概率等于第i层至少有一个元数的概率。即意味着level大于

的概率

=

即h小于等于

的概率至少为

此意味着skip list的高度为

的概率较大,带入我们上面的时间复杂度计算公式得到最后的时间复杂度为

参考资料

  • http://epaperpress.com/sortsearch/download/skiplist.pdf
  • https://github.com/tracymacding/skip-list.git (go语言skip list实现)