C++でRMQ（区間最小値クエリ）を使って二分木のLCA（最小共通祖先）を求める方法

概念

本記事では、根付き木における2つのノードのLCA（最小共通祖先）を求める問題を、RMQ（区間最小値クエリ）の問題へ帰着させることで解く手法について解説します。

用語の整理

根付き木Tにおいて、2つのノードaとbの最小共通祖先（Lowest Common Ancestor：LCA）とは、aとbの両方を子孫として持つノードのうち、根から最も遠い位置にあるノードを指します。

例えば、下図のように、ノードDとノードIのLCAはノードBになります。

LCA問題はさまざまなアプローチで解くことが可能で、それぞれ時間計算量や空間計算量が異なります。

区間最小値クエリ（Range Minimum Query：RMQ）は、配列に対して適用されるクエリで、指定された2つのインデックスの間で最小値となる要素の位置を求めるものです。RMQにも複数の解法がありますが、本記事ではセグメント木を用いたアプローチを取り上げます。セグメント木では前処理にO(n)、区間最小値クエリ1回あたりO(log n)の時間がかかり、セグメント木を保持するために必要な追加の空間計算量はO(n)となります。

LCAからRMQへの帰着

この考え方では、根から木全体をオイラーツアー（「鉛筆を離さずに一筆で巡る」ような巡回）で訪問します。これは先行順（行き順）巡回の特徴を持つDFS（深さ優先探索）の一種です。

重要な観察 ― 上図を見ると、ノードDとノードIのLCAはノードBです。これは、木TをDFSで探索したときに、Dの訪問からIの訪問までの間に出現するノード群の中で、根に最も近いノードがLCAになっていることを意味します。この観察こそが帰着の鍵となります。言い換えれば、オイラーツアーにおいてaとbの出現（どの出現ペアでもよい）の間に現れるノードのうち、レベル（深さ）が最小で、かつそのレベルにおいて唯一存在するノードがLCAであるということです。

実装には次の3つの配列が必要です。

• Tのオイラーツアーの順に訪問したノードを格納する配列

• オイラーツアーで訪問した各ノードのレベルを格納する配列

• 各ノードがオイラーツアーで最初に出現するインデックスを格納する配列（どの出現でもよいですが、ここでは最初の出現を記録します）

アルゴリズムの手順

• 木に対してオイラーツアーを実行し、euler配列・level配列・first occurrence配列を埋めます。

• first occurrence配列を使って2つのノードに対応するインデックスを取得します。これらがlevel配列上のクエリ範囲の両端となり、この範囲に対してRMQアルゴリズムで最小値を求めます。

• アルゴリズムが範囲内の最小レベルのインデックスを返したら、そのインデックスをオイラーツアー配列に適用して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.

実行すると、「ノード4とノード9のLCAはノード2である」という結果が出力されます。これは図の例とも一致しており、ノード4（D）とノード9（I）の共通祖先の中で最も根から遠いノードがノード2（B）であることを示しています。