那为什么叫做概率数据结构呢?这个问题后面再解答.
查找节点
跳跃表是如何提高查找效率的呢?
将上图旋转45°,就会发现与二叉查找树是类似,遍历时可以快速跳过很多节点....添加元素
以上面3层结构为例,我们需要添加一个值为95的元素
首先会按上图红线遍历得知,需要在元素90后新增节点95.
2. 建塔升层
那节点95是否要在下一层建塔升层,根据什么判断呢?...这里采用的是coin flip(抛硬币)算法.
也就是和抛硬币一样,要么正面,要么反面,并没有固定规律,也正是这种随机性,跳跃表称为概率数据结构....对应这里就是元素随机建塔升层,或不建塔升层.实现方式也很简单,1以内取随机数,规定大于等于0.5建塔升层,小于0.5不进行建塔升层.
例如,我们计算的随机数值为0.6,那就需要建塔升层....删除节点
节点的删除,首先按照查找逻辑,找对对应节点,在删除节点时,除了要删除节点本身,还需要将塔的各层也一并删掉,并将各层元素节点连接起来.