C++でBSTを変換する：各キーに自身より大きいキーの合計を加算する方法

はじめに

この記事では、二分探索木(BST)を、「各ノードのキーに、そのキーより大きいすべてのキーの合計を加算した二分木」へ変換するC++プログラムを解説します。

問題の概要

入力として与えられるのは二分探索木です。私たちのタスクは、この木を、各ノードの値が「元の値 + 自分より大きいすべてのキーの合計」に置き換えられた二分木へと変換することです。

例えば、次のようなBSTを考えてみましょう。

        5
       / \
      2   13

この場合、変換後の各ノードの値は以下のようになります。

• 13 → 13(自分より大きいキーが存在しないため、そのまま)
• 5 → 5 + 13 = 18
• 2 → 2 + 5 + 13 = 20

アルゴリズムのポイント:逆中間順走査

通常のBSTでは、中間順(inorder)走査を行うとキーが昇順に訪問されます。そこで、「右 → 根 → 左」の順でノードを訪問する逆中間順(reverse inorder)走査を使うと、キーを降順に処理することができます。

降順に走査しながら、これまで訪問したノードの合計値を累積していき、その合計を現在のノードのキーに代入すれば、目的の変換が実現できます。

手順のまとめ

1. 右部分木を再帰的に走査する。
2. 現在のノードのキーを累積和に加算し、その値でノードのキーを更新する。
3. 左部分木を再帰的に走査する。

C++での実装例

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

// BSTのノード構造体
struct node {
    int key;
    struct node* left;
    struct node* right;
};

// 子を持たない新しいノードを作成
struct node* newNode(int key) {
    struct node* node = (struct node*)malloc(sizeof(struct node));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    return (node);
}

// 逆中間順でBSTを走査し、累積和を加算
void reverse_BST(struct node *root, int *sum_ptr) {
    if (root == NULL)
        return;
    reverse_BST(root->right, sum_ptr);
    // 走査しながら要素を加算
    *sum_ptr = *sum_ptr + root->key;
    root->key = *sum_ptr;
    reverse_BST(root->left, sum_ptr);
}

// 累積和を使って各ノードの値を更新
void change_greater(struct node *root) {
    int sum = 0;
    reverse_BST(root, &sum);
}

// 中間順走査の結果を出力
void printInorder(struct node* node) {
    if (node == NULL)
        return;
    printInorder(node->left);
    cout << node->key << " ";
    printInorder(node->right);
}

int main() {
    node *root = newNode(5);
    root->left = newNode(2);
    root->right = newNode(13);
    cout << "Given Tree :" << endl;
    printInorder(root);
    change_greater(root);
    cout << endl;
    cout << "Modified Tree :" << endl;
    printInorder(root);
    return 0;
}

実行結果

Given Tree :
2 5 13
Modified Tree :
20 18 13

計算量と補足

このアルゴリズムは各ノードを一度だけ訪問するため、時間計算量は O(n) です。空間計算量は再帰の深さに依存し、バランスの取れた木であれば O(log n)、最悪の場合(木が連結リスト状に偏っている場合)は O(n) となります。

また、変換後の中間順走査の結果が「20 18 13」と降順になっている点にも注目してください。これは、各ノードが「自分より大きいキーの合計」を含むように更新されたことで、もとのBSTの大小関係が反転したことを示しています。