对 CLRS 随机构建的二叉搜索树证明中的主张感到困惑

Question

不确定我是否应该把它放在 math 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 影响 子树中键的数量似乎暗示了一种依赖关系，因为它限制了高度 的子树。

我显然错过了一些关键的关系。如有任何帮助，我们将不胜感激，谢谢。

Answer 1

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

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