C++でTreap（ツリープ）を実装する方法｜挿入・削除・探索の基本操作を解説

Treap（ツリープ）は、二分探索木（BST）とヒープの性質を兼ね備えたランダム化データ構造です。各ノードは「キー」と「優先度」の2つの値を持ち、キーについては二分探索木の規則（左の子 ＜ 親 ＜ 右の子）、優先度についてはヒープの規則（親の優先度 ≥ 子の優先度）が常に保たれます。優先度を乱数で決定することで木のバランスが偏りにくくなり、すべての操作を期待計算量 O(log n) で実行できます。

この記事では、C++を用いてTreapを実装し、挿入（insert）・削除（delete）・探索（search）の3つの基本操作を行うプログラムを紹介します。

使用する関数とその役割

insertNod()：キーの挿入

指定したキーを優先度とともに、Treapへ再帰的に挿入します。

root = nullptr の場合
　　新しいノードを作成して返す
挿入する値がルートのキーより小さい場合
　　左部分木に挿入する
　　ヒープの性質に違反している場合は右回転する
それ以外の場合
　　右部分木に挿入する
　　ヒープの性質に違反している場合は左回転する

searchNod()：キーの探索

指定したキーをTreap内から再帰的に探索します。

キーが存在しない場合は false を返す
キーが存在する場合は true を返す
キーがルートより小さい場合は左部分木を探索する
それ以外の場合
　　右部分木を探索する

deleteNod()：キーの削除

指定したキーをTreapから再帰的に削除します。

キーが存在しない場合は何もせず終了
キーがルートより小さい場合は左部分木へ進む
キーがルートより大きい場合は右部分木へ進む
キーが見つかった場合：
　　削除対象が葉ノードの場合
　　　　メモリを解放し、root を nullptr に更新する
　　削除対象が2つの子を持つ場合
　　　　左の子の優先度が右の子より低い場合
　　　　　　root に対して rotLeft() を呼び出し、左の子を再帰的に削除する
　　　　それ以外の場合
　　　　　　root に対して rotRight() を呼び出し、右の子を再帰的に削除する
　　削除対象が1つの子のみを持つ場合
　　　　子ノードを特定し、root を子で置き換えてメモリを解放する
結果を出力する
終了

C++による実装例

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
struct TreapNod { // ノードの宣言
   int data;
   int priority;
   TreapNod* l, *r;
   TreapNod(int d) { // コンストラクタ
      this->data = d;
      this->priority = rand() % 100;
      this->l= this->r = nullptr;
   }
};
void rotLeft(TreapNod* &root) { // 左回転
   TreapNod* R = root->r;
   TreapNod* X = root->r->l;
   R->l = root;
   root->r= X;
   root = R;
}
void rotRight(TreapNod* &root) { // 右回転
   TreapNod* L = root->l;
   TreapNod* Y = root->l->r;
   L->r = root;
   root->l= Y;
   root = L;
}
void insertNod(TreapNod* &root, int d) { // 挿入
   if (root == nullptr) {
      root = new TreapNod(d);
      return;
   }
   if (d < root->data) {
      insertNod(root->l, d);
      if (root->l != nullptr && root->l->priority > root->priority)
      rotRight(root);
   } else {
      insertNod(root->r, d);
      if (root->r!= nullptr && root->r->priority > root->priority)
      rotLeft(root);
   }
}
bool searchNod(TreapNod* root, int key) {
   if (root == nullptr)
      return false;
   if (root->data == key)
      return true;
   if (key < root->data)
      return searchNod(root->l, key);
      return searchNod(root->r, key);
}
void deleteNod(TreapNod* &root, int key) {
   // 削除対象が葉ノードの場合
   if (root == nullptr)
      return;
   if (key < root->data)
      deleteNod(root->l, key);
   else if (key > root->data)
      deleteNod(root->r, key);
      // 削除対象が2つの子を持つ場合
   else {
      if (root->l ==nullptr && root->r == nullptr) {
         delete root;
         root = nullptr;
      }
      else if (root->l && root->r) {
         if (root->l->priority < root->r->priority) {
            rotLeft(root);
            deleteNod(root->l, key);
         } else {
            rotRight(root);
            deleteNod(root->r, key);
         }
      }
      // 削除対象が1つの子のみを持つ場合
      else {
         TreapNod* child = (root->l)? root->l: root->r;
         TreapNod* curr = root;
         root = child;
         delete curr;
      }
   }
}
void displayTreap(TreapNod *root, int space = 0, int height =10) { // Treapの表示
   if (root == nullptr)
      return;
   space += height;
   displayTreap(root->l, space);
   cout << endl;
   for (int i = height; i < space; i++)
      cout << ' ';
      cout << root->data << "(" << root->priority << ")\n";
      cout << endl;
   displayTreap(root->r, space);
}
int main() {
   int nums[] = {1,7,6,4,3,2,8,9,10 };
   int a = sizeof(nums)/sizeof(int);
   TreapNod* root = nullptr;
   srand(time(nullptr));
   for (int n: nums)
      insertNod(root, n);
   cout << "Constructed Treap:\n\n";
   displayTreap(root);
   cout << "\nDeleting node 8:\n\n";
   deleteNod(root, 8);
   displayTreap(root);
   cout << "\nDeleting node 3:\n\n";
   deleteNod(root, 3);
   displayTreap(root);
   return 0;
}

実行結果

Constructed Treap:

1(12)

2(27)

3(97)

4(46)

6(75)

7(88)

8(20)

9(41)

10(25)

Deleting node 8:

1(12)

2(27)

3(97)

4(46)

6(75)

7(88)

9(41)

10(25)

Deleting node 3:

1(12)

2(27)

4(46)

6(75)

7(88)

9(41)

10(25)

※優先度は乱数によって決まるため、実行するたびに括弧内の数値や木の形状は変化します。

まとめ

Treapは、乱数による優先度を活用することで、通常の二分探索木がソート済みデータの連続挿入などで偏ってしまう問題を回避できる強力なデータ構造です。挿入・削除・探索はすべて期待計算量 O(log n) で実行でき、実装も比較的シンプルなため、競技プログラミングから実務システムまで幅広く活用されています。本記事のコードをベースに、ぜひ自分のプロジェクトでも試してみてください。