Skip List的工作原理
Skip List(跳跃表)是一种支持快速查找的数据结构,插入、查找和删除操作都仅仅只需要O(log n)
对数级别的时间复杂度,它的效率甚至可以与红黑树等二叉平衡树相提并论,而且实现的难度要比红黑树简单多了。
Skip List主要思想是将链表与二分查找相结合,它维护了一个多层级的链表结构(用空间换取时间),可以把Skip List看作一个含有多个行的链表集合,每一行就是一条链表,这样的一行链表被称为一层,每一层都是下一层的”快速通道”,即如果x层和y层都含有元素a,那么x层的a会与y层的a相互连接(垂直)。最底层的链表是含有所有节点的普通序列,而越接近顶层的链表,含有的节点则越少。
对一个目标元素的搜索会从顶层链表的头部元素开始,然后遍历该链表,直到找到元素大于或等于目标元素的节点,如果当前元素正好等于目标,那么就直接返回它。如果当前元素小于目标元素,那么就垂直下降到下一层继续搜索,如果当前元素大于目标或到达链表尾部,则移动到前一个节点的位置,然后垂直下降到下一层。正因为Skip List的搜索过程会不断地从一层跳跃到下一层的,所以被称为跳跃表。
Skip List还有一个明显的特征,即它是一个不准确的概率性结构,这是因为Skip List在决定是否将节点冗余复制到上一层的时候(而在到达或超过顶层时,需要构建新的顶层)依赖于一个概率函数,举个栗子,我们使用一个最简单的概率函数:丢硬币,即概率P
为0.5
,那么依赖于该概率函数实现的Skip List会不断地”丢硬币”,如果硬币为正面就将节点复制到上一层,直到硬币为反。
理解Skip List的原理并不困难,下面我们将使用Java来动手实现一个支持基本需求(查找,插入和删除)的Skip List。
本文作者为SylvanasSun(sylvanas.sun@gmail.com),首发于SylvanasSun’s Blog。
原文链接:https://sylvanassun.github.io/2017/12/31/2017-12-31-skip_list/
(转载请务必保留本段声明,并且保留超链接。)
节点与基本实现
对于一个普通的链表节点一般只含有一个指向后续节点的指针(双向链表的节点含有两个指针,一个指向前节点,一个指向后节点),由于Skip List是一个多层级的链表结构,我们的设计要让节点拥有四个指针,分别对应该节点的前后左右,为了方便地将头链表永远置于顶层,还需要设置一个int属性表示该链表所处的层级。
|
|
接下来是SkipList的基本实现,为了能够让Key进行比较,我们规定Key的类型必须实现了Comparable接口,同时为了支持ForEach循环,该类还实现了Iterable接口。
|
|
我们还需要定义几个辅助方法,如下所示(都很简单):
|
|
查找
查找一个节点的过程如下:
从顶层链表的头部开始进行遍历,比较每一个节点的元素与目标元素的大小。
如果当前元素小于目标元素,则继续遍历。
如果当前元素等于目标元素,返回该节点。
如果当前元素大于目标元素,移动到前一个节点(必须小于等于目标元素),然后跳跃到下一层继续遍历。
如果遍历至链表尾部,跳跃到下一层继续遍历。
|
|
插入
插入操作的过程要稍微复杂些,主要在于复制节点到上一层与构建新层的操作上。
|
|
删除
对于删除一个节点,需要先找到节点所在的位置(位于最底层链表中的位置),之后再自底向上地删除该节点在每一行中的冗余复制。
|
|
迭代器
由于我们的SkipList实现了Iterable接口,所以还需要实现一个迭代器。对于迭代一个Skip List,只需要找到最底层的链表并且移动到它的首节点,然后进行遍历即可。
|
|