1. 序章


このチュートリアルでは、フラットリストをツリーまたはフォレストに変換する方法を示します。


2. 問題文








入力時に、親子階層を表すペアのリストがあります。それぞれは、がノードのIDであり、がその親のIDである構造です。 基本的に、 ペアは、階層内のノード間の有向エッジを示します。


さらに、ペアは任意の順序で表示されます。 たとえば、ノード2は、このツリーのノード4の親です。


いずれにせよ、ペアはリストの前に来る可能性があります。


さらに、階層内に複数のツリーが存在する可能性があります。入力リストに親が子として表示されないノードは、独立したツリーのルートを表します。 私たちの目標は、リストをツリーのセット、つまり、複数ある場合はフォレストに変換し、それらのルートを特定することです。


IDは、整数、文字列データ、タプルなど、任意のタイプにすることができます。 最後に、一般的なケースを検討し、すべてのデータ型で機能するソリューションを紹介します。


3. 解決


簡単な方法は、ペアを1つずつ処理し、これまでに構築されたフォレストで親のノードを見つけて、それに子をアタッチすることです。 次に、親がまだ存在しない場合は、対応するノードを作成します。 しかし、それは部分的な解決策にすぎません。 ノードを適切なツリーに編成することは、それらのルートを特定しなければあまり意味がありません。


ルーツを見つけるために、次の観察を使用します。 IDが子として表示される場合、潜在的なルートとして除外できます。 したがって、デフォルトですべてのノードを候補ルートと見なし、入力リストでその親が見つかった場合に候補を除外すると、リスト全体の処理時に実際のルートのみが残ります。




3.1. 正当性の証明


アルゴリズムの正しさを証明しましょう。 ループ不変条件は、既知の親を持たないすべてのノードを含むことです。このようなノードを候補ルートと呼びます。


空集合に初期化するため、ループの前では不変条件は自明に真です。


ここで、不変量が-番目の反復の前に成り立つと仮定しましょう。 次の冒頭でもそうですか？ いくつかのケースを分析します。


    

  • が候補ルートの場合、それを除外してから削除します。
    • 

  • が候補ルートでない場合は、に追加されません。
    • 

  • が新しく作成されたノードの場合、既知の親がないため、に追加します。
    • 

  • が新しく作成されたノードでない場合は、以前に別のノードの子として追加されたことがわかっているため、に含めません。
    • 



そのため、ルート候補である場合にのみ新しいノードに追加し、親を持つことが判明したノードを削除します。 したがって、不変条件は次のループの前に保持されます。 アルゴリズムの最後に、実際のルートのみが含まれ、他のノードは含まれません。


3.2. 複雑


時間の下限複雑さは、ペアを処理する必要があるためです。ここで、は入力リストの長さ、つまりフォレスト内のエッジの数です。 各ノードには正確に1つの親があるため、ノードの数も概算します。 より正確には、ルートには見た目のエッジがなく、リストに表示されないため、ノードの数とツリーの数の違いです。


上限は、実装方法によって異なります。 迅速なアクセスのためにペアを記憶するために補助データ構造を使用しない場合、メモリの複雑さはになりますが、時間の複雑さは2次式になります。 これは、最悪の場合、フォレスト全体をトラバースして、指定されたIDを持つノードを見つけるためです。 したがって、リストから-番目のペアを読み取るときにルックアップを実行します。最悪の場合の時間計算量は次のようになります。


      


3.3. ハッシュテーブルによるバリエーション


ハッシュテーブルをキーとしてノードIDを使用し、値としてノードへのポインターを使用する場合、の平均ケース時間計算量はになります。 したがって、平均的な場合、アルゴリズム全体は線形になります。


      


疑似コードのすべては同じままですが、ハッシュテーブルを維持し、それを次の場所で使用する点が異なります。




さらに、ハッシュテーブルの作成時にキーのセットが変更されないため、完全なハッシュを実現できます。 これは、最悪の場合でも検索が行われることを意味します。 その結果、ツリーを構築するためのアルゴリズムは線形になります。


4. 連結成分としての樹木


この問題に取り組む別の方法があります。 入力配列は、（おそらく切断された）グラフのエッジのリストと見なすことができます。 すべてのエッジを読み取ると、任意のノードから深さ優先探索を開始し、同じツリーに属する他のすべてのノードにアクセスします。 親がないものは、ツリーのルートを表します。 すべてのノードに到達するまでこのプロセスを繰り返し、ツリーを連結成分として識別し、それらのルートを収集します。 キャッチは、ルート以外の頂点からトラバーサルを開始する場合、開始ノードの祖先にアクセスするために両方向のエッジを維持する必要があることです。


4.1. 擬似コード


擬似コードは次のとおりです。




 深さ優先探索（DFS）に基づいています。




4.2. 複雑


リストを読み取ってノードを保存するのはです。 深さ優先探索は、どのノードにも2回アクセスしません。 したがって、アルゴリズム全体の複雑さは線形である可能性があります。 ただし、実装方法によって異なります。 特に、隣接行列または隣接リストでエッジを表すかどうかについて。


前者の場合、属性はブール行です（IDを自然数にマップする必要があります）。 ノードごとに、その子ノードを見つけるために行全体を通過する必要があります。 アルゴリズムは2次の複雑さです。 一方、隣接リストを使用する場合は、各ノードにアクセスして、各エッジを1回通過します。 ノードのあるツリーにはエッジが含まれているため、への-番目の呼び出しには時間がかかります。ここで、は-番目のツリーのノードの数です。 木々を合計すると、が得られます。


4.3. 入力の縮退


深さ優先アプローチは、エッジがない縮退した場合でも処理できます。 ただし、問題の定義方法から、そのような入力は不可能であることがわかります。 その理由は、空のリストに対応するためです。この場合、処理に使用できるデータがなく、アルゴリズムを実行できません。


5. 結論


この記事では、フォームのペア（子ID、親ID）を含むフラットリストからツリーのフォレストを構築するための2つのアルゴリズムを紹介しました。 1つのアルゴリズムは、この問題のために特別に考案したアドホックソリューションです。 もう1つは、深さ優先探索を介して連結成分を識別する方法を採用したものです。 適切なデータ構造を使用すれば、どちらも線形時間で実行できます。