1. 序章
このチュートリアルでは、完全な-Aryツリー内のノードの総数を計算する問題について説明します。 そのために、最初に反復的で再帰的なアプローチを検討し、次に純粋に数学的アプローチを検討します。
2. フル-AryTree
完全な-aryツリーに慣れることから始めましょう:
ここで、リーフノードを除くすべてのノードに子(この場合は)があることがわかります。
さらに、この問題では、葉の総数がわかっている場合に、ツリー内のノードの総数を計算するように求められます()。 この場合、葉の総数がであるのに対し、ノードの総数はであることが数えられます。
すべての正の整数について、葉の総数を知るだけで、ノードの総数を見つけることができます。
3. 反復ソリューション
ノードの総数は、基本的に、ツリーの各レベルでのノードの数の合計です。 これを繰り返し行う方法を見てみましょう。
3.1. アルゴリズムフロー
反復アプローチでは、葉のノードから開始して、木の根に向かって上向きに歩きます。 フルアリーツリーの各ノードには子があるため、レベルのノードの総数はその上のレベルのの倍になります。
したがって、各反復で、1レベル上に移動し、現在のレベルに存在するノードの数だけ、これまでのノードの総数をインクリメントします。
誤った入力値から保護するために、検証チェックを含め、無効な入力の場合にエラーで終了することができます。
3.2. 擬似コード
反復アプローチの擬似コード実装を見てみましょう。
まず、ノードの総数()と現在のレベルのノードの数()をリーフの数として初期化します。 各反復で、は係数で減少し、現在のレベルのノードの数で増加します。
最後に、は、現在のレベルのノードの数がの値に達したときに停止します。これは、ツリーのルートに到達したことを意味します。
4. 再帰的ソリューション
同じアルゴリズムのアイデアは、再帰的アプローチを使用して実装できます。 ループを再帰に置き換える方法を見てみましょう。
4.1. 擬似コード
特定のレベルまでのノードの総数をカウントするプロセスは、基本的に、そのレベルのノードをその上のレベルまでのノードの総数に追加するのと同じです:
したがって、この再帰式を念頭に置いて、再帰スタイルの実装の擬似コードを見てみましょう。
関数は、関数によってラップされるコア再帰部分であることがわかります。 この抽象化には2つの利点があります。
- 事前検証は、ラッパー関数内で1回実行できます。
- クライアントは、内部実装の詳細を漏らさずに同じインターフェイスを取得します
5. ダイレクトフォーミュラアプローチ
反復的および再帰的アプローチを理解したので、コア機能をすぐに利用できる数学関数に委任するもう1つのアプローチを学びましょう。
5.1. 高さの事前計算
ツリーの一番上から始めて、各レベルのノードの総数を書き留めると、等比数列の系列が得られます。
ソリューションは、等比数列の合計に要約されます。 したがって、ヘルパー関数として対数関数と指数関数を利用できます。
コア機能を数学関数に委任することにより、このアプローチはより読みやすくシンプルに見えます。
5.2. 直接計算
高さ計算の中間ステップを削除することで、ノードの総数を計算する式をさらに簡略化できます。 数学的に見てみましょう:
最後に、次の式を使用するアルゴリズムの簡略化されたバージョンに到達しましょう。
6. 複雑さの分析
ツリーの高さを直接または間接的に使用するすべてのアプローチの時間計算量はです。 これは、完全なツリーの高さがツリーの順序に対数的に比例するためです。
ただし、最後のアプローチでは、中間計算を行う必要はありません。 算術論理演算装置(ALU)がハードウェアレベルでの除算をサポートすると仮定すると、アルゴリズムの時間計算量はになります。 そうしないと、最後のアルゴリズムでさえ時間計算量がになります。
7. 結論
このチュートリアルでは、完全な-aryツリーのノードの総数を計算するためのさまざまなアプローチについて説明しました。 反復的かつ再帰的なアプローチを使用してゼロから開始し、直接数式ベースのアプローチで終了しました。