C++でRMQを使用してバイナリツリーでLCAを検索する

コンセプト

この記事では、ツリー内の2つのノードのLCAをRMQ問題に還元することにより、そのLCAを見つける問題を解決する方法について説明します。

例

最低共通祖先（LCA） ルートツリーTの2つのノードaとbのうち、aとbの両方を子孫として持つ、ルートから最も遠いノードとして定義されます。

たとえば、下の図によると、ノードDとノードIのLCAはノードBです。

LCAの問題を解決するために、非常に多くのアプローチを適用できます。これらのアプローチは、時間と空間の複雑さの点で異なります。

範囲最小クエリ（RMQ） 配列に適用され、指定された2つのインデックス間の最小値を持つ要素の位置を特定します。 RMQを解決するためにさまざまなアプローチを適用できます。この記事によると、セグメントツリーベースのアプローチが説明されています。セグメントツリーに関しては、前処理時間はO（n）であり、範囲最小クエリの時間はO（Logn）です。ここで、必要な追加スペースは、セグメントツリーを格納するためのO（n）です。

LCAのRMQへの削減

事前注文トラバーサル特性を備えたDFS（深さ優先探索）タイプのトラバーサルであるオイラーツアー（鉛筆を持ち上げずに訪問）でルートからツリーを訪問するというこのアイデアを説明します。

観察 −上の図によると、ノードDとIのLCAはノードBであり、TのDFS中にDとIの訪問中に遭遇したすべてのノードの中でルートに最も近いノードであることを示しています。したがって、この観察結果は次のように言えます。削減の鍵です。ここでも、私たちのノードは最小レベルのノードであり、Tのオイラーツアーでaとbの連続発生（任意）の間に発生するすべてのノードの中でそのレベルの唯一のノードであると言えます。

実装には3つのアレイが必要です-

• Tのオイラーツアーの順にノードを訪問

• Tのオイラーツアーで訪問した各ノードレベル

• Tのオイラーツアーでのノードの最初の発生インデックス（どの発生でも良いので、最初の発生を追跡しましょう）

メソッド

• ツリーでオイラーツアーを実行し、オイラー、レベル、および最初の出現配列を埋めます。

• 最初に出現する配列を適用して、最小値のRMQアルゴリズムに供給されるレベル配列の範囲のコーナーとなる2つのノードに対応するインデックスを取得します。

• アルゴリズムが範囲内の最小レベルのインデックスを返すときに、それを適用してオイラーツアー配列を使用してLCAを決定します。

例

/* This C++ Program is implemented to find LCA of u and v by reducing the problem to RMQ */
#include<bits/stdc++.h>
#define V 9 // indicates number of nodes in input tree
int euler1[2*V - 1]; // indicates for Euler tour sequence
int level1[2*V - 1]; // indicates level of nodes in tour sequence
int firstOccurrence1[V+1]; // indicates first occurrences of nodes in tour
int ind; // indicates variable to fill-in euler and level arrays
//This is a Binary Tree node
struct Node1{
   int key;
   struct Node1 *left, *right;
};
// Utility function creates a new binary tree node with given key
Node1 * newNode1(int k){
   Node1 *temp = new Node1;
   temp->key = k;
   temp->left = temp->right = NULL;
   return temp;
}
// indicates log base 2 of x
int Log2(int x){
   int ans = 0 ;
   while (x>>=1) ans++;
      return ans ;
}
/* A recursive function is used to get the minimum value in a given range of array indexes. The following are parameters for this function.
st --> indicates pointer to segment tree
index --> indicates index of current node in the segment tree.
Initially 0 is passed as root is always at index 0
ss & se --> indicate starting and ending indexes of the segment
represented by current node, i.e., st[index]
qs & qe --> indicate starting and ending indexes of query range
*/
int RMQUtil(int index1, int ss1, int se1, int qs1, int qe1, int *st1){
      // It has been seen that if segment of this node is a part of given range, then return the min of the segment
      if (qs1 <= ss1 && qe1 >= se1)
         return st1[index1];
         //It has been seen that if segment of this node is outside the given range
      else if (se1 < qs1 || ss1 > qe1)
         return -1;
      // It has been seen that if a part of this segment overlaps with the given range
      int mid = (ss1 + se1)/2;
      int q1 = RMQUtil(2*index1+1, ss1, mid, qs1, qe1, st1);
      int q2 = RMQUtil(2*index1+2, mid+1, se1, qs1, qe1, st1);
      if (q1==-1) return q2;
      else if (q2==-1) return q1;
      return (level1[q1] < level1[q2]) ? q1 : q2;
   }
   // Return minimum of elements in range from index qs (query start) to
   // qe (query end). It mainly uses RMQUtil()
   int RMQ(int *st1, int n, int qs1, int qe1){
      // Check for erroneous input values
      if (qs1 < 0 || qe1 > n-1 || qs1 > qe1){
         printf("Invalid Input");
         return -1;
      }
      return RMQUtil(0, 0, n-1, qs1, qe1, st1);
   }
   // Now a recursive function that constructs Segment Tree for
   array[ss1..se1]. // si1 is index of current node in segment tree st
   void constructSTUtil(int si1, int ss1, int se1, int arr1[], int *st1){
      // When there will be only one element in array, store it in current node of
      // segment tree and return
      if (ss1 == se1)st1[si1] = ss1;
      else{
         // It has been seen that if there are more than one
         elements, then recur for left and right subtrees and store the
         minimum of two values in this node
         int mid1 = (ss1 + se1)/2;
         constructSTUtil(si1*2+1, ss1, mid1, arr1, st1);
         constructSTUtil(si1*2+2, mid1+1, se1, arr1, st1);
         if (arr1[st1[2*si1+1]] < arr1[st1[2*si1+2]])
            st1[si1] = st1[2*si1+1];
         else
            st1[si1] = st1[2*si1+2];
      }
   }
   /* Now this function is used to construct segment tree from given
   array. This function allocates memory for segment tree and calls
      constructSTUtil() to fill the allocated memory */
      int *constructST(int arr1[], int n){
         // Allocating memory for segment tree
         //Indicates height of segment tree
         int x = Log2(n)+1;
         // Indicates maximum size of segment tree
         int max_size = 2*(1<<x) - 1; // 2*pow(2,x) -1
         int *st1 = new int[max_size];
         // Indicates filling the allocated memory st1
         constructSTUtil(0, 0, n-1, arr1, st1);
         // Returning the constructed segment tree
         return st1;
      }
   // Indicates recursive version of the Euler tour of T
   void eulerTour(Node1 *root, int l){
      /* if the passed node exists */
      if (root){
         euler1[ind] = root->key; // inserting in euler array
         level1[ind] = l; // inserting l in level array
         ind++; // indicates increment index
         /* It has been seen that if unvisited, mark first occurrence*/
         if (firstOccurrence1[root->key] == -1)
         firstOccurrence1[root->key] = ind-1;
         /* touring left subtree if exists, and remark euler
         and level arrays for parent on return */
         if (root->left){
            eulerTour(root->left, l+1);
            euler1[ind]=root->key;
            level1[ind] = l;
            ind++;
         }
         /* touring right subtree if exists, and remark euler
         and level arrays for parent on return */
         if (root->right) {
            eulerTour(root->right, l+1);
            euler1[ind]=root->key;
            level1[ind] = l;
            ind++;
         }
      }
   }
   // Returning LCA of nodes n1, n2 (assuming they are
   // present in the tree)
   int findLCA(Node1 *root, int u1, int v1){
      /* Marking all nodes unvisited. Note that the size of
      firstOccurrence is 1 as node values which vary from
      1 to 9 are used as indexes */
      memset(firstOccurrence1, -1, sizeof(int)*(V+1));
      /* To start filling euler and level arrays from index 0 */
      ind = 0;
      /* Starting Euler tour with root node on level 0 */
      eulerTour(root, 0);
      /* constructing segment tree on level array */
      int *st1 = constructST(level1, 2*V-1);
      /*It has been seen that if v before u in Euler tour. For RMQ to
      work, first parameter 'u1' must be smaller than second 'v1' */
      if (firstOccurrence1[u1]>firstOccurrence1[v1])
      std::swap(u1, v1);
      // Indicates starting and ending indexes of query range
      int qs1 = firstOccurrence1[u1];
      int qe1 = firstOccurrence1[v1];
      // Indicates query for index of LCA in tour
      int index1 = RMQ(st1, 2*V-1, qs1, qe1);
      /* returning LCA node */
      return euler1[index1];
   }
   // Driver program to test above functions
   int main(){
      // Let us create the Binary Tree as shown in the diagram.
      Node1 * root = newNode1(1);
      root->left = newNode1(2);
      root->right = newNode1(3);
      root->left->left = newNode1(4);
      root->left->right = newNode1(5);
      root->right->left = newNode1(6);
      root->right->right = newNode1(7);
      root->left->right->left = newNode1(8);
      root->left->right->right = newNode1(9);
      int u1 = 4, v1 = 9;
      printf("The LCA of node %d and node %d is node %d.\n",
      u1, v1, findLCA(root, u1, v1));
      return 0;
}

出力

The LCA of node 4 and node 9 is node 2.