C++で区間木（Interval Tree）を実装する方法｜アルゴリズムとサンプルコード解説

区間木（インターバルツリー、Interval Tree）は、区間を格納するために設計された順序付き木構造のデータ構造です。最大の特徴は、任意の区間や点と重なるすべての区間を効率的に検索できる点にあります。本記事では、C++による区間木の実装方法を、アルゴリズムの解説とサンプルコード、実行結果とあわせて紹介します。

アルゴリズム

挿入操作（insert）

開始
    関数 insert() は新しいノードを木に挿入する：
        木が空の場合、新しいノードが根となる。
        根の区間の下限値（low）を取得する。
        新しい区間の下限値が根の下限値より小さい場合、左部分木へ挿入する。
        それ以外の場合、右部分木へ挿入する。
        必要に応じて、祖先ノードの max 値を更新する。
終了

探索操作（intervalFind）

開始
    関数 intervalFind() は与えられた区間 i を区間木から探索する：
        木が空の場合は null を返す。
        与えられた区間が根の区間と重なる場合、根の区間を返す。
        根に左の子が存在し、その max 値が与えられた区間の下限値以上であれば、
            左部分木内の区間と重なる可能性があるため、左部分木を探索する。
        それ以外の場合、右部分木だけを探索すればよい。
終了

ポイントは、各ノードが「自分とその部分木に含まれる区間の上限値の最大値（max）」を保持していることです。この max 値を利用することで、重なり得る区間が存在しない部分木の探索を丸ごと省略でき、高速な検索が可能になります。

サンプルコード

#include <iostream>
using namespace std;

// 区間を表す構造体
struct Interval {
    int l, h;
};

// 区間木のノードを表す構造体
struct ITNod {
    Interval *i;
    int max;
    ITNod *l, *r;
};

// 新しいノードを作成する
ITNod *newNode(Interval i) {
    ITNod *t = new ITNod;
    t->i = new Interval(i);
    t->max = i.h;
    t->l = t->r = NULL;
    return t;
}

// ノードを木に挿入する
ITNod *insert(ITNod *r, Interval i) {
    if (r == NULL)
        return newNode(i);
    int l = r->i->l;
    if (i.l < l)
        r->l = insert(r->l, i);
    else
        r->r = insert(r->r, i);
    if (r->max < i.h)
        r->max = i.h;
    return r;
}

// 2つの区間が重なるかどうかを判定する
bool Overlap(Interval i1, Interval i2) {
    if (i1.l <= i2.h && i2.l <= i1.h)
        return true;
    return false;
}

// 指定した区間と重なる区間を探索する
Interval *intervalFind(ITNod *root, Interval i) {
    if (root == NULL)
        return NULL;
    if (Overlap(*(root->i), i))
        return root->i;
    if (root->l != NULL && root->l->max >= i.l)
        return intervalFind(root->l, i);
    return intervalFind(root->r, i);
}

// 中間順巡回で木の内容を表示する
void inorder(ITNod *root) {
    if (root == NULL)
        return;
    inorder(root->l);
    cout << "[" << root->i->l << ", " << root->i->h << "]" << " max = " << root->max << endl;
    inorder(root->r);
}

int main(int argc, char **argv) {
    Interval ints[] = { { 5, 20 }, { 6, 7 }, { 3, 4 }, { 67, 26 }, { 3, 4 } };
    int n = sizeof(ints) / sizeof(ints[0]);
    ITNod *root = NULL;
    for (int i = 0; i < n; i++)
        root = insert(root, ints[i]);
    cout << "構築した区間木の中間順巡回の結果：\n";
    inorder(root);
    Interval x = { 7, 6 };
    cout << "\n区間 [" << x.l << "," << x.h << "] を検索します";
    Interval *res = intervalFind(root, x);
    if (res == NULL)
        cout << "\n重なる区間は見つかりませんでした";
    else
        cout << "\n[" << res->l << ", " << res->h << "] と重なっています";
}

コードの解説

• Interval 構造体： 区間の下限値 l と上限値 h を保持します。
• ITNod 構造体： 区間へのポインタ、部分木内の上限値の最大値 max、左右の子ノードへのポインタを持ちます。
• insert 関数： 二分探索木と同様に、区間の下限値を比較基準として再帰的に挿入を行い、戻りつつ max 値を更新します。
• Overlap 関数： 2つの区間が共通部分を持つかどうかを判定します。
• intervalFind 関数： 左部分木の max 値と検索対象の下限値を比較し、探索不要な部分木を枝刈りしながら効率的に検索します。

実行結果

構築した区間木の中間順巡回の結果：
[3, 4] max = 4
[3, 4] max = 4
[5, 20] max = 26
[6, 7] max = 26
[67, 26] max = 26

区間 [7,6] を検索します
[5, 20] と重なっています

このように、区間木を使うことで「指定した区間と重なる区間の検索」を効率的に行えます。カレンダーの予定管理やIPアドレス範囲の照合など、区間を扱うさまざまな場面で活用できるデータ構造です。