C++で二分探索木のバランスを取る方法｜中順走査による再構築アルゴリズム

問題概要

二分探索木（BST）が与えられたとき、同じノード値を持つ「バランスの取れた二分探索木」を構築することを考えます。二分探索木がバランスしているとは、すべてのノードにおいて、左右の部分木の深さの差が1を超えないことと定義されます。条件を満たす結果が複数存在する場合は、そのいずれかを返して構いません。

例えば、次のような片寄った木が与えられたとします。

解き方のアプローチ

この問題を解く鍵となるのは、「二分探索木を中順走査（in-order traversal）すると、ノードの値が昇順にソートされた配列が得られる」という性質です。ソート済みの配列から毎回中央の要素を根として選び、再帰的に左右の部分木を構築すれば、自然とバランスの取れたBSTが得られます。

具体的な手順は以下の通りです。

• inorder() メソッドを定義し、中順走査の結果（昇順ソート済みの値）を配列に格納する

• construct() メソッドを定義する。引数には範囲を示す low と high を渡す

• low > high の場合は null を返す（再帰のベースケース）

• 中央インデックスを mid = low + (high - low) / 2 として求める

• arr[mid] を値とする新しいノードを作成し、これを root とする

• root の左部分木は construct(low, mid - 1) の結果、右部分木は construct(mid + 1, high) の結果とする

• root を返す

• メイン処理では inorder() を呼び出した後、construct(0, 配列のサイズ - 1) を返す

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
    public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data){
        val = data;
        left = right = NULL;
    }
};
void insert(TreeNode **root, int val){
    queue<TreeNode*> q;
    q.push(*root);
    while(q.size()){
        TreeNode *temp = q.front();
        q.pop();
        if(!temp->left){
            if(val != NULL)
                temp->left = new TreeNode(val);
            else
                temp->left = new TreeNode(0);
            return;
        }else{
            q.push(temp->left);
        }
        if(!temp->right){
            if(val != NULL)
                temp->right = new TreeNode(val);
            else
                temp->right = new TreeNode(0);
            return;
        }else{
            q.push(temp->right);
        }
    }
}
TreeNode *make_tree(vector<int> v){
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i<v.size(); i++){
        insert(&root, v[i]);
    }
    return root;
}
void tree_level_trav(TreeNode*root){
    if (root == NULL) return;
    cout << "[";
    queue<TreeNode *> q;
    TreeNode *curr;
    q.push(root);
    q.push(NULL);
    while (q.size() > 1) {
        curr = q.front();
        q.pop();
        if (curr == NULL){
            q.push(NULL);
        } else {
            if(curr->left)
                q.push(curr->left);
            if(curr->right)
                q.push(curr->right);
            if(curr->val == 0 || curr == NULL){
                cout << "null" << ", ";
            }else{
                cout << curr->val << ", ";
            }
        }
    }
    cout << "]"<<endl;
}
class Solution {
public:
    vector <int> arr;
    void inorder(TreeNode* node){
        if(!node || node->val == 0) return;
        inorder(node->left);
        arr.push_back(node->val);
        inorder(node->right);
    }
    TreeNode* construct(int low, int high){
        if(low > high) return NULL;
        int mid = low + (high - low) / 2;
        TreeNode* root = new TreeNode(arr[mid]);
        root->left = construct(low, mid - 1);
        root->right = construct(mid + 1, high);
        return root;
    }
    TreeNode* balanceBST(TreeNode* root) {
        inorder(root);
        return construct(0, (int)arr.size() - 1);
    }
};
main(){
    vector<int> v = {1,NULL,2,NULL,NULL,NULL,3,NULL,NULL,NULL,NULL,NULL,NULL,NULL,4};
    TreeNode *root = make_tree(v);
    Solution ob;
    tree_level_trav(ob.balanceBST(root));
}

入力

[1,NULL,2,NULL,NULL,NULL,3,NULL,NULL,NULL,NULL,NULL,NULL,NULL,4]

出力

[2, 1, 3, 4]

計算量の分析

このアルゴリズムの計算量は以下の通りです。

• 時間計算量：O(n) — 中順走査で全ノードを一度訪問し、木の再構築でも各ノードを一度だけ処理するためです。

• 空間計算量：O(n) — ソート済みの値を格納する配列と、再帰呼び出しのスタック領域が必要になります。

まとめ

不平衡な二分探索木をバランスさせるには、まず中順走査によって昇順ソート済みの値の配列を取得し、その中央要素を根として再帰的に木を組み立て直すのが最もシンプルかつ確実な方法です。この手法を使えば、すべてのノードで左右の部分木の高さの差が1以内に収まる平衡なBSTを、線形時間 O(n) で効率的に構築できます。