祖先ノード検索（LCA）完全ガイド：アルゴリズム、応用、実装と最適化

2025年12月12日 最終更新日時 : 2025年12月12日 エバープレイ編集部

はじめに

ツリー構造の祖先ノード検索（Ancestors Search）、特に「Lowest Common Ancestor（LCA、最小共通祖先）」の問題は、ファイルシステム、DOMツリー、XML、系譜データ、ネットワーク解析、競技プログラミングなど幅広い分野で基本的かつ重要な技術です。本稿では基礎概念から一般的アルゴリズム（ナイーブ法、タイムスタンプ法、二分リフト、オイラー巡回＋RMQ、Tarjan のオフライン法）、動的木に対するアプローチ、実装上の注意点、計算量とメモリのトレードオフまで、実用的・理論的に深掘りして解説します。

問題定義と基本概念

与えられた根付き木（rooted tree）に対して、2つのノード u, v に共通の祖先のうち、最も深い（root に近くない）ノードを LCA(u, v) と定義します。多くの関連問題が存在します：

  • 単純な問い合わせ: あるノードが別のノードの祖先か（is-ancestor）を判定する。
  • LCA 問い合わせ: 任意の u, v に対し LCA(u, v) を返す。
  • 距離計算: 2 点間の距離は depth[u] + depth[v] - 2*depth[LCA(u,v)] で求められる（辺重みが 1 の場合）。
  • オフライン／オンライン: 問い合わせが事前に全て分かっているか（オフライン）か、逐次到着するか（オンライン）かで適切なアルゴリズムは異なります。

最も単純なアプローチ（親ポインタでの上昇）

各ノードが親（parent）への参照を持つ場合、u と v の深さを揃えるために深い方を親へ辿り、深さが等しくなったら同時に親へ辿っていく方法があります。

  • 長所: 実装が極めて単純で、メモリオーバーヘッドがほとんどない。
  • 短所: 各クエリで O(h)（h はツリーの高さ）かかり、最悪で O(N) となる。多数のクエリや深い木では実用的でない。

タイムスタンプ法（Tin/Tout を用いる祖先判定）

DFS の入り時刻 tin[v] と退出時刻 tout[v] を記録すると、u が v の祖先であることは次の条件で判定できます： tin[v] <= tin[u] && tout[u] <= tout[v]。これは O(1) 判定で済むため、祖先判定（is-ancestor）が大量に必要な場面で非常に有効です。ただし LCA を直接返すわけではないため、LCA 問い合わせには他の技術と組み合わせます。

二分リフト（Binary Lifting）

二分リフトはオンラインで高速に LCA を求める代表的手法です。各ノード v に対して 2^k 個上の祖先 up[v][k] を事前計算（DP）します。計算とクエリの複雑度・特徴は次の通りです：

  • 前処理: O(N log N)（N はノード数、log は最大高さの対数）時間、O(N log N) メモリ。
  • クエリ: O(log N) 時間で LCA を取得可能。
  • 実装ポイント: 深さを揃えるときにビット分解を使い、上昇の各ステップを up[][] テーブル参照で行う。再帰深度が問題になる場合、スタックベースの DFS を使って tin/tout と depth, up 配列を計算する。

二分リフトは扱いやすく、多くの競技プログラミングや実務実装で標準になっています。辺に重みがある場合でも深さ（あるいは root からの距離）を記録しておけば距離計算に応用できます。

オイラー巡回（Euler Tour）と RMQ による O(1) クエリ法

オイラー巡回法と Range Minimum Query（RMQ）を組み合わせると、前処理 O(N) ～ O(N log N)、クエリ O(1) の非常に高速な実装が可能です。Bender と Farach-Colton の手法が有名です。手順は大まかに次のとおりです：

  • 根から DFS して、訪問したノードの順にオイラー巡回配列 E を作る（ノードが訪れるたびに配列へ追加）。同時に各ノードの最初の出現位置 first[v] と深さ depth[v] を記録する。
  • LCA(u, v) は E 内で first[u] から first[v] までの区間（順序に注意）の深さが最小となるノード（RMQ の最小値）に対応する。
  • RMQ はスパーステーブル等で実装すれば O(N log N) 前処理、O(1) クエリだが、Bender-Farach-Colton の手法を用いると O(N) 前処理かつ O(1) クエリが可能。

この手法の利点は非常に高速なクエリ応答（特に大量の問い合わせがある場合）と、距離計算等への応用のしやすさです。一方、RMQ の前処理に追加のメモリが必要になります。

Tarjan のオフライン LCA（Disjoint Set Union を利用）

Tarjan が提案したオフラインアルゴリズムは、クエリ集合が事前に分かっている場合に効率的です。主要なアイデアは DFS を行いながら DSU（Union-Find）を用いて部分木の情報をマージし、探索済みのノードに対して対応するクエリを処理することです。

  • 時間計算量: O(N + Q α(N))（Q はクエリ数、α は逆アッカーマン関数）で実質的に線形。
  • 制約: オンラインでの問い合わせには使えない（全てのクエリを事前に知っている必要がある）。
  • 用途: 大量クエリを一括で処理するバッチ処理や、変更がない静的木に対する一回限りの解析に最適。

動的木とオンライン更新（Link-Cut Tree, Euler Tour Tree, HLD）

木構造に対してリンク（辺の追加）やカット（辺の削除）を含む動的操作が必要な場合、標準的な LCA 前処理は使えません。そのため以下のようなデータ構造が用いられます：

  • Link-Cut Tree（Splay ベースの動的木）: パス更新やパス問い合わせ、LCA を O(log N) で処理可能。実装は複雑。
  • Euler Tour Tree（ダイナミックなオイラー巡回を保持する平衡二分木）: 動的連結成分や部分木サイズの管理に便利。
  • Heavy-Light Decomposition（HLD）: パス分解を用いて各パスをセグメント木で管理し、クエリや更新を O(log^2 N) あるいは改善して O(log N) で実現できる。LCA の取得自体は容易（重み付き深さや親ポインタとの併用で簡単に求まる）。

動的木の選択は、必要な操作（リンク／カット／パス和／ノード更新等）と実装コストで決めるのが一般的です。

実装上の注意点と最適化

  • 根の選択: 根をどこにとるかで深さや親が変わるが、LCA の定義自体は根付き木に依存する。一般に任意のノード（多くは 0 または 1）を根にとれば良い。
  • 森林への対応: 木が複数ある場合、各連結成分ごとに根を設定するか、仮想的なスーパー根を作って辺で連結する方法がある（後者は距離計算等に注意）。
  • メモリ: 二分リフトやスパーステーブルは O(N log N) のメモリを必要とする。組込み環境やメモリ制限が厳しい場合は tin/tout と親ポインタだけで妥協することも検討。
  • 再帰深度: 深い木では再帰 DFS がスタックオーバーフローを起こすことがある。明示的スタックを用いた DFS を推奨。
  • 重み付き木での距離計算: depth[v] を「辺の数」ではなく「root からの距離（重みの合計）」として保存しておけば LCA を使って距離を簡単に計算できる。
  • 検証・デバッグ: ランダムな木生成とランダムクエリに対しナイーブ法で結果を比較するのが実装検証に有効。

応用例

  • ファイルシステムや DOM ツリーでの最も近い共通親要素の検索。
  • ネットワークにおける最短経路や共通中継点の特定（ツリー上）。
  • 系譜データ・進化系統樹（phylogenetic tree）での共通祖先検索。
  • 競技プログラミング: 距離クエリ、パス上の最大値／和のクエリ、部分木クエリなど多様な問題の基盤。

まとめと選び方の指針

どのアルゴリズムを採用するかは、問題の性質によります。簡単な実装とオンライン対応が欲しい場合は二分リフト（Binary Lifting）を推奨します。多数のクエリかつ最高速の応答が必要で前処理コストを許容する場合はオイラー巡回＋RMQ（Bender-Farach-Colton）を検討してください。クエリが事前に既知なら Tarjan のオフラインアルゴリズムが非常に効率的です。木が動的に変化する場合は Link-Cut Tree や Euler Tour Tree、HLD といった動的データ構造を検討します。

最後に、実装では再帰深度、メモリ制約、入力サイズに注意し、ランダムテストによる検証を行うことを強く勧めます。

参考文献

カテゴリー
IT
前の記事
音色調整の科学と実践：録音・ミックスからマスタリングまでの包括ガイド
2025年12月12日
次の記事
クラシック音楽の新古典派（ネオクラシシズム）——背景・特徴・代表作を深掘り
2025年12月12日