跳表节点层数的确定方法

• 初始化节点层数为1，这是跳表中所有节点的初始层数
• 对每个节点，通过随机数生成器生成一个介于0和1之间的随机数p
• 将p与固定的概率因子P进行比较，如果p小于P，则将节点的层数加1
• 重复步骤2和步骤3，直到p大于或等于P为止

产生越高的节点层数，概率越低。定量的分析如下：

假设概率因子是p，节点层数至少为 1。

而大于 1 的节点层数，满足一个概率分布：

• 节点层数恰好等于 1 的概率为 1-p
• 节点层数大于等于 2 的概率为 p，而节点层数恰好等于 2 的概率为 p(1-p)
• 节点层数大于等于 3 的概率为 p^2，而节点层数恰好等于 3 的概率为 p^2*(1-p)
• 节点层数大于等于 4 的概率为 p^3，而节点层数恰好等于 4 的概率为 p^3*(1-p)
• ……

一个节点的平均层数（也即包含的平均指针数目）（期望）：

现在很容易计算出：

• 当 p=1/2 时，每个节点所包含的平均指针数目为 2
• 当 p=1/4 时，每个节点所包含的平均指针数目为 1.33