binary-search-tree - 二分探索木の密度？

Question

二分探索木を扱う宿題に取り組んでいますが、よくわからない質問に出くわしました。質問は、密度が二分木の検索にかかる時間にどのように影響するかを尋ねます。二分探索木とbig-O表記法は理解していますが、密度についてはこれまで扱ったことがありません。

Answer 1

二分探索木の密度は、レベルに累積されたノードの数として定義できます。完全な二分木は最も密度が高くなります。したがって、質問は基本的に、各レベルのノードの数がツリー内の検索時間にどのように影響するかについて尋ねます。それが明確でない場合はお知らせください。