如何在跳跃表中插入算法？

跳跃表的插入算法要复杂一点。如下图所示。首先，需要按照上述查找流程找到待插入元素的前驱和后继；然后，按照如下随机算法生成一个高度值：

// p是一个(0,1)之间的常数，一般取p=1/4或者1/2

public void randomHeight(double p){

int height = 0 ;

while(random.nextDouble() < p) height ++ ;

return height + 1;

}

最后，将待插入节点按照高度值生成一个垂直节点（这个节点的层数正好等于高度值），之后插入到跳跃表的多条链表中去。假设height=randomHeight(p)，这里需要分两种情况讨论：

如果height大于跳跃表的高度，那么跳跃表的高度被提升为height，同时需要更新头部节点和尾部节点的指针指向。

如果height小于等于跳跃表的高度，那么需要更新待插入元素前驱和后继的指针指向。

资料来源：《HBase原理与实践》，文章链接：https://developer.aliyun.com/article/724670