BST（二分探索木）の各ノードに、より大きい値をすべて加算する方法

BST（二分探索木：Binary Search Tree）は二分木の一種で、「根の値より小さい値を持つノードがすべて左側に、大きい値を持つノードがすべて右側に配置される」という性質を持つデータ構造です。

本記事で扱うのは、そのBSTに対して「現在のノードより大きい値をすべて加算する」という古典的なアルゴリズム問題です。つまり、BST内の各ノードについて、そのノードの値より大きい値を持つすべてのノードの合計を、そのノード自身の値に足し合わせていく処理を行います。

問題の定義

与えられた二分探索木（BST）の各ノードに対して、そのノードより大きい値を持つすべてのノードの合計値を加算してください。

入力例

    10
   /  \
  5    20
 / \   / \
1   7 15  25

出力例

     70
    /  \
  82    45
  / \   / \
83  77 60  25

解説

このプログラムは、BSTを「各ノードの値 ＝ 元の値 ＋ 自分より大きい要素の総和」となる二分木へと変換します。

たとえば上記の例では、最大値である25は変更されず、その親の20には「20＋25＝45」が、さらに上の10には「10＋15＋20＋25＝70」が代入されていきます。葉に近いノードほど、より多くの上位ノードの値を引き継ぐため、結果として83や82といった大きな値になります。

解法のアプローチ：逆中間順走査

この問題を効率的に解く鍵となるのが逆中間順走査（Reverse Inorder Traversal）です。

通常の中間順走査は「左部分木 → 根 → 右部分木」の順でノードを訪問し、BSTでは昇順に値を取り出せます。一方、逆中間順走査では右部分木から先に再帰呼び出しを行うため、ノードを降順に訪問できます。

あわせて、これまで走査したノードの合計値を保持する変数を用意します。各ノードを訪問したら、次の手順で値を更新します。

1. 現在のノードの値を合計変数に加算する
2. ノードの値を、その合計値で置き換える

こうすることで、各ノードには「自分自身＋自分より大きいすべてのノードの合計」が格納されます。計算量はO(n)、空間計算量は再帰の深さに依存してO(h)（hは木の高さ）です。

C++による実装例

#include <iostream>
using namespace std;
struct node {
    int data;
    node *left;
    node *right;
};
node *newNode(int key) {
    node *temp=new node;
    temp->left=NULL;
    temp->right=NULL;
    temp->data=key;
    return temp;
}
void Inorder(node *root) {
    if(!root)
        return;
    Inorder(root->left);
    cout<<root->data<<" ";
    Inorder(root->right);
}
node *Insert(node *root,int key) {
    if(!root)
        return newNode(key);
    if(key<root->data)
        root->left=Insert(root->left,key);
    else
        root->right=Insert(root->right,key);
    return root;
}
void RevInorderAdd(node *root,int &sum) {
    if(!root)
        return;
    RevInorderAdd(root->right,sum);
    sum+=root->data;
    root->data=sum;
    RevInorderAdd(root->left,sum);
}
void AddGreater(node *root) {
    int sum=0;
    RevInorderAdd(root,sum);
}
int main() {
    /* 次のBSTを作成する
       10
       / \\
      5   20
     / \  / \\
    1  7 15  25 */
    node *root = NULL;
    root = Insert(root, 10);
    Insert(root, 20);
    Insert(root, 25);
    Insert(root, 15);
    Insert(root, 5);
    Insert(root, 7);
    Insert(root, 1);
    Inorder(root);
    cout<<endl;
    AddGreater(root);
    Inorder(root);
    cout<<endl;
    return 0;
}

まとめ

BSTの各ノードにより大きい値をすべて加算する問題は、逆中間順走査と累積和を組み合わせることで、一度の走査（O(n)）で解決できます。「降順に訪問しながら合計を保持する」という発想は、同様の累積演算が必要な他の木構造の問題にも応用できる有用なテクニックです。