algorithm - 对 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)) 个节点作为叶子(大约是总节点的一半是叶子)。新值到达任何地方的概率相同(即作为任何这些节点的子节点)。预计其中一半将成为叶子的左 child (将叶子节点的高度增加 1)，另一半将成为该叶子的右 child 。这为树提供了预期的 O(log n) 高度。因此，对这样一棵树的每个操作都花费 O(log n)。