0

AVL ツリーのノードの最小数を証明するこの ( http://condor.depaul.edu/ntomuro/courses/417/notes/lecture1.html ) ペーパーを読んでいたところです。ただし、O(log n) はノード数をまったく参照していないため、結果の意味がわかりません。これはどのように証明できますか？ただし、最初のステップと、反復がどのように単純化されるかは理解しています。しかし、4番目のステップの後、私は彼が何をしているのか正確に理解できていません（漠然と想像することはできますが）. 最後の数行が何を証明しているか、パート 1 の最後で彼がどのように式を単純化しているか、誰か説明してくれませんか?

ありがとう

4

1 に答える 1

1

O(logn) はノードを参照します。「n」はノード数を表します。後続の各レベルのノード数が 2 倍になることを認識することで、直感的に考えることができます。これは AVL ツリーであるため、ノードを次のレベルにプッシュする前に、前のレベルがいっぱいになる必要があります。これは、各レイヤーがノードの数を 2 倍にするため、ログに記録するツリーの高さを制限します。つまり、ノードの数はノード = 2^高さ - 1 として記述できます。高さと丸さを解くと、logn が得られます。

于 2014-05-16T13:30:05.997 に答える