3

不知道我是否应该把它放在数学 stackexchange 上，但是哦。

在 CLRS 的第 300 页...

Theorem 12.4
The expected height of a randomly built binary search tree on n distinct keys is O(lgn).

他们定义了3个随机变量......

'Xn' is the height of a randomly built binary search on n keys.
'Yn' is the "exponential height", where Yn = 2^(Xn)
'Rn' is the position that the root key would occupy if the key's were sorted, its rank.

和指标随机变量Zn,1 Zn,2 Zn,3 ... Zn,n...

'Zn,i = I{Rn = i}'

因此，他们继续进行证明（见正文），但在此过程中，他们提出了以下主张……

We claim that the indicator random variable Zn,i = I{Rn = i} is independent of the
values of Yi-1 and Yn-i. Having chosen Rn = i, the left subtree (whose exponential
height is Yi-1) is randomly built on the i-1 keys whose ranks are less than i. This
subtree is just like any other randomly built binary search tree on i-1 keys.
Other than the number of keys it contains, this subtree's structure is not affected
at all by the choice of Rn = i, and hence the random variables Yi-1 and Zn,i are
independent.

对于 Yn-i 也是如此。我的问题是那部分，除了它包含的键的数量......是的，子树的结构不受 Rn 的影响，但是 Rn 影响子树中键的数量这一事实似乎暗示了依赖于如何它限制了子树的高度。

我显然错过了一些关键的关系。任何帮助表示赞赏，谢谢。

4

1 回答 1

0

对于预期的时间证明，您可以将每个插入视为一个独立事件。插入器不是对抗性的（即不会尝试破坏您的二叉树）。现在，如果这确实是随机的，那么您可以将要插入的每个其他（每个奇数或每个偶数）值视为作为坏节点插入。坏节点是导致树高度增加的节点。坏节点之间有好节点。

如果你已经有一棵高度为“h”的树（考虑它有 O(2^h) 个节点），那么它将有 O(2^(h-1)) 个节点作为叶子（大约一半的节点是叶子） . 新值出现在任何地方的概率相同（即作为任何这些节点的子节点）。预计其中一半将成为叶子的左孩子（将叶子节点的高度增加 1），另一半将成为该叶子的右孩子。这为树提供了预期的 O(log n) 高度。因此，对这种树的每个操作都需要 O(log n)。

于 2011-11-19T15:26:07.373 回答