C++で通常のBSTを平衡BST（平衡二分探索木）に変換する方法

この記事では、C++を使って通常の二分探索木（BST）を平衡二分探索木（Balanced BST）に変換するプログラムについて詳しく解説します。

ここでは、左または右に偏った（スキューした）二分探索木が与えられることを想定します。偏ったBSTは、実質的に連結リストと同じ状態になり、検索・挿入・削除の計算量が O(n) まで悪化してしまいます。これを一定の手順に従って平衡な形に変換することで、計算量を O(log n) に戻すことができます。

変換の基本的な考え方

偏ったBSTを平衡BSTに変換するには、以下の2段階の手順を用います。

1. 中順走査（Inorder Traversal）でノードを収集する： BSTの中順走査は必ず昇順のソート済み順序でノードを訪問するため、その結果を配列（vector）に保存すると、ソート済みのノード列が得られます。
2. 中央の要素を根として再帰的に木を再構築する： ソート済み配列の中央の要素を根とし、その左右の部分配列からそれぞれ左部分木・右部分木を再帰的に構築します。これにより、左右の高さのバランスが取れたBSTが完成します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;

// 木のノード構造体
struct Node {
    int data;
    Node* left, *right;
};

// 木を中順走査し、ノードポインタを vector に格納する
void store_nodes(Node* root, vector<Node*> &nodes) {
    if (root == NULL)
        return;
    store_nodes(root->left, nodes);
    nodes.push_back(root);
    store_nodes(root->right, nodes);
}

// ソート済みノード列から平衡二分木を構築する
Node* construct_tree(vector<Node*> &nodes, int start, int end) {
    if (start > end)
        return NULL;
    // 中央の要素を根にする
    int mid = (start + end) / 2;
    Node* root = nodes[mid];
    root->left = construct_tree(nodes, start, mid - 1);
    root->right = construct_tree(nodes, mid + 1, end);
    return root;
}

// バランスの取れていないBSTを平衡BSTへ変換する
Node* buildTree(Node* root) {
    // 与えられたBSTのノードをソート済みの順序で格納
    vector<Node *> nodes;
    store_nodes(root, nodes);
    int n = nodes.size();
    return construct_tree(nodes, 0, n - 1);
}

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

// 先順走査（Preorder Traversal）を実行する
void preOrder(Node* node) {
    if (node == NULL)
        return;
    printf("%d ", node->data);
    preOrder(node->left);
    preOrder(node->right);
}

int main() {
    // 左に偏ったBSTを作成
    Node* root = newNode(10);
    root->left = newNode(8);
    root->left->left = newNode(7);
    root->left->left->left = newNode(6);
    root->left->left->left->left = newNode(5);

    // 平衡BSTへ変換
    root = buildTree(root);

    printf("平衡BSTの先順走査結果 : \n");
    preOrder(root);
    return 0;
}

実行結果

平衡BSTの先順走査結果 :
7 5 6 8 10

コードのポイント解説

1. store_nodes 関数

この関数は木を中順走査（左 → 根 → 右）します。BSTの性質上、この順序で訪問するとノードは必ず昇順に並ぶため、vector にはソート済みのノードポインタが格納されます。

2. construct_tree 関数

ソート済み配列の (start + end) / 2 番目の要素を根に選ぶことで、左右の部分木に含まれるノード数の差を最小限に抑えます。これを再帰的に繰り返すことで、高さのバランスが取れたBSTが構築されます。

3. 計算量

• 時間計算量： 中順走査に O(n)、木の再構築にも O(n) かかるため、全体で O(n) です。
• 空間計算量： ノードポインタを一時的に保存するため、O(n) の追加メモリが必要です。

まとめ

偏ったBSTは検索効率が連結リスト並みに低下してしまうため、実用上は平衡化が重要です。本記事で紹介した「中順走査でソート済み配列を作成 → 中央要素を根として再帰的に再構築」という手法は、シンプルでありながら確実に平衡BSTを得られる定番のアルゴリズムです。AVL木や赤黒木のような自己平衡化データ構造を使わない場合でも、この方法で既存のBSTを一度だけ平衡化できます。