data-structures - ノードの数がわかっている場合、二分木の最小の高さを見つける方法は？

Question

二分木のノード数をnとすると、二分木の最小の高さを求める一般的な関数用語は何でしょうか。

n = floor（log2（n））+1になると思います。しかし、私は間違っていると思います。

Answer 1

この概念を覚えておいてください

高さを最小にするには、各レベル、収容できるノードの最大数を指定する必要があります

したがって、高さhのツリーの場合、ツリーが収容できるノードの最大数は合計= 2 ^（h + 1）-1であるため、 n <= 2 ^（h + 1）-1
を解くと次のようになります。
h> = log（n + 1）base2 -1
ログの床または天井を決定するために、次のように考えます。

私のlognが3.56に来る場合、それは高さ3まで各レベルが完全に消費されるまで、最後のレベルが完全に満たされていないことを意味します。高さの定義では、根から葉までの最長のパスであると示されているため、高さにはその最後のレベルも含まれます。

したがって、床よりも天井が優先されます。このアプローチでは、m-aryツリーも見つけることができます。

Answer 2

二分木の高さから：

N個の要素がある場合、二分木の最小の高さはlog2（N）+1になります。

Answer 3

誘導によってこれを証明してみてください。二分木のタイプは帰納的であり、2つのコンストラクターがあります。

• Leaf(v)
• Node(Tree,Tree)

これで、構造的帰納法を使用して、二分木の最小の高さを表示できます。最小の高さを取得するには、完全な二分木があります。これは二分木であり、どのサブツリーでも、子の高さは同じです。（これは基本的に、木を引き出すと「穴」が表示されないことを意味します。）したがって、このタイプの木があると仮定して、その高さがであることを証明しfloor(log_2(n)) + 1ます。これを少し簡単に証明するには、向きを変えて次のように言います。たとえば、高さのある木があるとすると、最大でノードfloor(log_2(n))+1があることを証明します。nこれは、コンストラクターに対する構造的帰納法によって証明できます。