algorithm - 2-3-4 ツリーの上限と下限

Question

n 個のノードを持つ 2-3-4 ツリーの高さの上限と下限を見つけます。率直に言って、私はどのように始めればよいかわかりません。これには公式がありますか？助けていただければ幸いです。

Answer 1

最悪の場合、すべてのノードには正確に2人の息子がいるため、次のことを解決する必要があります。

2^0 + 2^1 + 2^2 + ... + 2^h >= n

h条件を満たす最小値を見つけると、「最悪の場合」の2-3-4木の高さがわかります。

最適なケースの高さを取得するには、ノードごとに4人の息子でこのプロセスを繰り返します。