通りがけ順走査 — 左、ルート、右
通りがけ順(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つです。