【C++】二分探索木で最小共通祖先（LCA）を求めるプログラムの解説

二分木とは、各ノードが最大で2つの子ノード（左の子と右の子）を持つことのできる木構造のデータ構造です。本記事では、二分探索木（BST）において、指定した2つのノードの最小共通祖先（Lowest Common Ancestor：LCA）を求めるC++プログラムを解説します。

最小共通祖先とは、2つのノードn1とn2の両方の子孫となるノードのうち、最も深い位置にあるノードのことです。二分探索木では「左の子 ＜ 親 ＜ 右の子」という性質が成り立つため、この性質を利用することでLCAを効率的に求めることができます。

アルゴリズム

LCAを求める手順は以下の通りです。

1. データd、左の子ポインタl、右の子ポインタrを持つ構造体nを宣言する。
2. 新しいノードを生成する関数newnode()を作成する。
3. 二分探索木の最小共通祖先を求める関数LCA()を呼び出す。
   ・ノードn1とn2は木の中に存在すると仮定する。
   ・rootがNULLの場合はNULLを返す。
   ・rootがNULLでない場合、次の2つのケースに分かれる。
     a) n1とn2がどちらもrootより小さい場合 → LCAは左の部分木に存在する。
     b) n1とn2がどちらもrootより大きい場合 → LCAは右の部分木に存在する。
   ・上記以外の場合、現在のrootがLCAとなる。

サンプルコード

#include<iostream>
using namespace std;
struct n {
   int d;
   struct n* l, *r;
}*p = NULL;
struct n* newnode(int d) {
   p = new n;
   p->d= d;
   p->l = p->r = NULL;
   return(p);
}
struct n *LCA(struct n* root, int n1, int n2) {
   if (root == NULL)
      return NULL;
   if (root->d > n1 && root->d > n2)
      return LCA(root->l, n1, n2);
   if (root->d< n1 && root->d < n2)
      return LCA(root->r, n1, n2);
      return root;
}
int main() {
   n* root = newnode(9);
   root->l = newnode(7);
   root->r = newnode(10);
   root->l->l = newnode(6);
   root->r->l= newnode(8);
   root->r->r = newnode(19);
   root->r->l->r = newnode(4);
   root->r->r->r = newnode(20);
   int n1 = 20, n2 = 4;
   struct n *t = LCA(root, n1, n2);
   cout<<"Lowest Common Ancestor of 20 and 4 is:" <<t->d<<endl;
   n1 = 7, n2 = 6;
   t = LCA(root, n1, n2);
   cout<<"Lowest Common Ancestor of 7 and 6 is:" << t->d<<endl;
}

出力結果

Lowest Common Ancestor of 20 and 4 is:9
Lowest Common Ancestor of 7 and 6 is:7

コードの解説

このプログラムのポイントは、LCA関数が二分探索木の性質を活かして再帰的に探索を進める点です。

• root->d > n1 かつ root->d > n2 の場合：2つのノードがともに左の部分木に存在するため、左へ再帰的に探索を進めます。
• root->d < n1 かつ root->d < n2 の場合：2つのノードがともに右の部分木に存在するため、右へ再帰的に探索を進めます。
• それ以外の場合：n1とn2がrootを挟んで左右に分かれる（あるいはどちらかがrootと一致する）ため、現在のrootが最小共通祖先となります。

例えば、20と4のLCAを求める場合、root（9）に対して20は大きく、4は小さいため、2つのノードはrootを挟んで左右に分かれています。このため探索は即座に終了し、rootである9がLCAとして返されます。

計算量

• 時間計算量：O(h)。hは木の高さです。平衡な二分探索木であればO(log n)に抑えられます。
• 空間計算量：O(h)。再帰呼び出しに伴うスタック領域が必要です。