ツリートラバーサル

コンピュータサイエンスにおいて、ツリートラバーサル（ツリー検索やツリーウォーキングとも呼ばれる）はグラフトラバーサルの一種で、ツリーデータ構造内の各ノードを 1 回だけ訪問（取得、更新、削除など）するプロセスを指します。このようなトラバーサルは、ノードを訪問する順序によって分類されます。以下のアルゴリズムはバイナリツリーについて説明していますが、他のツリーにも一般化できます。

リンクリスト、1次元配列、その他の線形データ構造は標準的には線形順序で走査されますが、ツリーは複数の方法で走査できます。ツリーは深さ優先または幅優先の順序で走査できます。深さ優先順序で走査する一般的な方法は、インオーダー、プレオーダー、ポストオーダーの3つです。^{[1]これらの基本的な走査以外にも、}反復深化深さ優先探索などの深さ制限のある検索など、さまざまなより複雑なスキームやハイブリッドスキームが可能です。後者は、幅優先探索と同様に、無限ツリーを走査するためにも使用できます。以下を参照してください。

ツリーのトラバースには、何らかの方法ですべてのノードを反復処理することが含まれます。特定のノードから複数の次のノードが存在する可能性があるため (線形データ構造ではない)、逐次計算 (並列ではない) を想定すると、一部のノードを延期する必要があります。つまり、後でアクセスできるように何らかの方法で保存する必要があります。これは、多くの場合、スタック( LIFO) またはキュー(FIFO) を介して行われます。ツリーは自己参照型 (再帰的に定義される) データ構造であるため、トラバースは再帰、またはより微妙に言えばコア再帰によって自然かつ明確な方法で定義できます。これらの場合、延期されたノードはコール スタックに暗黙的に保存されます。

深さ優先探索はスタックを介して簡単に実装でき、再帰的（コールスタック経由）にも実装できる。一方、幅優先探索はキューを介して簡単に実装でき、コアカーシブにも実装できる。^{[2] : 45−61}

深さ優先探索(DFS)では、次の兄弟に進む前に、探索ツリーが可能な限り深くなります。

深さ優先探索で二分木を走査するには、各ノードで次の操作を実行します。^{[3] [4]}

1. 現在のノードが空の場合は戻ります。
2. 次の3つの操作を特定の順序で実行します。^[5]

   N: 現在のノードにアクセスします。

   L: 現在のノードの左のサブツリーを再帰的に走査します。

   R: 現在のノードの右サブツリーを再帰的に走査します。

トラバーサルのトレースはツリーのシーケンシャル化と呼ばれます。トラバーサル トレースは、訪問した各ノードのリストです。事前順序、イン順序、または事後順序に従ったシーケンシャル化のいずれも、基になるツリーを一意に記述することはできません。異なる要素を持つツリーが与えられた場合、事前順序または事後順序とイン順序の組み合わせのいずれかで、ツリーを一意に記述できます。ただし、事後順序と事前順序の組み合わせでは、ツリー構造に多少の曖昧さが残ります。^[6]

ノードに対するトラバーサルの位置 (図では赤、緑、青) に応じて、ノードの訪問が行われる方法は 3 つあります。1 つの色を選択すると、以下に説明するように、ノードの訪問が 1 回だけ決定されます。3 つの色すべてを訪問すると、同じノードが 3 回訪問され、「全順序」の順序付けが行われます。

F - B - A - A - A - B - D - C - C - C - D - E - E - E - D - B - F - G - G -  I - H - H - H -  I -  I - G - F

1. 現在のノード（図では赤い位置）にアクセスします。
2. 現在のノードの左のサブツリーを再帰的に走査します。
3. 現在のノードの右サブツリーを再帰的に走査します。

事前順序トラバーサルは、親ノードが子ノードよりも先に処理されるため、 トポロジ的にソートされたトラバーサルです。

1. 現在のノードの左のサブツリーを再帰的に走査します。
2. 現在のノードの右サブツリーを再帰的に走査します。
3. 現在のノード（図では青い位置）にアクセスします。

後順序トラバーサルは、バイナリ式ツリーの後置式を取得するのに役立ちます。

1. 現在のノードの左のサブツリーを再帰的に走査します。
2. 現在のノード（図では緑の位置）にアクセスします。
3. 現在のノードの右サブツリーを再帰的に走査します。

各ノードのキーが左のサブツリーのすべてのキーより大きく、右のサブツリーのすべてのキーより小さくなるように順序付けられた二分探索木では、順序探索は昇順でソートされたキーを取得します。^[7]

1. 現在のノードにアクセスします。
2. 現在のノードの右サブツリーを再帰的に走査します。
3. 現在のノードの左のサブツリーを再帰的に走査します。

1. 現在のノードの右サブツリーを再帰的に走査します。
2. 現在のノードの左のサブツリーを再帰的に走査します。
3. 現在のノードにアクセスします。

1. 現在のノードの右サブツリーを再帰的に走査します。
2. 現在のノードにアクセスします。
3. 現在のノードの左のサブツリーを再帰的に走査します。

各ノードのキーが左のサブツリーのすべてのキーより大きく、右のサブツリーのすべてのキーより小さくなるように順序付けられたバイナリ検索ツリーでは、逆順トラバーサルによってキーが降順でソートされて取得されます。

深さ優先探索を使用して任意のツリー (必ずしもバイナリ ツリーではない) をトラバースするには、各ノードで次の操作を実行します。

1. 現在のノードが空の場合は戻ります。
2. 事前順序トラバーサルのために現在のノードにアクセスします。
3. 1 から現在のノードのサブツリーの数 - 1 までの各iに対して、または逆方向のトラバーサルの場合は後者から前者まで、次の操作を実行します。
   1. 現在のノードのi番目のサブツリーを再帰的に走査します。
   2. 順序どおりにトラバーサルするために現在のノードにアクセスします。
4. 現在のノードの最後のサブツリーを再帰的に走査します。
5. 後順トラバーサルのために現在のノードにアクセスします。

問題によっては、事前順序、事後順序、特にサブツリーの数 − 1 の順序操作のいずれかがオプションになる場合があります。また、実際には、事前順序、事後順序、順序操作のいずれか 1 つ以上が必要になる場合があります。たとえば、3 値ツリーに挿入する場合、項目を比較して事前順序操作を実行します。ツリーのバランスを再調整するために、後で事後順序操作が必要になる場合があります。

幅優先探索(BFS) またはレベル順探索では、次の深さに進む前に探索ツリーが可能な限り広げられます。

深さ優先探索でも幅優先探索でもないツリー探索アルゴリズムもあります。そのようなアルゴリズムの 1 つがモンテカルロ木探索です。これは、探索空間のランダム サンプリングに基づいて探索ツリーを拡張し、最も有望な動きを分析することに重点を置いています。

事前順序トラバーサルを使用すると、式ツリーからプレフィックス式 (ポーランド記法)を作成できます。つまり、式ツリーを事前順序でトラバースします。たとえば、示されている算術式を事前順序でトラバースすると、"+ * A − B C + D E " が生成されます。プレフィックス表記では、各演算子のオペランド数が固定されている限り、括弧は必要ありません。事前順序トラバーサルは、ツリーのコピーを作成する場合にも使用されます。

ポストオーダー トラバーサルは、二分木のポストフィックス表現 (逆ポーランド記法) を生成できます。 示された算術式をポストオーダーでトラバースすると、「 A B C − * D E + + 」が生成されます。後者は簡単にマシン コードに変換でき、スタック マシンで式を評価できます。ポストオーダー トラバーサルは、ツリーを削除する場合にも使用されます。各ノードは、その子ノードを解放した後に解放されます。

インオーダートラバーサルは、バイナリ検索ツリーを設定したコンパレータに従って、基になるセットから順番に値を返すため、 バイナリ検索ツリーで非常によく使用されます。

ツリーが配列（最初のインデックスが0）で表現されている場合、次の要素のインデックスを計算することが可能である：^{[8] [説明が必要]}

手順bubbleUp(配列、i、leaf)
    く ← 1
    私 ← (私 - 1)/2
    一方、 (リーフ + 1) % (k * 2) ≠ k
        私 ← (私 - 1)/2
        k ← 2 * k
    戻る​

手順preorder(配列)
    私 ← 0
    i ≠ array.size の場合
        訪問(配列[i])
        i = サイズ - 1 の場合
            i ← サイズ
        そうでない場合、 i < size/2
            私 ← 私 * 2 + 1
        それ以外
            葉 ← i - サイズ/2
            親 ← bubble_up(配列、i、リーフ)
            私 ← 親 * 2 + 2

開始する は、標準の検索関数を使用してnodeバイナリ検索ツリーで見つかった可能性があります。ここでは、親ポインターなしの実装で示されています。つまり、祖先ポインターを保持するために を使用しています。 bststack

手順search(bst, キー)
    // (ノード、スタック) を返します
    ノード ← bst.root
    スタック ←空のスタック
    、ノード ≠ null
        スタック.push(ノード)
        キー = node.key
            の場合、 (node, stack)
        を返します。キー < node.keyの場合、 (node, stack) を返します。
            ノード ← ノード.左    
        それ以外
            ノード ← ノード.right
    戻り値( null、空のスタック)

関数inorderNext ^{[2] : 60は}、の順序どおりの近傍node、順序どおりの後続ノード（ の場合dir=1）または順序どおりの先行ノード（の場合dir=0）、および更新された を返すstack。これにより、バイナリ検索木を順番に順序どおりに走査し、指定された方向でdirさらに検索することができる。

手順inorderNext(ノード、ディレクトリ、スタック)
    新しいノード ← node.child[dir]
    newnode ≠ null
        の場合
            ノード ← 新しいノード
            スタック.push(ノード)
            新しいノード ← node.child[1-dir]
        newnode = null に
        なるまで(node, stack)を返す
    // ノードには dir-child がありません:
    
        stack.isEmpty()
            の場合は、 ( null、空のスタック)を返します。
        古いノード ← ノード
        node ← stack.pop() // oldnode の親
    oldnode ≠ node.child[dir]になるまで
    // 現在、oldnode = node.child[1-dir]、
    // つまり、ノード = 元のノードの祖先（および先行ノード/後続ノード）
    戻り値(ノード、スタック)

この関数はキーを使用しないことに注意してください。つまり、シーケンシャル構造はバイナリ検索ツリーのエッジによって完全に記録されます。方向変更のないトラバーサルの場合、(償却)平均複雑度は、完全なトラバーサルがサイズの BST に対してエッジアップに 1 ステップ、エッジダウンに 1 ステップかかるためです。最悪の場合の複雑度は、ツリーの高さと 同じです。${\displaystyle {\mathcal {O}}(1),}$${\displaystyle 2n-2}$${\displaystyle n,}$${\displaystyle {\mathcal {O}}(h)}$${\displaystyle h}$

上記のすべての実装では、ツリーの高さに比例したスタック スペースが必要です。これは、再帰の場合は呼び出しスタック、反復の場合は親 (祖先) スタックです。バランスの悪いツリーでは、このサイズがかなり大きくなる可能性があります。反復実装では、各ノードで親ポインターを維持するか、ツリーをスレッド化することで (次のセクション)、スタック要件を排除できます。

バイナリ ツリーは、すべての左側の子ポインタ (それ以外の場合は null) がノードの順序どおりの先行ノード (存在する場合) を指すようにし、すべての右側の子ポインタ (それ以外の場合は null) がノードの順序どおりの後続ノード (存在する場合) を指すようにすることでスレッド化されます。

利点:

1. コールスタックを使用し、メモリと時間を消費する再帰を回避します。
2. ノードは親の記録を保持します。

デメリット:

1. ツリーはより複雑です。
2. 一度に実行できる走査は 1 つだけです。
3. 両方の子ノードが存在せず、両方のノード値が祖先ノードを指している場合、エラーが発生しやすくなります。

モリス探索はスレッドを使った順序探索の実装である: ^[9]

1. 順序どおりの後継へのリンクを作成します。
2. これらのリンクを使用してデータを印刷します。
3. 変更を元に戻して元のツリーを復元します。

また、以下にリストされているのは、単純なキューベースのレベル順トラバーサルの疑似コードです。このコードでは、特定の深さにあるノードの最大数に比例したスペースが必要になります。これは、ノードの総数の半分になることもあります。このタイプのトラバーサルでは、反復深化深さ優先探索を使用して、よりスペース効率の高いアプローチを実装できます。

手順レベル順序(ノード)
    キュー ←空のキュー
    キュー.エンキュー(ノード)
     queue.isEmpty()ではない場合
        ノード ← queue.dequeue()
        訪問(ノード)
        node.left ≠ nullの場合
            キューにキューを追加します(ノードの左)
        node.right ≠ nullの場合
            キューにキューを追加します。

ツリーが配列（最初のインデックスが 0）で表されている場合は、すべての要素を反復処理するだけで十分です。

プロシージャlevelorder(array)、
     iは0からarray.sizeまで
        訪問(配列[i])

走査は通常、有限個のノード（したがって有限の深さと有限の分岐係数）を持つツリーに対して行われますが、無限ツリーに対しても行うことができます。これは関数型プログラミング（特に遅延評価）において特に興味深いことです。無限データ構造は（厳密に）評価されない（無限の時間がかかる）にもかかわらず、簡単に定義して操作できることが多いためです。チェスや囲碁のゲームツリーなど、一部の有限ツリーは明示的に表現するには大きすぎるため、それらを無限であるかのように分析すると便利です。

トラバーサルの基本的な要件は、最終的にすべてのノードを訪問することです。無限ツリーの場合、単純なアルゴリズムではこの要件を満たせないことがよくあります。たとえば、無限の深さのバイナリ ツリーがある場合、深さ優先探索ではツリーの片側 (慣例により左側) を下り、残りの部分を訪問することはありません。また、順序順または後順序のトラバーサルでは、葉に到達していないため (実際には決して到達しない)、どのノードも訪問しません。対照的に、幅優先 (レベル順) のトラバーサルでは、無限の深さのバイナリ ツリーを問題なくトラバーサルし、分岐係数が制限されているツリーであればトラバーサルします。

一方、深さ 2 のツリーでは、ルートには無限の子があり、これらの子にはそれぞれ 2 つの子があります。この場合、深さ優先探索ではすべてのノードが訪問されます。孫 (1 つのノードの子の子) をすべて調べ尽くしたら、次のノードに移動します (後順ではないと仮定すると、その場合はルートに到達しません)。対照的に、幅優先探索では、まず子をすべて調べ尽くそうとするため、孫に到達することはありません。

実行時間のより洗練された分析は、無限順序数によって行うことができます。たとえば、上記の深さ 2 のツリーの幅優先探索では、 ω ·2 ステップかかります。最初のレベルに ω がかかり、次に 2 番目のレベルに別の ω が掛かります。

したがって、単純な深さ優先または幅優先の検索では、すべての無限ツリーを走査することはできず、非常に大きなツリーでは効率的ではありません。ただし、ハイブリッド メソッドでは、基本的に対角引数(「対角」は垂直と水平の組み合わせであり、深さと幅の組み合わせに対応します) を介して、任意の (可算) 無限ツリーを走査できます。

具体的には、無限に分岐する無限の深さの木が与えられた場合、ルート ()、ルートの子 (1)、(2)、...、孫 (1, 1)、(1, 2)、...、(2, 1)、(2, 2)、...、というようにラベルを付けます。したがって、ノードは、正の数の有限 (場合によっては空) シーケンスと1 対 1で対応しています。これらのシーケンスは可算であり、最初にエントリの合計によって順序付けされ、次に指定された合計内で辞書式順序で配置できます (指定された値の合計になるシーケンスは有限個だけなので、すべてのエントリに到達します。正式には、指定された自然数の構成は有限個あり、具体的にはn ≥ 1の構成は2 ^{n −1}個あります)。これにより、トラバーサルが実現します。明示的には、

1. （）
2. （１）
3. （１、１） （２）
4. (1, 1, 1) (1, 2) (2, 1) (3)
5. (1、1、1、1) (1、1、2) (1、2、1) (1、3) (2、1、1) (2、2) (3、1) (4)

等

これは、無限の深さの二分木をこの木にマッピングし、幅優先探索を適用すると解釈できます。つまり、親ノードを 2 番目以降の子に接続する「下」のエッジを、最初の子から 2 番目の子、2 番目の子から 3 番目の子などへの「右」のエッジに置き換えます。したがって、各ステップで、下に行く (末尾に (, 1) を追加する) か、右に行く (最後の番号に 1 を追加する) ことができます (ルートは例外で、ルートは余分なので下に行くことしかできません)。これは、無限二分木と上記の番号付けとの対応を示しています。エントリの合計 (マイナス 1) はルートからの距離に対応し、無限二分木の深さn − 1にある 2 ^{n −1}個のノードと一致します(2 は二分に対応します)。

• Dale, Nell. Lilly, Susan D. 「Pascal Plus データ構造」 DC Heath and Company. レキシントン、マサチューセッツ州。1995 年。第 4 版。
• Drozdek, Adam. 「C++ のデータ構造とアルゴリズム」。Brook/Cole。パシフィック グローブ、カリフォルニア州。2001 年。第 2 版。
• 「ツリー横断」(math.northwestern.edu)

• PHP でのトラバーサル例を使用してデータベースに階層データを保存する
• MySQL での階層データの管理
• MySQL でのグラフの操作
• Rosetta Codeでさまざまなプログラミング言語に実装されたツリー トラバーサルを参照してください。
• 再帰なしのツリー走査
• ツリートラバーサルアルゴリズム
• バイナリツリートラバーサル
• データ構造におけるツリートラバーサル