通りがけ順走査 — 左、ルート、右

通りがけ順(LNR)木走査を学びます。BST ではノードを昇順に訪問します。再帰アルゴリズム、反復的変形、一般的な応用を理解します。

Traversal

詳細な説明

通りがけ順走査(LNR)

通りがけ順走査は 左部分木、ノード、右部分木 の順序でノードを訪問します。二分探索木の場合、値が昇順ソート順序で生成されます。これが BST の最も有用な性質の1つです。

再帰的実装

INORDER(node):
  if node is NULL: return
  INORDER(node.left)
  visit(node)          // 現在のノードを処理
  INORDER(node.right)

        4
       / \
      2   6
     / \ / \
    1  3 5  7

通りがけ順結果: [1, 2, 3, 4, 5, 6, 7]

出力がソートされていることに注目してください。これは有効な BST で常に成り立ちます。

スタックを使用した反復的実装

INORDER_ITERATIVE(root):
  stack = []
  current = root
  while current != NULL or stack is not empty:
    while current != NULL:
      stack.push(current)
      current = current.left
    current = stack.pop()
    visit(current)
    current = current.right

反復版は明示的なスタックを使用して再帰をシミュレートします。最も左のノードを最初に処理し、再帰的な呼び出し順序と同じです。

時間・空間計算量

  • 時間: O(n) — すべてのノードが正確に1回訪問される
  • 空間: O(h) — 再帰の深さ(またはスタックサイズ)は木の高さ h に等しい。バランスした木では O(log n)、偏った木では O(n)

応用

  • BST 検証: 通りがけ順走査がソート済みシーケンスを生成すれば、木は有効な BST
  • K 番目に小さい要素: 通りがけ順走査を実行し、k 番目の要素で停止
  • 範囲クエリ: 通りがけ順走査中に2つの境界値間のすべての値を収集

ユースケース

通りがけ順走査はツリーベースのインデックスを使用するデータベースやファイルシステムの基礎です。インデックス付き列に対して ORDER BY を含む SQL クエリを実行すると、データベースエンジンは本質的に B-tree の通りがけ順走査を実行します。木の走査の面接質問として最も一般的なものの1つです。

試してみる — Binary Tree Visualizer

フルツールを開く