C++で二分探索木（BST）の指定範囲内にあるノード数をカウントする方法

本記事では、ノードで構成される二分探索木（BST）とある範囲が与えられたとき、その範囲に含まれるノードの個数を計算して結果を表示する方法を解説します。

二分探索木（BST）とは

二分探索木（Binary Search Tree：BST）とは、すべてのノードが以下の性質を満たす木構造のことです。

• あるノードの左部分木に含まれるキーは、その親ノードのキー以下である。
• あるノードの右部分木に含まれるキーは、その親ノードのキー以上である。

つまり、BSTはすべての部分木を「左部分木」と「右部分木」の2つのセグメントに分割でき、次のように定義できます。

left_subtree（キー） ≤ node（キー） ≤ right_subtree（キー）

この性質により、BSTでは範囲外の部分木を探索から切り捨てられるため、効率的なカウントが可能になります。

具体例

入力：

範囲：[11, 40]

出力： カウントは 5

解説： 範囲[11, 40]に含まれるノードの値は 14、19、27、31、35 の5つです。したがって、与えられた二分探索木の中には合計5つのノードが存在します。

アルゴリズムのアプローチ

このプログラムで使用するアプローチは以下の通りです。

• データ（data）、左ポインタ（left）、右ポインタ（right）を持つノード構造体を定義し、範囲を設定します。
• ユーザーが入力する新しいノードを挿入する関数を作成します。
• 指定された範囲に含まれるノードをカウントする別の関数を作成します。
• ルートがNULLの場合は0を返します（ベースケース）。
• root->data が low と high の両方に等しい場合（low == high の場合）は1を返します。
• root->data が high 以下かつ low 以上の場合は、1 + 左右の子に対する再帰呼び出しの結果を返します。
• それ以外で root->data が low より小さい場合は、右の子に対して再帰的にカウント関数を呼び出します。
• それ以外の場合は、左の子に対して再帰的にカウント関数を呼び出します。

ポイントは、現在のノードが範囲より小さい場合は右部分木だけを、範囲より大きい場合は左部分木だけを探索すればよいという点です。これにより無駄な探索を省き、計算量を抑えられます。

C++での実装例

#include<iostream>
using namespace std;

// BSTのノード
struct node{
    int data;
    struct node* left, *right;
};

// 新しいノードを作成するユーティリティ関数
node *newNode(int data){
    node *temp = new node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return (temp);
}

int findcount(node *root, int low, int high){
    // ベースケース
    if (!root){
        return 0;
    }
    if (root->data == high && root->data == low){
        return 1;
    }
    // 現在のノードが範囲内の場合、カウントに含め、
    // 左右の子に対して再帰的に処理する
    if (root->data <= high && root->data >= low){
        return 1 + findcount(root->left, low, high) +
        findcount(root->right, low, high);
    }
    else if (root->data < low){
        return findcount(root->right, low, high);
    }
    // それ以外は左の子に対して再帰的に処理する
    else{
        return findcount(root->left, low, high);
    }
}

// main関数
int main(){
    // 上記の図に示したBSTを構築する
    node *root = newNode(27);
    root->left = newNode(14);
    root->right = newNode(35);
    root->left->left = newNode(10);
    root->left->right = newNode(19);
    root->right->left = newNode(31);
    root->right->right = newNode(42);
    int low = 10;
    int high = 50;
    cout << "Count of nodes between [" << low << ", " << high
    << "] is " << findcount(root, low, high);
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

Count of nodes between [10, 50] is 7

この例では、範囲[10, 50]に含まれるノードは 10、14、19、27、31、35、42 の7つであるため、正しく7が出力されています。

まとめ

BSTの性質を利用することで、指定範囲内のノード数を効率的にカウントできます。範囲外の値を持つノードでは片側の部分木のみを再帰的に探索するため、全ノードを走査する場合と比べて無駄な処理を削減できるのが大きな利点です。時間計算量は平衡なBSTの場合 O(log n + k)（kは範囲内のノード数）、最悪の場合は O(n) となります。