C++で二分探索木（BST）からCeiling（天井）とFloor（床）を求める方法

本記事では、二分探索木（BST）からCeiling（天井）値とFloor（床）値を求める方法について解説します。

まず用語を整理しておきましょう。あるキーに対する「Ceiling」とは、そのキー以上の値の中で最小の要素を指し、「Floor」とはそのキー以下の値の中で最大の要素を指します。

応用例：メモリ管理システム

例えば、メモリ管理システムを構築することを考えてみます。空きメモリブロック（フリーノード）がBST上に配置されており、入力された要求サイズに対して最適なフィット（ベストフィット）を見つけたい場面です。このとき、ツリーを降下しながら「キー値より大きい最小のデータ」を追跡していくことになります。

Ceiling値を求めるアルゴリズム

ツリーを降下しながら、キー値より大きい最小のデータを探す場合、各ノードにおいて次の3つのケースが考えられます。

• ルートのキーが探索キーと一致する場合： ルートの値がそのままCeiling値となります。
• ルートのデータがキーより小さい場合（root.key < key）： Ceiling値は左部分木には存在しないため、右部分木へ進み、問題の範囲を絞り込みます。
• ルートのデータがキーより大きい場合（root.key > key）： ルート自体がCeiling候補になります。ただし、左部分木の中にキーより大きく、かつルートより小さい値を持つノードが存在する可能性もあるため、左部分木も探索します。より良い候補が見つからなければ、ルートの値がCeiling値となります。

動作イメージ

例えば、次のようなBSTを考えます。

            8
          /   \
         4     12
        / \    / \
       2   6  10  14

このツリーでは、0・1・2のCeilingは2、3・4のCeilingは4、5・6のCeilingは6、というように求まっていきます。また、15のようにツリー内のどの値よりも大きいキーに対しては、Ceilingが存在しないため -1 を返します。

ここではCeiling関数のみを実装しますが、比較条件を少し修正するだけで、同様のロジックでFloor値も取得できます。

C++による実装例

#include <iostream>
using namespace std;

class node {
    public:
    int key;
    node* left;
    node* right;
};

node* getNode(int key) {
    node* newNode = new node();
    newNode->key = key;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

int ceiling(node* root, int num) {
    if (root == NULL)
        return -1;
    if (root->key == num)
        return root->key;
    if (root->key < num)
        return ceiling(root->right, num);
    int ceil = ceiling(root->left, num);
    return (ceil >= num) ? ceil : root->key;
}

int main() {
    node* root = getNode(8);
    root->left = getNode(4);
    root->right = getNode(12);
    root->left->left = getNode(2);
    root->left->right = getNode(6);
    root->right->left = getNode(10);
    root->right->right = getNode(14);

    for (int i = 0; i < 16; i++)
        cout << i << "\tCeiling: " << ceiling(root, i) << endl;
}

出力結果

0	Ceiling: 2
1	Ceiling: 2
2	Ceiling: 2
3	Ceiling: 4
4	Ceiling: 4
5	Ceiling: 6
6	Ceiling: 6
7	Ceiling: 8
8	Ceiling: 8
9	Ceiling: 10
10	Ceiling: 10
11	Ceiling: 12
12	Ceiling: 12
13	Ceiling: 14
14	Ceiling: 14
15	Ceiling: -1

計算量について

このアルゴリズムの時間計算量は O(h) です（hはツリーの高さ）。各ステップで探索対象が左右いずれかの部分木に限定されるため、バランスの取れたBSTであれば O(log n)、最悪ケース（線形に偏ったツリー）では O(n) となります。メモリ管理のような頻繁な検索が必要なシステムでは、ツリーのバランスを保つことが性能面で重要になります。