在CLRS困惑的要求随机内置二叉搜索树的证明 [英] Confused on claim in CLRS randomly built binary search tree proof

问题描述

不知道我是否应该把这个数学stackexchange代替，但很好哦。

Not sure if I should put this on math stackexchange instead, but oh well.

在CLRS ...

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

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

They define 3 random variables...

'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.

和指标随机变量锌，1锌，锌2，3 ...锌，N ...

And indicator random variables Zn,1 Zn,2 Zn,3 ... Zn,n...

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

于是，他们继续做证明（见正文），但在它的中间，他们提出以下要求...

So they go on to make the proof (see the text), but in the midst of it they make the following claim...

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的影响 键的子树数目似乎暗示一个依赖由于如何它限制了高度 的子树。

Likewise for Yn-i. My issue is that part, Other than the number of keys it contains... Yes, the structures of the subtrees are unaffected by Rn, but the fact that Rn affects the number of keys in the subtrees seems to imply a dependence due to how it limits the height of the subtrees.

我显然缺少一些关键的关系。任何帮助是AP preciated，谢谢。

I'm obviously missing some key relationship. Any help is appreciated, thanks.

推荐答案

有关在预期的时间证明，你能想到的每一个插入的是一个独立的事件。插入器是不是对抗性的（即不尝试打破你的二叉树）。现在，如果这是真正随机的，那么你可以考虑每隔（每个奇数或每个偶数）值要插入的插入一个坏的节点。坏节点是那些导致树增加高度。坏节点具有良好的节点之间。

For the expected time proof, you can think of every insertion to be an independent event. The inserter is not adversarial (i.e. doesn't try to break your binary tree). Now, if this is truly random, then you can consider every other (every odd or every even) value to be inserted as being inserted as a bad node. Bad nodes are ones that cause the tree to increase in height. Bad nodes have good nodes between them.

如果你已经拥有的高度H一棵树（认为它有O（2 ^ H）节点），那么它将有O（2 ^（H-1））节点作为叶（约总数的一半节点是树叶）。有一个新的值去​​（即作为任何那些节点的一个子）的任意位置的概率相同。据预计，其中一半将成为叶的左子（增加1的叶节点的高度），而另一半将成为叶的右子。这给出了一个预期为O（log n）的高度到树中。因此，在这样的树成本o每个操作（log n）的。

If you already have a tree of height 'h' (consider it has O(2^h) nodes), then it will have O(2^(h-1)) nodes as leaves (approximately half the total nodes are leaves). There is an equal probability of a new value going anywhere (i.e. as a child of any of those nodes). It is expected that half of them will become left child of a leaf (increasing the height of the leaf node by 1) and the other half will become the right child of that leaf. This gives an expected O(log n) height to the tree. Hence, every operation on such a tree costs O(log n).

这篇关于在CLRS困惑的要求随机内置二叉搜索树的证明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！