1. 概要

この記事では、最も低い共通の祖先の問題について説明します。 基本的な定義から始めて、ルートツリー内の2つのノードの最も低い共通の祖先を見つけるために使用されるいくつかの方法を実行します。

2. 意味

2つのノードのルートツリー内の最も低い共通祖先（LCA）は、との両方の祖先である最も低い（最も深い）ノードです。

ルートツリー内のノードの祖先は、ルートから（を含む）へのパス上にあるノードであることに注意してください。

たとえば、ノード1をルートとする次のツリーを見てみましょう。

ハイライトされた2つのノード7と11のLCAを見つけましょう。 これら2つのノードの共通の祖先は、ノード1と2です。 ノード2はノード1よりも深いため、。

3. 素朴なアプローチ

3.1. 理論的アイデア

このアプローチの考え方は、各ノードに1つずつ、合計2つのポインターを持つことです。 LCA でそれらが出会うことができるように、これらのポインターをルートに向かって移動する必要があります。

最初に気付くのは、これらのポインターが同じ深さにある必要があるということです。 それに加えて、より深いポインタがLCAになることはありません。 したがって、最初のステップは、2つのポインターが同じ深さになるまで、より深いポインターをその親に移動し続けることです。

これで、同じ深さにある2つのポインターができました。 1つのノードで出会うまで、両方のポインターを一度に1ステップずつルートに向かって移動し続けることができます。 このノードは、ポインターが出会うことができる最も深いノードであるため、LCAである開始ノードの最も深い共通の祖先です。

3.2. P再処理

このソリューションを実装するには、各ノードの深さと親を計算する必要があります。 これは、ルートから開始する単純なDFSトラバーサルで実行できます。

まず、現在のノードを訪問済みとして設定します。 次に、関数を再帰的に呼び出す前に、子ノードの親と深さを設定します。

このアプローチの前処理ステップの複雑さはです。ここで、はノードの数です。 適用する必要があるのは1回だけなので、複雑さは効率的であると見なされます。

3.3. LCAを見つける

ルートから開始して前の関数を呼び出した後、各ノードの深さと親を取得します。 これで、前に説明したアプローチを適用できます。

まず、両方のノードの深さが同じになるまで、より深いノードをその親に移動し続けます。 その後、両方のノードが出会うまで親に移動します。

アプローチはかなり単純であると考えられていますが、ノードのペアのLCAを見つけることも、の複雑さを持ちます。ここで、はツリーの高さです。 この複雑さは、ほぼ線形のツリーの場合にまで及ぶ可能性があります（ルートで接続された2つの長いチェーンを考えてみてください）。

4. スパーステーブルの背景

セクション3で説明したアプローチを強化するには、スパーステーブルのデータ構造に関する背景を説明する必要があります。 スパーステーブルを最初に作成する必要があります。 次に、複雑さを抑えて最小範囲のクエリに答えることができます。

スパーステーブルの主なアイデアについて説明します。 後で、ニーズに合わせて更新します。

4.1. スパーステーブルの構築

スパーステーブルは、前処理を使用して静的配列の範囲クエリに応答できるデータ構造です。 このデータ構造の背後にある直感は、任意の範囲を、長さが2の累乗である最大の範囲の連結として表すことができるということです。 これは、範囲の長さをバイナリで表すのと同じです。 たとえば、長さの範囲は、長さが8、4、および1の3つの範囲の連結として表すことができます。

配列内の最小範囲クエリに回答するために使用されるスパーステーブルについて説明しましょう。 スパーステーブルは、サイズの配列で構成されます。 配列の要素から始まり、長さが。の範囲の最小値を格納します。

この配列を次の昇順で入力してみましょう。

  1. は単にに等しい。
  2. 計算してみましょう：この値は、インデックスで始まる長さの範囲の最小値であることがわかっています。 この範囲を2つの等しい部分に分割できます。それぞれの長さは、で始まり、もう1つはで始まります。 これは、との間の最小値に等しいことを意味します。

アルゴリズムの実装を見てください。

スパーステーブルの作成の複雑さはです。ここで、は要素の数です。

4.2. スパーステーブルのクエリ

スパーステーブルが作成されたので、それを使用して範囲最小クエリに回答する方法を見てみましょう。 数値を2進数に変換する1つの方法は、2の累乗を降順で調べることです。 現在の電力が。以下の場合は、対応するビットをアクティブにして、それを。から減算します。 同様のことをします。 範囲内の最小値を見つけたいとしましょう。

まず、現在の場所はです。 そのような最大のものを見つけたい（長さが2の累乗で、に含まれる最長の範囲）。 この値を見つけた後、すでにに格納されているため、この範囲の最小値を取得できます。

次に、同じ方法で範囲内の最小値を見つける必要があります。 空の間隔になるまでこれを続けます。 の値は厳密に減少するため、の値を降順で1回ループするだけで、答えを計算できます。

説明されているアルゴリズムを見てみましょう。

スパーステーブルのクエリの複雑さはです。ここで、は要素の数です。

スパーステーブルがどのように機能するかについての背景がわかったので、LCAを見つけるためのより効率的なアルゴリズムを見てみましょう。

5. バイナリリフティングアプローチ

5.1. 理論的アイデア

スパーステーブルに似た構造を構築しましょう。ただし、長さが2の累乗の範囲に最小値/最大値を格納する代わりに、すべてのノードの祖先を格納します。

つまり、あるノードへのポインタがあり、このポインタをその親の時間に移動した場合、最終的にノードになります。 これをからのジャンプと呼びましょう。

5.2. 前処理

この構造の構築を開始する前に、各ノードの直接の親を格納する配列が必要です。

構造の構築は、通常のスパーステーブルの構築に似ています。

  2. forの値を見つけるには、からジャンプする必要があります。 ただし、からジャンプすると、ノードに到達することはすでにわかっています。 また、からジャンプすると、ノードに到達することもわかっています。 2つの連続したジャンプはジャンプと同等であるため、これはを意味します。

5.3. アルゴリズム

それでは、スパーステーブル構造を使用して単純なアプローチを最適化する方法を見てみましょう。 素朴なアプローチは、2つの主要なステップで構成されていました。

最初のステップは、両方のポインターが同じ深さになるまで、より深いポインターをその親に移動することでした。

より深いポインタがノードにあり、もう1つがノードにあると仮定します。 に等しい既知のステップ数でポインターを移動する必要があります。 バイナリに変換し、ビットがアクティブになるようにジャンプを実行すると、ジャンプが発生します。 このジャンプにより、このポインターは他のポインターと同じ深さになります。

各ジャンプはであり、ジャンプのタイプをチェックする必要があるため、このステップ全体の複雑さは。です。

2番目のステップは、あるノードで出会うまで両方のポインターを同時に移動することでした。

ここでの主なアイデアは、最初に大きなジャンプを試すことです。 両方のポインターで大きなジャンプを実行すると、それらが同じノードに到達する場合、共通の祖先に到達しました。 ただし、ジャンプしすぎた可能性があります。 より深い共通の祖先が存在する可能性があります。 したがって、このジャンプはできません。もっと小さいものを試してみましょう。

現在のジャンプがそれらを異なるノードに導く場合は、このジャンプを実行してポインターを更新する必要があります。 これは基本的に、共通の祖先にまだ到達していない、可能な限り最大のジャンプを行ったことを意味します。 したがって、両方のポインターの親は、LCAである最も深い共通の祖先になります。 このステップでは、さまざまなジャンプも検討するため、複雑さもです。

このアルゴリズムの複雑さはです。ここで、はノードの数です。

5.4. バイナリリフティングアルゴリズムの手順

要約すると、このアプローチでLCAを見つけることは、2つの主要な部分で構成されます。

  1. 前処理：この部分はツリーに1回だけ適用され、2つのステップがあります。
    • 各ノードの深さと親を見つけます（アルゴリズム1）。
    • スパーステーブル構造を構築します（アルゴリズム5）。 この部分の複雑さは、スパーステーブルの作成の複雑さによるものです。
  2. LCAクエリへの回答：この部分は、LCAを検索するノードの各ペアに適用されます（アルゴリズム6）。 この部分の複雑さは、ジャンプのみを行っているためです。

6. 比較

このチュートリアルでは、2つのアプローチを最終的に比較してみましょう。

バイナリリフティングアプローチを使用する場合の主な利点は、多数のクエリを処理できることです。 まず、前処理を1回適用する必要があります。そうすると、多数のクエリを実行できます。各クエリはで応答されます。 したがって、各クエリは、単純なアプローチを使用する場合よりも複雑に回答されます。

7. 結論

このチュートリアルでは、ツリーデータ構造の最小共通祖先問題について説明しました。

最初に定義を確認し、次にLCAを見つける2つの方法について説明しました。 最後に、2つの方法を簡単に比較しました。