リーフカウントを使用して、完全なK-Aryツリー内のノードの総数を見つける

1. 序章

このチュートリアルでは、完全な-Aryツリー内のノードの総数を計算する問題について説明します。そのために、最初に反復的で再帰的なアプローチを検討し、次に純粋に数学的アプローチを検討します。

完全な-aryツリーに慣れることから始めましょう：

ここで、リーフノードを除くすべてのノードに子（この場合は）があることがわかります。

さらに、この問題では、葉の総数がわかっている場合に、ツリー内のノードの総数を計算するように求められます（）。この場合、葉の総数がであるのに対し、ノードの総数はであることが数えられます。

すべての正の整数について、葉の総数を知るだけで、ノードの総数を見つけることができます。

ノードの総数は、基本的に、ツリーの各レベルでのノードの数の合計です。これを繰り返し行う方法を見てみましょう。

反復アプローチでは、葉のノードから開始して、木の根に向かって上向きに歩きます。フルアリーツリーの各ノードには子があるため、レベルのノードの総数はその上のレベルのの倍になります。

したがって、各反復で、1レベル上に移動し、現在のレベルに存在するノードの数だけ、これまでのノードの総数をインクリメントします。

誤った入力値から保護するために、検証チェックを含め、無効な入力の場合にエラーで終了することができます。

反復アプローチの擬似コード実装を見てみましょう。

まず、ノードの総数（）と現在のレベルのノードの数（）をリーフの数として初期化します。各反復で、は係数で減少し、現在のレベルのノードの数で増加します。

最後に、は、現在のレベルのノードの数がの値に達したときに停止します。これは、ツリーのルートに到達したことを意味します。

同じアルゴリズムのアイデアは、再帰的アプローチを使用して実装できます。ループを再帰に置き換える方法を見てみましょう。

特定のレベルまでのノードの総数をカウントするプロセスは、基本的に、そのレベルのノードをその上のレベルまでのノードの総数に追加するのと同じです：

したがって、この再帰式を念頭に置いて、再帰スタイルの実装の擬似コードを見てみましょう。

関数は、関数によってラップされるコア再帰部分であることがわかります。この抽象化には2つの利点があります。

反復的および再帰的アプローチを理解したので、コア機能をすぐに利用できる数学関数に委任するもう1つのアプローチを学びましょう。

ツリーの一番上から始めて、各レベルのノードの総数を書き留めると、等比数列の系列が得られます。

ソリューションは、等比数列の合計に要約されます。したがって、ヘルパー関数として対数関数と指数関数を利用できます。

コア機能を数学関数に委任することにより、このアプローチはより読みやすくシンプルに見えます。

高さ計算の中間ステップを削除することで、ノードの総数を計算する式をさらに簡略化できます。数学的に見てみましょう：

最後に、次の式を使用するアルゴリズムの簡略化されたバージョンに到達しましょう。

ツリーの高さを直接または間接的に使用するすべてのアプローチの時間計算量はです。これは、完全なツリーの高さがツリーの順序に対数的に比例するためです。

ただし、最後のアプローチでは、中間計算を行う必要はありません。 算術論理演算装置（ALU）がハードウェアレベルでの除算をサポートすると仮定すると、アルゴリズムの時間計算量はになります。そうしないと、最後のアルゴリズムでさえ時間計算量がになります。

このチュートリアルでは、完全な-aryツリーのノードの総数を計算するためのさまざまなアプローチについて説明しました。 反復的かつ再帰的なアプローチを使用してゼロから開始し、直接数式ベースのアプローチで終了しました。