什么是跳跃表

跳跃表（skiplist)是一种基于有序链表的扩展，简称跳表

image.png

时间和空间复杂度

插入的时间复杂度是：O(logN)
查找的时间复杂度：O(logN)
占用空间是2N，即空间复杂度O(N)

性质

1.分层
2.每一层都是有序的链表
3.最底层包含所有的元素
4.上一层是当前层的子集
5.每个结点包含有两个指针：指向下一个节点和指向下一层节点

算法

计算元素所占的层数：

int random_level()
{
    K = 1;
    while (random(0,1))
        K++;
    return K;
}

相当于抛硬币实验，抛到硬币正面需要抛的次数
随机变量K满足参数为p = 1/2的几何分布，期望为E（K) = 1/p = 2, 每个元素的层数，期望值是2层，N个元素的跳跃表占用空间是2N

插入：

计算得到K,然后再1到K层的链表都插入元素

image.png

查找

现在当前层查找，再到下一层查找

image.png

几何分布

在n次伯努利试验中，试验k次才得到第一次成功的机率。详细地说，是：前k-1次皆失败，第k次成功的概率。
在伯努利试验中，成功的概率为p，若ξ表示出现首次成功时的试验次数，则ξ是离散型随机变量，它只取正整数，且有P(ξ=k)=(1-p)的(k-1)次方乘以p (k=1，2，…，0<p<1)，此时称随机变量ξ服从几何分布。它的期望为1/p

应用

redis的有序集合

跟红黑树比较

优点是维持结构平衡的成本比较低，完全依靠随机
红黑树靠节点着色和