1. 序章

ツリーの高さと深さは、複雑さの分析や多数のアルゴリズムで考慮する重要な属性です。 このチュートリアルでは、これら2つの属性の違いを示します。

2. 問題の説明

ツリー内のノードごとに、heightとdepthの2つの機能を定義できます。 ノードの高さは、最も遠いリーフノードまでのエッジの数です。 一方、ノードの深さは、ルートに戻るエッジの数です。 したがって、ルートの深さは常にですが、リーフノードの高さは常にです。 そして、木全体を見ると、その深さと高さは両方とも根の高さです。

高さ対。 深さ

3. フローチャート

任意のノードの高さまたは深さの計算は、幅優先探索（BFS）を使用して実行できます。 ただし、一般的なケースは今後の投稿のために残しておきます。 簡単に言えば、ノードの高さをその子の最大の高さとして設定することで、再帰的に高さを見つけることができます。

ノードの高さを見つける

深さについては、ツリー内の各ノードがその親ノードを格納していると仮定すると、ターゲットノードからルートまでトラバースして、途中でエッジを数えることができます。

ノードの深さを見つける

4. 擬似コード

これら2つを並べて見てみましょう。 前に述べたように、高さで、私たちは下向きに、そして深さで、上向きに横断します：

5. 複雑

それらの複雑さを比較することもできます。 高さを見つけるためにBFSを使用したため、複雑さはです。ここで、nはツリー内のノードの数です。 深度アルゴリズムに関しては、ターゲットノードからルートまでのエッジを反復処理します。 したがって、ノードの深さを見つけるための時間計算量は、であり、最悪の場合はであることが簡単にわかります。 また、スペースの複雑さは、高さと深さを見つけるためのです。 高さを見つける場合は、BFSキューにメモリを割り当てる必要があります（再帰的ソリューションで自動的に割り当てられます）。 そして、深さを見つける場合には、親のためにスペースを割り当てる必要があります。

6. 結論

この短い記事では、木の高さと深さの違いを示しました。 これを行うために、それらを計算するためのアプローチを検討し、それらの時空の複雑さを比較しました。