0

给定 randomLevel() 函数：

enter code here

randomLevel()
    newLevel := 1
        --random() returns a random value in [0,1)
    while random() < p do
        newLevel := newLevel+1
    return min(newLevel,MaxLevel)

这用于确定在插入节点时他将获得什么级别，根据 pugh 的文章，列表的最大级别 a 大于 k 的概率等于 1 - (1 - p^k )^n并且文章还说这个表达式最多为 np^k （因此对于那些知道这篇文章的人来说，预期的最大水平最多为 L(n) + 1/(1-p)..）。

我在理解这个数字的来源时遇到了严重的麻烦，因为我所能想到的就是 P(j 级的节点) = (p^j) (1-p) => P(大于 k 的节点) = 1 - sum(P(第 i 层中的节点), i=1 到 i=k) 这导致 P(最大级别 > k) = P( 级别 > k 中的节点之一) = n P(节点在大于 k 的级别) = ... = n*(1+p*(p^k-1))

帮助 ？？？谢谢 ：）

4

1 回答 1

0

考虑到p = 0.5，你有：

1/2 of the nodes at level 1
1/4 of the nodes at level 2
1/8 of the nodes at level 3
1/16 of the nodes at level 4
etc.

节点处于 levelk的概率是节点处于 level 的概率的 1/2 k-1。

或者，使用您发布的符号：

P(node in level greater than k) = 1 - sum(P(node in level i), i=1 to i=k)

因此，一个节点的级别大于 4 的概率例如是：

= 1 - (1/2 + 1/4 + 1/8 + 1/16)
= 1 - (8/16 + 4/16 + 2/16 + 1/16)
= 1 - 15/16
= 1/16
于 2014-10-30T20:20:51.297 回答