二分探索木（BST）の全ノードに、それより大きい値の合計を加算するアルゴリズム

本記事では、二分探索木（BST）の各ノードに対して、「そのノードより大きい値を持つすべてのノードの値の合計」を加算して更新するという興味深い問題を取り上げます。処理前後の木は、以下の図のように変化します。

例えば、元の木で値 50 のノードは、それより大きい値（60、70、80）の合計 210 を加算して 260 に更新されます。一方、最大値である 80 のノードは、それより大きい値が存在しないため 80 のまま変わりません。

アルゴリズムの考え方

この問題は、通常の通り順（inorder）走査を逆にした「右部分木 → 根 → 左部分木」の順序で木を走査することで、効率的に解くことができます。この順序で走査すると、ノードが降順に訪問されるため、走査しながら累積和 sum を更新していくだけで、各ノードに「自分より大きい値の合計」を加算した結果を代入できます。

bstUpdate(root, sum) の擬似コードは以下のとおりです。

Begin
    if root is null, then stop
    bstUpdate(right of root, sum)
    sum := sum + value of root
    update root value using sum
    bstUpdate(left of root, sum)
End

C++による実装例

#include<iostream>
using namespace std;
class Node {
    public:
        int data;
        Node *left, *right;
    };
    Node *getNode(int item) {
        Node *newNode = new Node();
        newNode->data = item;
        newNode->left = newNode->right = NULL;
        return newNode;
}
void updateBST(Node *root, int *sum) {
    if (root == NULL)
        return;
    updateBST(root->right, sum); // 右部分木を更新
    *sum = *sum + root->data;
    root->data = *sum; // 根のデータを更新
    updateBST(root->left, sum); // 左部分木を更新
}
void BSTUpdate(Node *root) {
    int sum = 0;
    updateBST(root, &sum);
}
void inorder(Node *root) {
    if (root != NULL) {
        inorder(root->left);
        cout<<root->data<<" ";
        inorder(root->right);
    }
}
Node* insert(Node* node, int data) {
    if (node == NULL)
        return getNode(data);
    if (data <= node->data) // 左へ
        node->left = insert(node->left, data);
    else // 右へ
        node->right = insert(node->right, data);
    return node;
}
int main() {
    int data[] = {50, 30, 20, 40, 70, 60, 80};
    int n = sizeof(data)/sizeof(data[0]);
    Node *root = NULL;
    for(int i = 0; i < n; i++) {
        root = insert(root, data[i]);
    }
    BSTUpdate(root);
    inorder(root);
}

実行結果

350 330 300 260 210 150 80

この出力は、更新後の木を通り順（inorder）走査した結果です。元の木の最小値 20 が最大値 350 に、最大値 80 がそのまま 80 になっていることが確認できます。

計算量

時間計算量：O(n)

各ノードを一度ずつ訪問するため、ノード数 n に対して線形時間で処理が完了します。

空間計算量：O(h)

再帰呼び出しの深さは木の高さ h に依存します。平衡な二分探索木であれば O(log n)、最悪の場合（木が一直線に偏っている場合）は O(n) となります。