跳跃表是基于链表的概率数据结构,完善了链表不易查询的缺点.
跳跃表的基本结构如下:
每一横向的链表子序列称为层;
每一纵向的相同值的节点序列称为塔;
链表的头部和尾部通常使用-INF(负无穷)和 INF(正无穷)表示;
通常,上一层的元素数量是下一层数量的一半.
那为什么叫做概率数据结构呢?这个问题后面再解答.
查找节点
跳跃表是如何提高查找效率的呢?
将上图旋转45°,就会发现与二叉查找树是类似,遍历时可以快速跳过很多节点.
对于二叉查找树不熟悉的可以参考二叉树.
可见,当层越多时,可跳过的节点也就越多,查找效率也就越高.
添加节点
1. 添加元素
以上面3层结构为例,我们需要添加一个值为95的元素
首先会按上图红线遍历得知,需要在元素90后新增节点95.
2. 建塔升层
那节点95是否要在下一层建塔升层,根据什么判断呢?
这里采用的是coin flip(抛硬币)算法.
也就是和抛硬币一样,要么正面,要么反面,并没有固定规律,也正是这种随机性,跳跃表称为概率数据结构.
在元素数量足够多时,硬币正反的概率是相同的,所以基本也是上一层元素数量是下一层的一半.
对应这里就是元素随机建塔升层,或不建塔升层.实现方式也很简单,1以内取随机数,规定大于等于0.5建塔升层,小于0.5不进行建塔升层.
例如,我们计算的随机数值为0.6,那就需要建塔升层.
明显,跳跃表在搜索时是从上层至下层的顺序,而添加时正好相反,是从下层至上层的顺序.
删除节点
节点的删除,首先按照查找逻辑,找对对应节点,在删除节点时,除了要删除节点本身,还需要将塔的各层也一并删掉,并将各层元素节点连接起来.
同样以元素95为例
可见,为了方便找到前置节点,最好是采用双向链表
以上就是跳跃表的基本操作,它在保留链表插入快的基础上,还提升了搜索效率,将搜索的时间复杂度由O(N) 提升为 平均O(log(N)),最坏O(N).
在插入时,相比维护二叉树的旋转和重新分配也要快速的多.
是典型的空间换时间的数据结构.
