バランスの取れた探索木の​​深さの証明

Question

Tは、その左の部分木L、n個の要素を持つバランスBSTであり、その正しいものをR、どのようにその深さ（n）が2log以下であることを証明できる場合は+ 1？

は、私が持っている誘導によって証拠があるが、私はそれを得ることはありません。

（私は指向stackoverflowのは主にプログラミングされていることを理解しますが、私は二分探索木に関するいくつかの質問を発見し、それを試してみることにしました、私は良いではない何かをしておりません願っています：。））

Answer 1

「バランス」の定義では、同じノードのすべての左と右のサブツリーの深さは1で、最大異なります。例えば1つのルートと2枚の葉（それらがバランスBSTに配置することができる唯一の方法で、三つの要素）とBSTであるように「深さ」、通常、「下葉のツリールートから最長の歩行ステップ数」として定義されます、1つの根と1つのリーフと1が（その葉は根の左または右のサブツリーは違いはありませんか）と同じように、深さ1（あなたがそれを深さ2を与えるだろう、わずかに異なる定義を使用しているように見えますが？）持っていると言わまた、葉ちょうど根を持つ1（単一要素）が深さ0を持っているだろうが（ゼロ要素とはBSTはありません）。

nのので<上記で定義したようにD（N）木の深さを呼び出す= 3つの要素は、明確に、（また、不平等のRHSれるD(n) < log(n) + 1 logので、検査によって（底2対数を意味1 = D(2) < log(2) + 1 = 2で）1 = D(3) log(3) + 1は、）実際の> 2であり、そして0 = D(1) < log(1) + 1 = 1 - 。これは私たちに誘導基盤を提供します。

私たちは、すべてのD(k) < log(k) + 1のためならばk < nが、それはまた、そのD(n) < log(n) + 1に従っていることを示さなければならない誘導による証明を完了します。

nが奇数の場合、明らかに左右のサブツリー要素それぞれを(n-1)/2、およびツリーがサブツリーよりも深さ1以上を有しています。その後D(n) = 1 + D((n-1)/2) < 1 + 1 + log((n-1)/2)（= 1 + log(n-1)以降）（帰納法の仮定により）log((n-1)/2) = log(n-1) - 1したがってなおさら< 1 + log(n)、QED。

nが偶数の場合は、

は、あなたの代わりにlog(n)のと「Aましてや」仕上げなしlog(n-1)とちょうど同じ手順に従ってください、との証拠はまだ保持します。

Answer 2

平衡二分木は、左右のサブツリー内の要素の数をすることができ完了している場合は、

あなたの答えは真である（N-1）/ 2が、それは完全ではない場合、要素の数はである必要はない（n-1）の/ 2として最後のレベルが異なる要素を有することができる