首页 > Algorithm > 跳表SkipList的原理和C实现

跳表SkipList的原理和C实现

Algorithm 2013-05-29

跳表SkipList,顾名思义是链表的一种,或者说它是单链表的变异实现,使用跳表可以将查询操作的复杂度控制到θ(lg N),而普通的链表只能通过顺序查找,复杂度为θ(N),如此跳表的优势就很明显了,虽然它是通过以空间换时间搞定的。

先看一下普通的有序单链表:

oenhan

要在里面查找一个值就需要顺序比较,复杂度大家都清楚了。如何降低复杂度,折半查找也却可以将复杂度降到θ(lg N),但不适应单链表,那就将折半的思想抽出来,隔一段位置就建立一个标签索引,根据标签索引缩短查找范围,就是跳表,如下图:

跳表通过对间隔的数据做一个标签索引,产生了多层单链表,在最高层依次确定查找数据的范围,最终将范围缩小到可接受值,我们看跳表其实就是一个二叉查找树的变形,只是所有的数据都在最左段,其他节点用来建立查找索引,如此跳表的插入删除就比二叉查找树方便多了。

查找过程:

例子:查找元素 117

  1. 比较 21, 比 21 大,往后面找
  2. 比较 37,   比 37大,比链表最大值小,从 37 的下面一层开始找
  3. 比较 71,  比 71 大,比链表最大值小,从 71 的下面一层开始找
  4. 比较 85, 比 85 大,从后面找
  5. 比较 117, 等于 117, 找到了节点。

查找代码:

DataType *search(DataType x)
{
    DataType *p = Top;

    while(1)
    {
         while (p->right->data < x)
         {    p = p->right;
         }
         if (p->down == NULL)
         {
              return p->right;
         }
         p = p->down;
    }
}

插入过程:

首先需要确定插入数值的层数K,即数值要建立K-1个索引。K通过随机数random(0,1)掷硬币得出,即为投掷出0的次数

如:

int get_level()
{
   k=1;
   while(random(0,1))
   {
        k++;
   }
   return k;
}

跳表的插入-oenhan

如果插入的值是119,层数为2,则遍历倒数2层,插入相关的数据节点。

具体代码:

int skipnode_insert(int value)
{

    int max_level = get_skiplist_level();
    int random_level = get_random_levle();
    int level = max_level;

    /*define point to mark insert location*/
    skipnode *skiplist_heads[random_level];
    memset(skiplist_heads,0,sizeof(skipnode));

    skipnode *p = TOP;
    while(p)
    {
        while(p->next->value < value)
        {
            p = p->next;
        }
        if(level < = random_level)
        {
            skiplist_heads[level-1] = p;
            p = p->down;
            level--;
        }
    }

    p = NULL;
    skipnode * down = NULL;

    for (int i = 0; i < random_level; i++)
    {
         p = skiplist_heads[i];
         skipnode *node = (skipnode*)malloc(sizeof(skipnode));
         /*add new line*/
         if(p == NULL)
         {
            skipnode *node_head = (skipnode*)malloc(sizeof(skipnode));
            node_head->value = -1;
            node_head->down = TOP;
            node_head->next = NULL;

            p = node_head;
            TOP = node_head;
        }
        node->value = value;
        node->next = p->next;
        node->down = down;
        p->next = node;
        down = p;

    }
}

跳表SkipList的原理和C实现来自于OenHan,链接为:http://oenhan.com/skiplist-principle
更多阅读