データ構造と探索｜スタック・キュー・二分探索木・AVL・BFSを図で理解する

後で処理する対象を、どの順序で取り出すか。それを決める構造がスタックやキューです。値を比較して進む木、つながりをたどるグラフにも順序の規則があります。データ構造の形だけでなく、追加・取出し・更新で守る条件を理解します。

この記事で理解すること

• スタックとキューを使うと処理順序がどう変わるかを説明する。

• 二分探索木の大小条件とAVL木の高さ条件を、探索・挿入・削除で確認する。

• BFSとDFSを区別し、循環するグラフで重複した処理を防ぐ。

架空の倉庫で、作業依頼を順番に処理し、整数の商品キーを検索し、通路の接続から到達できる区画を調べる例を使います。同じキーの二重挿入は認めず、グラフの隣接区画は名前の昇順で調べるとします。順序が指定されていない場合、唯一の訪問順とは限りません。

スタックとキュー：追加と取出しの位置

スタックは後入れ先出し、LIFOの構造です。pushで頂上へ積み、popで最後に積んだ要素を取り出します。キューは先入れ先出し、FIFOで、enqueueで末尾へ加え、dequeueで先頭から取り出します。操作名だけでなく、どの端を使うかを確認します。

空から要素を取り出す操作は、その構造だけでは値を返せません。空判定、エラー、特別な戻り値などの仕様が必要です。容量固定なら満杯への追加も検査します。単なる構造の定義と、複数スレッドが安全に共有する同期機構は別テーマです。

配列と連結リスト：実装の違いを理解する

配列は添字で要素へアクセスする構造です。途中に値を挿入して順番を保つには、後ろの要素をずらす処理が必要になることがあります。連結リストはノードが次のノード等への参照を持つ構造で、対象の位置が分かれば参照の付け替えで挿入できます。

ただし、連結リストは位置を探すまで順番にたどる必要があります。「挿入が速いから全ての検索も速い」とはいえません。配列でキューを実装するときも、毎回全要素をずらす方法と、先頭位置を進める循環バッファでは動きが違います。具体的な実装と抽象的な取出し順を分けます。

木と二分探索木：形と大小の規則

木は根から枝をたどる階層構造です。ノード、親、子、葉、部分木という用語を使います。二分木は各ノードの子が最大二つの木です。二分探索木はさらに、各ノードの左部分木のキーが小さく、右部分木のキーが大きいという条件を持ちます。

30を検索するなら、40より小さいので20へ、20より大きいので30へ進みます。左の子だけが小さければよいのではなく、左部分木の全キーが条件を満たす必要があります。比較で片側へ絞れる理由は、この大小条件にあります。

中順走査で昇順になるのは二分探索木の大小条件があるためです。どんな二分木でも中順が数値順になるわけではありません。再帰の呼出しの動きは擬似言語・再帰の記事と対応付けて学びます。

挿入と削除：探索木の条件を保つ

25を挿入するなら、40、20、30と比較し、30の左側の空いている位置へ置きます。新しいキーが既にある場合、この例では追加しません。重複キーを数として保持するなど別の方式を使う場合は、比較条件と格納規則を先に決めます。

削除は子の数で場合を分けます。葉なら親からの参照を外し、子が一つならその子を親へつなぎます。子が二つなら、右部分木の最小キーである後継などを使って値を置き換え、移した元の位置を適切に削除します。単にそのノード以下を消す処理ではありません。

元の木で20を削除するなら、後継の30で20の位置を置き換え、元の30の葉を外す方法があります。10は残り、根40より小さい条件も保ちます。右部分木の任意の値を持ってくると、大小条件を壊す場合があるため、後継を選ぶ理由を確認します。

AVL木：高さの偏りを回転で直す

二分探索木へ小さい順にキーを挿入すると、片側へ長く伸びる場合があります。AVL木は各ノードで左右の部分木の高さの差を1以内に保つ二分探索木です。高さ差の符号は資料の定義で逆になる場合があるので、ここでは左の高さ−右の高さとします。

30、20、10を順に入れると30の左側に偏ります。30を基点に右回転し、20を根、10を左、30を右にすると、高さ差を直せます。回転では部分木も正しく付け替え、キーの中順の順序を保ちます。キーの値を小さい順に書き換えて直す操作ではありません。

左の子の右側へ偏る場合は、子を左回転してから親を右回転する二重回転が必要になることがあります。右側の偏りは対称に考えます。挿入・削除後に祖先の高さを更新して条件を点検し、削除では上方への再調整が続く場合もあります。

AVLの探索・挿入・削除は高さが対数的に抑えられます。一方、通常の二分探索木の形は入力順で偏り、最悪では長い列になります。計算量の厳密な評価やソートとの比較は計算量の記事へ分けます。

グラフ：接続を表し、訪問済みを管理する

グラフは頂点と辺で接続を表します。方向を持つ有向グラフ、方向を持たない無向グラフ、重み付きの辺などがあり、条件で使える探索が変わります。この例は無向・重みなしです。木と違って循環や、同じ頂点への複数経路が存在します。

頂点からつながる頂点を並べる隣接リストを使います。AはB・C、BはA・D、CはA・D・E、DはB・C、EはCへつながります。訪問済みを記録しないと、AからBへ進んで再びAへ戻り、同じ処理を繰り返す危険があります。

幅優先探索BFS：近い層から調べる

BFSはキューを使い、開始頂点から辺の本数が少ない層を先に調べます。最初にAを訪問済みとしてキューへ入れ、先頭を取り出して未訪問の隣接頂点を末尾へ加えます。この例では取り出す順はA、B、C、D、Eです。

distance[A] ← 0
visited ← {A}
queue ← [A]
while queue is not empty
  v ← dequeue(queue)
  for each u in neighbors(v) in name order
    if u is not in visited
      add u to visited
      distance[u] ← distance[v] + 1
      parent[u] ← v
      enqueue(queue, u)

DはBを調べた時点で訪問済みにするため、Cから見つけても二度キューへ入れません。取り出した時点でだけ印を付け、投入時の重複も管理しない方式では、待ち行列に同じ頂点が重複する場合があります。

重みなしのグラフではBFSで辺の本数が最小の経路を得られます。Dまでの距離は2、親をたどる経路はA-B-Dです。A-C-Dも同じ長さですが、昇順の調査で先に発見したBを親にします。重みが異なる辺の最小費用経路を、この条件だけで保証しません。

深さ優先探索DFS：一つの枝を先へ進む

DFSはスタックや再帰の呼出しを使い、一つの枝を深く進んでから戻ります。再帰版で訪問時に印を付け、隣接頂点を昇順に調べると、この例はA、B、D、C、Eの順です。BFSの順序や最短経路の性質とは違います。

明示的なスタックへ複数候補を入れる実装では、後入れ先出しなので、追加順と取出し順が逆になります。再帰版と同じ順序にしたいからといって、隣接頂点を昇順のまま一括pushすればよいわけではありません。訪問印の時点や実装条件も含めてトレースします。

演習1：取出し順

条件：空の構造へA、B、Cを順に追加し、その後全て取り出す。

問い：スタックとキューの順序を答える。

解答例：スタックはC、B、A。キューはA、B、C。

根拠と誤答の確認：後入れ先出しと先入れ先出しを対応付けます。

演習2：木の探索

条件：上の二分探索木で30を探す。

問い：比較するキーの順序を答える。

解答例：40、20、30。小さい側、大きい側の順に進む。

根拠と誤答の確認：図の全ノードを順番に見る探索ではありません。

演習3：二子の削除

条件：元の木から20を、後継を使う方式で削除する。

問い：置換に使うキーと残す子を答える。

解答例：30を置換に使い、10を左の子として残す。

根拠と誤答の確認：20の部分木全体を削除すると10まで失います。

演習4：AVLの回転

条件：空のAVL木へ30、20、10を挿入した。

問い：必要な回転と新しい根は何か。

解答例：30で右回転し、新しい根は20。10と30を左右へ置く。

根拠と誤答の確認：中順の10、20、30を保ったまま高さ差を直します。

演習5：重複した発見

条件：BFSでBからDをキューへ入れた後、CからもDを発見する。

問い：二重投入を防ぐ印はいつ付けるか。

解答例：Dを初めてキューへ入れる時点で訪問済みとする。

根拠と誤答の確認：取り出す時だけの印では、待機中のDを再投入する場合があります。

演習6：探索結果の範囲

条件：辺に異なる移動時間が付くが、通常のBFSで調べる。

問い：時間が最短の経路を保証できるか。

解答例：できない。通常のBFSが最小にするのは重みなしでの辺の本数。

根拠と誤答の確認：重み付きの費用の最小化と、到達や層順の探索を区別します。

参照資料とこの記事の範囲

事例・図・演習は教材用に独自に作成しました。公式・教育機関の資料で仕組みを確認し、特定年度の問題本文を前提にせず学べる構成にしています。

Runestone スタック・キュー等の基本構造

Runestone 二分探索木

Runestone AVLの高さと性能

Runestone BFS

IPA APシラバス

関連テーマを続けて学ぶ

擬似言語のトレース｜代入・ループ・配列・関数を実行順に追う

記述式の設問と本文根拠の読み方