C++でデカルトツリーを実装する方法【アルゴリズムとサンプルコード解説】

デカルトツリー（Cartesian Tree）は、数列から構築できる二分木の一種です。木を中順走査（inorder traversal）すると元の数列がそのまま復元でき、さらに各ノードの値が子ノードの値以下になるというヒープ性質を満たします。本記事では、C++を使ってデカルトツリーを実装する方法を、アルゴリズムの解説からサンプルコード、実行結果まで詳しく紹介します。

デカルトツリーとは

デカルトツリーは、次の2つの性質を持つ二分木です。

• 中順走査すると、元の入力数列と同じ順序で要素が得られる
• 親ノードの値は、常に子ノードの値以下である（最小ヒープ性質）

この性質により、デカルトツリーは「Treap（ツリーアップ）」とも呼ばれ、範囲最小クエリ（RMQ：Range Minimum Query）などの応用にも利用されます。

構築アルゴリズム

ここでは、配列内の最小要素を探してそれを根とし、残りの左側・右側の部分配列に対して再帰的に同じ処理を繰り返すことで、デカルトツリーを構築します。

Begin
    class CarTree で関数を宣言:
      min() = 配列内の最小要素のインデックスを求める:
        if (arr[i] < min)
          min = arr[i]
          minind = i
      inorder() = 木の中順走査を行う:
        木が空ならば
          return
        inorder(node->l)
        根 node->d を出力
        inorder(node->r)
End

手順のポイント

1. min()： 指定された範囲 [s, e] 内で最小値のインデックスを線形探索で求めます。
2. buildTree()： 範囲内の最小要素を新しいノードとして作成し、その左に範囲 [s, i-1]、右に範囲 [i+1, e] の部分木を再帰的に構築して接続します。
3. inorder()： 「左部分木 → 根 → 右部分木」の順に訪問し、元の数列が復元できることを確認します。
4. show()： インデント付きで木の構造を見やすく表示します。

C++による実装例

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

// ノードの宣言
struct nod {
   int d;
   struct nod* l;
   struct nod* r;
};

class CarTree {
   public:// 関数の宣言
   nod *newNode (int);
   int min(int [], int, int);
   nod *buildTree (int [], int, int);
   void inorder (nod* node);
   void show(nod *, int);
   CarTree()
   {}
};

// 最小要素のインデックスを返す
int CarTree::min(int arr[], int s, int e) {
   int i, min = arr[s], minind = s;
   for (i = s + 1; i <= e; i++) {
      if (arr[i] < min) {
         min = arr[i];
         minind = i;
      }
   }
   return minind;
}

// デカルトツリーを構築する
nod *CarTree::buildTree (int inorder[], int s, int e) {
   if (s >e)
      return NULL;
      int i = min(inorder, s, e);
      nod *r = newNode(inorder[i]);
   if (s == e)
      return r;
      r->l = buildTree(inorder, s, i - 1);// 左の子に対して再帰呼び出し
      r->r = buildTree(inorder, i + 1, e);// 右の子に対して再帰呼び出し
      return r;
}

// 中順走査
void CarTree::inorder (struct nod* node) {
   if (node == NULL)
      return;
      inorder (node->l);
      cout<<node->d<<" ";
      inorder (node->r);
}

// 木の構造を表示する
void CarTree::show(nod *ptr, int level) {
   int i;
   if(ptr == NULL)
      return;
   if (ptr != NULL) {
      show(ptr->r, level + 1);
      cout<<endl;
      for (i = 0;i < level;i++)
         cout<<" ";
         cout<<ptr->d;
         show(ptr->l, level + 1);
   }
}

// 新しいノードを作成する
nod *CarTree::newNode (int d) {
   nod* t = new nod;
   t->d = d;
   t->l = NULL;
   t->r = NULL;
   return t;
}

int main() {
   CarTree ct;
   int i, n;
   cout<<"挿入する要素数を入力してください: ";
   cin>>n;
   int a[n];
   for (i = 0; i < n; i++) {
      cout<<"要素 "<<i + 1<<" : ";
      cin>>a[i];
   }
   nod *r = ct.buildTree(a, 0, n - 1);
   cout<<"デカルトツリーの構造: "<<endl;
   ct.show(r,1);
   cout<<endl;
   cout<<"\n 木の中順走査の結果 \n"<<endl;
   ct.inorder(r);
   cout<<endl;
   return 0;
}

実行結果

挿入する要素数を入力してください: 10
要素 1 : 10
要素 2 : 30
要素 3 : 20
要素 4 : 40
要素 5 : 50
要素 6 : 70
要素 7 : 60
要素 8 : 80
要素 9 : 100
要素 10 : 112
デカルトツリーの構造:
112
100
80
60
70
50
40
20
30
10
木の中順走査の結果
10 30 20 40 50 70 60 80 100 112

動作の解説

入力された数列 {10, 30, 20, 40, 50, 70, 60, 80, 100, 112} のうち、最小値は先頭の 10 です。したがって 10 が根となり、右側の部分配列 {30, 20, 40, 50, 70, 60, 80, 100, 112} に対して同様の処理が再帰的に適用されます。

次に最小値は 20、続いて 40、50、60、70、80、100、112 と続き、結果として右方向に伸びた木が構築されます。

最後の中順走査では「10 30 20 40 50 70 60 80 100 112」と出力され、元の入力順序が正しく復元されていることが確認できます。これこそが、デカルトツリーの重要な性質の1つです。

計算量について

この実装では、再帰の各ステップで最小要素の探索に O(n) の計算量が必要となるため、全体の構築時間は最悪の場合 O(n²) になります。より効率的に構築したい場合は、スタックを活用した線形時間 O(n) の構築アルゴリズムも知られているので、大規模なデータを扱う際にはそちらの採用も検討するとよいでしょう。