转载

Skip List不学会就亏大了

如果说要学习一个简单却非常实用的“高级”数据结构,那么Skip List一定不能错过。它的提出已有二十多年[ Pugh, W. (1990) ],却依旧应用广泛(Redis、LevelDB等)。作为平衡树(AVL、红黑树、伸展树、树堆)的替代方案,虽然它性能不如平衡树稳定,但是在实现难度上却很有优势。

Skip List是什么

我们常用数组和链表来组织数据,对于已排序的数据, 数组 的查询时间复杂度可以是$/Theta(lgn)$(二分查找),插入和删除都是$/Theta(n)$。 链表 提供了一种更加灵活的组织方式,插入和删除的时间复杂度是$/Theta(1)$,查询的时间复杂度是$/Theta(n)$。 平衡树 是更好的方案,查询、插入、删除的时间复杂度都是$/Theta(lgn)$,但是实现上就是有点复杂。 Skip List 作为性能和实现难度的一个折中,就这样闪亮登场了,它具有很高概率的使得查询、插入、删除等主要操作时间复杂度也都是$/Theta(lgn)$,下图展示的就是一个Skip List的结构(图中箭头表示指针指向的元素)

Skip List不学会就亏大了

从结构上看,Skip List就是带有层级结构的链表(节点都是排好序的),最下面一层(level-0)是所有元素组成的一个链表,依次往上,每一层都也都是一个链表。不同的是,它们只包含一部分元素,并且越往上元素越少。仔细的话你会发现,通过增加层数,节点上可以带有更多的信息,通过这些信息可以直接访问更远的元素(这也是Skip List精髓所在),感官上就像跳过一些元素一样,所以取名叫Skip List(跳表)。

Skip List查询

查询操作很简单,比如我们要找图中节点key为 20 的元素。

  • 我们首先获取到头节点,从头检点的最高层开始(节点中的点表示指向节点的指针),下一个元素是 17 , 很明显 20>17 所以应该在后面。
  • 继续往后结果是 NULL 那说明后面没有要找的元素了,跳到下一层继续往后是 2520<25 说明,后面也没有我们要找的节点了。
  • 再跳到下一层,往后就找到我们要的节点了。如果到最下面一层还找不到,那这个元素就肯定不在表中了(因为最低层包含所有元素)。

Skip List不学会就亏大了

对比一下,如果只有最低一层的信息,我们要找 20 这个元素是需要 5 次才能找到,但是加上层级,我们有了更远节点的信息,利用更远节点的信息缩小查找范围,这里例子中我们只需要 2 次就找到了。

Skip List插入

插入操作也能很简单, 首先我们要找到插入位置,怎么找我们刚才已经描述过了。如下图所示,插入key为 10 的节点,插入点应该是节点 9 和节点 12 之间(紫色的线表示要更新的指向)。然后是插入节点 10 ,其实就是链表的逐层插入。 Skip List不学会就亏大了

这里的需要注意是,逐层插入需要知道节点在每一层的位置,如在level-2中,节点 10 前面应该是头结点,而后面应该是节点 17 。 因为查询操作得到的只是最后位置,所以通常需要一个临时的空间来记录这些信息。如果节点的高度超过超过了Skip List的最大层数,那么Skip List的层数相应的需要升高。举例如果这个的节点 10 的高度是 4 的话,根据Skip List的结构特点,那么层数需要提高到level-3。

节点高度与Skip List的最大层数

节点的高度是指需要多少域来保存下一个节点的信息,在上面例子中节点 10 的高度是 3 。 事实上这个高度不可能是固定的,如果所有节点高度固定,那Skip List就是失去意义了。通常确定节点高度使用如下的算法:

  • 给定一个概率$p$, 产生一个$[0,1)$ 之间的随机数
  • 如果这个随机数小于$p$,则高度加$1$
  • 重复以上动作,直到随机数大于概率$p$

Skip List的层数跟结构中最高节点高度相等。 但是通常我们还会约束Skip List的最大层数,公式:$maxLevel=log_{1/p}n$,其中n表示节点总数。 根据Pugh论文中的结论,p为1/2或者1/4时,整体性能会比较好。(当p=1/2时,确定节点高度有的地方称为抛硬币的方法)。

Skip List删除

删除操作就是插入操作的反向操作。 首先找到我们要删除节点的位置,在查找时使用临时空间记录节点在每一级的位置。 接着就是逐层的链表删除操作。 最后记住要释放空间。 删除节点之后,如果最高层没有节点存在,那Skip List的层数相应的需要降下来。 下图表示节点 9 的删除操作。 Skip List不学会就亏大了

正文到此结束
Loading...