ツリートラバーサル

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

種類

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

ツリートラバーサルのためのデータ構造

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

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

二分木の深さ優先探索（点線パス）:
  • 事前順序（赤い●の位置で訪問されたノード）：
        F、B、A、D、C、E、G、I、H。
  • 順序通り（緑の●の位置で訪問されたノード）：
        A、B、C、D、E、F、G、H、I。
  • 事後順序（青い●の位置で訪問されたノード）：
        A、C、E、D、B、H、I、G、F。

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

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

  1. 現在のノードが空の場合は戻ります。
  2. 次の3つの操作を特定の順序で実行します。[5]
    N: 現在のノードにアクセスします。
    L: 現在のノードの左のサブツリーを再帰的に走査します。
    R: 現在のノードの右サブツリーを再帰的に走査します。

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

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

ファ-バ-ア-ア-ア-バ-ニ-ク-ク-ド-イ-イ-ド-バ-ファ-ソ-ギ-イ- ハ-ハ-イ-イ- ソ- ファ​​​​​​

予約注文、NLR

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

事前順序トラバーサルは、親ノードがその子ノードのいずれかが処理される前に処理されるため、位相的にソートされたトラバーサルです。

ポストオーダー、LRN

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

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

順序通り、LNR

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

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

逆予約注文、NRL

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

逆ポストオーダー、RLN

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

逆順、RNL

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

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

任意のツリー

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

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

問題によっては、前順序、後順序、そして特に部分木の数 − 1 の順序操作のいずれかがオプションとなる場合があります。また、実際には、前順序、後順序、順序操作のいずれか1つ以上が必要となる場合もあります。例えば、三分木にデータを挿入する場合、項目を比較することで前順序操作が実行されます。その後、木のバランスを再調整するために後順序操作が必要になる場合があります。

レベル順：F、B、G、A、D、I、C、E、H。

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

その他のタイプ

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

アプリケーション

算術式を表す木: A * ( B − C ) + ( D + E )

事前順序探索は、式ツリーからプレフィックス式（ポーランド記法）を作成するために使用できます。つまり、式ツリーを事前順序に従って探索します。例えば、図に示された算術式を事前順序に従って探索すると、「+ * A − B C + D E」という式が生成されます。プレフィックス記法では、各演算子のオペランド数が固定されている限り、括弧は必要ありません。事前順序探索は、式ツリーのコピーを作成するためにも使用されます。

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

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

実装

深さ優先探索の実装

以下は、再帰アプローチ (左) と反復アプローチ (右) での事前順序、事後順序、および順序トラバーサルのスタックベースの実装の例です。

反復的なアプローチでの実装により、再帰の欠点、特にスタック スペースの制限やパフォーマンスの問題を回避できます。

いくつかの代替実装についても言及されています。

事前注文の実装

手順preorder(node) ノード = nullの場合、戻り値  訪問(ノード) 事前注文(ノード.左) 事前注文(node.right)
手順iterativePreorder(node) ノード = nullの場合、スタックを返す ←空のスタック  スタック.プッシュ(ノード)  stack.isEmpty()ではない場合 ノード ← stack.pop() 訪問(ノード) // 右の子が最初にプッシュされ、左の子が最初に処理されます node.right ≠ nullの場合 スタック.プッシュ(ノード.右) node.left ≠ nullの場合 スタック.プッシュ(ノード.左)

注文後の実装

手順postorder(node) ノード = nullの場合、戻り値  後順序(ノード.左) ポストオーダー(ノード.右) 訪問(ノード)
手順iterativePostorder(node) ノード = nullの場合、戻り値 stack ←空 stack lastNodeVisited ← nullノード≠ nullの場合、 stack.isEmpty()またはnode ≠ nullではない     スタック.プッシュ(ノード) ノード ← ノード.左 それ以外 peekNode ← stack.peek() // 右の子ノードが存在し、ノードをトラバースしている場合 // 左の子から右へ移動 peekNode.right ≠ null かつlastNodeVisited ≠ peekNode.rightの場合 ノード ← peekNode.right それ以外 訪問(peekNode) lastNodeVisited ← stack.pop()

順序どおりの実装

手順inorder(node) ノード = nullの場合、戻り値  inorder(ノード.left) 訪問(ノード) inorder(ノード.right)
手順iterativeInorder(node) ノード = nullの場合 、stack ←空のスタックを返します。stack.isEmpty()またはノード ≠ nullの場合、ノード ≠ nullではありません。     スタック.プッシュ(ノード) ノード ← ノード.左 それ以外 ノード ← stack.pop() 訪問(ノード) ノード ← ノード.right

予約注文の別のバリエーション

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

手順bubbleUp(配列, i, leaf) k ← 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, リーフ) i ← 親 * 2 + 2

次のノードまたは前のノードに進む

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

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

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

手順inorderNext(node, dir, stack) 新しいノード ← node.child[dir] newnode ≠ null の場合 ノード ← 新しいノード スタック.プッシュ(ノード) 新しいノード ← 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ステップの完全な探索ステップを必要とするため、計算量です。最悪の場合の複雑度は、木の高さと同じです。

上記の実装はすべて、ツリーの高さに比例したスタック領域を必要とします。これは、再帰呼び出しの場合は呼び出しスタック、反復呼び出しの場合は親（祖先）スタックです。ツリーのバランスが悪い場合、このスタック領域は相当な量になる可能性があります。反復呼び出しの実装では、各ノードに親ポインタを保持するか、ツリーをスレッド化することで、スタック要件を削減できます（次のセクション）。

スレッドを使用したモリス順序走査

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

利点:

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

デメリット:

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

モリストラバーサルは、スレッドを使用した順序付きトラバーサルの実装である。[9]

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

幅優先探索

また、以下に、単純なキューベースのレベル順探索の擬似コードを示します。この探索では、特定の深さにおけるノードの最大数に比例したメモリ容量が必要になります。これは、ノードの総数の半分にも達する可能性があります。この種の探索では、反復深化深さ優先探索を用いることで、よりメモリ効率の高いアプローチを実装できます。

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

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

手順levelorder(array) はi を0からarray.sizeまで指定します。 訪問(配列[i])

無限の木

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

トラバーサルの基本要件は、最終的にすべてのノードを訪問することです。無限木の場合、単純なアルゴリズムではこの要件を満たせないことがよくあります。例えば、無限の深さを持つ二分木の場合、深さ優先探索では木の片側（慣例的に左側）を探索し、残りのノードは探索しません。また、インオーダー探索やポストオーダー探索では、葉に到達していないため（実際には到達しません）、どのノードも探索しません。対照的に、幅優先（レベル順）探索では、無限の深さを持つ二分木を問題なく探索し、分岐係数が制限されている任意の木を探索します。

一方、深さ2のツリーで、ルートに無限の子ノードがあり、それぞれの子ノードに2つの子ノードがある場合、深さ優先探索ではすべてのノードを探索します。これは、孫ノード（あるノードの子ノードの子ノード）を探索し尽くしたら、次のノードに進むためです（ただし、後順探索でない場合はルートに到達しません）。一方、幅優先探索では、まず子ノードを探索し尽くすため、孫ノードに到達することはありません。

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

したがって、単純な深さ優先探索や幅優先探索では、すべての無限木を走査することはできず、非常に大きな木では効率的ではありません。しかし、ハイブリッド手法では、基本的に対角線引数を介して、任意の（可算）無限木を走査できます（「対角線」は垂直方向と水平方向の組み合わせであり、深さと幅の組み合わせに対応します）。

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

  1. （）
  2. （1）
  3. （1, 1） （2）
  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 は二分木に対応します)。

参考文献

  1. ^ 「講義8、ツリートラバーサル」 。 2015年5月2日閲覧。
  2. ^ ab Pfaff, Ben (2004).二分探索木とバランス木入門. フリーソフトウェア財団.
  3. ^ 二分木走査法
  4. ^ 「Preorder Traversal Algorithm」 . 2015年5月2日閲覧。
  5. ^ L before R は、図に示すように（標準的な）反時計回りの走査を意味します。L
    と R の前、間、または後に N を実行することで、説明されている方法のいずれかが決まります。
    走査が逆方向（時計回り）に行われる場合、その走査は逆順と呼ばれます。これは、データを降順で取得する場合の逆順走査について特に説明されています。
  6. ^ 「アルゴリズム、事前、事後、順序付きシーケンシャル化のどの組み合わせがユニークか？ Computer Science Stack Exchange」 。 2015年5月2日閲覧。
  7. ^ Wittman, Todd. 「Tree Traversal」（PDF） . UCLA Math . 2015年2月13日時点のオリジナル（PDF）からアーカイブ。 2016年1月2日閲覧。
  8. ^ "constexpr tree structures". Fekir's Blog . 2021年8月9日. 2021年8月15日閲覧。
  9. ^ Morris, Joseph M. (1979). 「バイナリツリーの単純かつ安価な走査」. Information Processing Letters . 9 (5): 197– 200. doi :10.1016/0020-0190(79)90068-1.

出典

  • デール、ネル、リリー、スーザン・D.「Pascal Plus データ構造」、DC Heath and Company、マサチューセッツ州レキシントン、1995年、第4版。
  • Drozdek, Adam. 『C++におけるデータ構造とアルゴリズム』 Brook/Cole. パシフィックグローブ、カリフォルニア州. 2001年. 第2版.
  • 「ツリー横断」（math.northwestern.edu）
  • PHP でのトラバーサル例を使用してデータベースに階層データを保存する
  • MySQL での階層データの管理
  • MySQLでグラフを操作する
  • Rosetta Codeでさまざまなプログラミング言語に実装されたツリートラバーサルを参照してください。
  • 再帰なしのツリー走査
  • ツリートラバーサルアルゴリズム
  • 二分木走査
  • データ構造におけるツリートラバーサル
「https://en.wikipedia.org/w/index.php?title=Tree_traversal&oldid=1326536207」から取得