3

代わりにこれを 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がサブツリー内のキーの数に影響を与えるという事実は、サブツリーの高さを制限します。

私は明らかにいくつかの重要な関係を欠いています。どんな助けでも大歓迎です、ありがとう。

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 に答える