二分木から最大のBST部分木を見つける方法 - C++実装解説

問題の概要

この記事では、二分木(BT)が与えられたときに、その中に含まれる最大のBST(二分探索木)部分木を見つけるという問題を解説します。

二分木とは、データを格納するために用いられる特殊なデータ構造で、「各ノードが最大2つの子ノードを持つ」という条件を満たす木構造です。

二分探索木(BST)は、すべてのノードが次の性質を満たす木のことです。

• 左部分木のキー値は、親(ルート)ノードのキー値よりも小さい。

• 右部分木のキー値は、親(ルート)ノードのキー値以上である。

具体例で問題を確認してみましょう。

入力:

出力:3

説明:

木全体がBSTとして成立しています。

解法アプローチ1:各ノードでBST判定を行うシンプルな方法

最も単純な解き方は、木を走査して各ノードごとに「その部分木がBSTかどうか」をチェックし、BSTとなっている最大の部分木のサイズを返す方法です。

実装例

この解法の動作を示すプログラムは以下の通りです。

#include<bits/stdc++.h>
using namespace std;
class node{
    public:
    int data;
    node* left;
    node* right;
    node(int data){
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
int findTreeSize(node* node) {
    if (node == NULL)
        return 0;
    else
        return(findTreeSize(node->left) + findTreeSize(node->right) + 1);
}
int isBSTree(struct node* node) {
    if (node == NULL)
        return 1;
    if (node->left != NULL && node->left->data > node->data)
        return 0;
    if (node->right != NULL && node->right->data < node->data)
        return 0;
    if (!isBSTree(node->left) || !isBSTree(node->right))
        return 0;
    return 1;
}
int findlargestBSTSize(struct node *root) {
    if (isBSTree(root)){
        return findTreeSize(root);
    }
    else
        return max(findlargestBSTSize(root->left), findlargestBSTSize(root->right));
}
int main() {
    node *root = new node(5);
    root->left = new node(2);
    root->right = new node(8);
    root->left->left = new node(1);
    root->left->right = new node(4);
    cout<<"The size of the largest possible BST is "<<findlargestBSTSize(root);
    return 0;
}

出力

The size of the largest possible BST is 5

解法アプローチ2:ボトムアップ方式による効率的な方法

もう一つの解法は、木を葉側(下)から根方向(上)へ向かって走査し、子ノードの情報をもとにBSTかどうかを判定していく方法です。この際、各ノードについて次の情報を追跡します。

• そのノードを根とする木がBSTであるかどうか。

• 左部分木内の最大要素の値。

• 右部分木内の最小要素の値。これらの値は、現在のノードとの比較によってBST判定に利用されます。

あわせて、現在のBSTのサイズと照らし合わせながら、最大のBSTサイズを更新していきます。

実装例

#include<bits/stdc++.h>
using namespace std;
class node{
    public:
    int data;
    node* left;
    node* right;
    node(int data){
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
int findlargestBSTSizeRec(node* node, int *minValRsubTree, int *maxValLsubTree, int *maxBSTSize, bool *isBSTree) {
    if (node == NULL){
        *isBSTree = true;
        return 0;
    }
    int min = INT_MAX;
    bool left_flag = false;
    bool right_flag = false;
    int leftSubtreeSize,rightSubTreeSize;
    *maxValLsubTree = INT_MIN;
    leftSubtreeSize = findlargestBSTSizeRec(node->left, minValRsubTree, maxValLsubTree, maxBSTSize, isBSTree);
    if (*isBSTree == true && node->data > *maxValLsubTree)
        left_flag = true;
    min = *minValRsubTree;
    *minValRsubTree = INT_MAX;
    rightSubTreeSize = findlargestBSTSizeRec(node->right, minValRsubTree, maxValLsubTree, maxBSTSize, isBSTree);
    if (*isBSTree == true && node->data < *minValRsubTree)
        right_flag = true;
    if (min < *minValRsubTree)
        *minValRsubTree = min;
    if (node->data < *minValRsubTree)
        *minValRsubTree = node->data;
    if (node->data > *maxValLsubTree)
        *maxValLsubTree = node->data;
    if(left_flag && right_flag){
        if (leftSubtreeSize + rightSubTreeSize + 1 > *maxBSTSize)
            *maxBSTSize = (leftSubtreeSize + rightSubTreeSize + 1);
        return (leftSubtreeSize + rightSubTreeSize + 1);
    }
    else{
        *isBSTree = false;
        return 0;
    }
}
int findlargestBSTSize(node* node){
    int min = INT_MAX;
    int max = INT_MIN;
    int largestBSTSize = 0;
    bool isBST = false;
    findlargestBSTSizeRec(node, &min, &max, &largestBSTSize, &isBST);
    return largestBSTSize;
}
int main(){
    node *root = new node(5);
    root->left = new node(2);
    root->right = new node(8);
    root->left->left = new node(1);
    root->left->right = new node(4);
    cout<<"The Size of the largest BST is "<<findlargestBSTSize(root);
    return 0;
}

出力

The Size of the largest BST is 5

まとめ

アプローチ1は直感的で理解しやすい反面、各ノードでBST判定とサイズ計算を繰り返すため、最悪計算量はO(n²)になります。一方、アプローチ2では子ノードの情報を一度の走査で集約できるため、木全体をO(n)で処理でき、大規模な木に対しても効率的に動作します。用途や入力サイズに応じて、適切な手法を選択するとよいでしょう。