Tがn個の要素を持つ平衡BSTであり、Lが左側のサブツリー、Rが右側のサブツリーである場合、その深さが2log（n）+1以下であることをどのように証明できますか？
私が持っている帰納法による証拠がありますが、私はそれを取得していません。
（stackoverflowは主にプログラミング指向であることを理解していますが、バイナリ検索ツリーに関するいくつかの質問を見つけて試してみることにしました。うまくいかないことを願っています。:)）
2431 次
2 に答える
2
「バランスのとれた」の定義により、同じノードのすべての左右のサブツリーの深さは、最大で1つ異なります。「深さ」は通常、「木の根から葉までの最長の歩行のステップ数」として定義されます。たとえば、1つの根と2つの葉を持つBST（バランスの取れたBSTに配置できる唯一の方法で3つの要素）は次のようになります。深さ1（深さ2を与えるわずかに異なる定義を使用しているように見えますか？）、1つのルートと1つのリーフ（そのリーフがルートの左または右のサブツリーであるかどうかに関係なく）を持つと言われています、一方、葉（単一の要素）でもあるルートのみを持つものは、深さが0になります（要素がゼロのBSTはありません）。
したがって、n <= 3の要素の場合、D（n）を上記のように定義されたツリーの深さと呼びます。これは、検査によって明確にD(n) < log(n) + 1（2を底とする対数を意味logします）、-これは私たちに誘導ベースを与えます。1 = D(2) < log(2) + 1 = 21 = D(3)log(3) + 1> 20 = 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)log(n-1)
于 2009-11-08T00:37:21.507 に答える
0
平衡二分木が完全である場合、左右のサブツリーの要素数は（n-1）/ 2になる可能性がありますが、完全でない場合、要素数は（n-1）/2である必要はありません。最後のレベルには異なる要素が含まれる場合があります
于 2016-08-04T16:10:12.747 に答える