algorithm - 二分木の密度

Question

特定のバイナリ ツリーの密度を調べるにはどうすればよいですか? このインタビューの質問に出くわしましたが、密度が何を意味するのかわかりません! どんな助けでも大歓迎です。

Answer 1

密な二分木は完全に近い (に2^(h + 1) - 1 nodes)近いh.h

密度の簡単な尺度は次のとおりです。

(n - h)/(2^(h + 1) - h - 1)

私はその式を作ったばかりなので、インタビューの回答のニーズに合っているかどうかはわかりませんが、退化したツリーの場合は 0、完全なツリーの場合は 1 になります。密集した木では 1 に近い数値が得られ、まばらな木では 0 に近い数値が得られます。

ウィキペディアには、二分木に関する多くの情報があります。

Answer 2

二分木では、各レベルのノード数は値の範囲内にあります。レベル0には、ルートという1つのノードがあります。レベル1では、1つまたは2つのノードが存在する可能性があります。任意のレベルkで、ノードの数は1〜2kの範囲です。レベルごとのノードの数は、ツリーの密度に影響します。直感的には、密度は木の高さに対する木のサイズ（ノードの数）の尺度です。