Javaで平衡二分探索木（BST）から指定した合計値になるペアを検索する方法

概要

平衡二分探索木（Balanced BST）と目標となる合計値（target sum）が与えられたとき、その合計値に等しくなるノードのペアが木の中に存在するかどうかを判定する関数を作成します。ペアが存在すれば true を返し、存在しなければ false を返します。

この問題では、期待される時間計算量は O(n) であり、使用できる追加の補助記憶域は O(Log n) までとされています。また、二分探索木自体への変更（ノードの追加・削除・構造の書き換えなど）は一切許されない点にも注意が必要です。

ここで重要なポイントとして、平衡BSTの高さは常に O(Log n) であるという性質があります。この性質が後述の効率的な解法の基礎となります。

例：

解法アプローチ

1. 全探索（Brute Force）

最も単純な方法は、BST内のすべてのノードのペアを順番に調べ、その合計が X と一致するかを確認することです。この方法の時間計算量は O(n²) となり、大規模な木に対しては非効率です。

2. 中間順走査（Inorder Traversal）を利用した方法

より優れた解法は、補助配列を作成し、BSTの中間順走査（Inorder Traversal）の結果をその配列に格納する方法です。BSTの中間順走査は必ずソート済みのデータを生成するため、得られる配列は昇順にソートされた状態になります。

ソート済み配列が手に入れば、いわゆる「Two Pointer（双方向ポインタ）」テクニックを使って、配列の先頭と末尾から中央に向かってポインタを移動させながらペアを探すことで、O(n) 時間でペアの有無を判定できます。

この解法は O(n) 時間で動作しますが、中間順走査の結果を保存するために O(n) の補助空間が必要になる点には留意してください。

Java実装例

// 平衡BST内で指定された合計値になるペアを検索するJavaコード
import java.util.ArrayList;

// 二分木のノードを表すクラス
class Node1 {
    int data1;
    Node1 left1, right1;
    Node1(int d){
        data1 = d;
        left1 = right1 = null;
    }
}

public class BinarySearchTree {
    // BSTのルートノード
    Node1 root1;

    // コンストラクタ
    BinarySearchTree(){
        root1 = null;
    }

    // 木の中間順走査を実行するメソッド
    void inorder(){
        inorderUtil1(this.root1);
    }

    // 中間順走査のためのユーティリティ関数
    void inorderUtil1(Node1 node1){
        if (node1 == null)
            return;
        inorderUtil1(node1.left1);
        System.out.print(node1.data1 + " ");
        inorderUtil1(node1.right1);
    }

    // insertRec() を呼び出すメソッド
    void insert(int key1){
        root1 = insertRec1(root1, key1);
    }

    /* BSTに新しいキーを挿入する再帰関数 */
    Node1 insertRec1(Node1 root1, int data1){
        // 木が空の場合は新しいノードを返す
        if (root1 == null) {
            root1 = new Node1(data1);
            return root1;
        }
        // それ以外の場合は木を下へたどる
        if (data1 < root1.data1)
            root1.left1 = insertRec1(root1.left1, data1);
        else if (data1 > root1.data1)
            root1.right1 = insertRec1(root1.right1, data1);
        return root1;
    }

    // BSTの各ノードの値をArrayListに格納して返すメソッド
    ArrayList<Integer> treeToList(Node1 node1, ArrayList<Integer> list1){
        // ベースケース
        if (node1 == null)
            return list1;
        treeToList(node1.left1, list1);
        list1.add(node1.data1);
        treeToList(node1.right1, list1);
        return list1;
    }

    // ペアが存在するかどうかをチェックするメソッド
    boolean isPairPresent(Node1 node1, int target1){
        // このリスト a1 は treeToList メソッドの引数として渡され、
        // 後ほどBSTの値で埋められる
        ArrayList<Integer> a1 = new ArrayList<>();

        // リスト a2 には treeToList メソッドが返した
        // BSTのすべての値が格納される
        ArrayList<Integer> a2 = treeToList(node1, a1);

        int start1 = 0;                 // a2 の開始インデックス
        int end1 = a2.size() - 1;       // a2 の終了インデックス

        while (start1 < end1) {
            if (a2.get(start1) + a2.get(end1) == target1) {
                // 目標値が見つかった！
                System.out.println("Pair Found: " + a2.get(start1) + " + " + a2.get(end1) + " " + "= " + target1);
                return true;
            }
            if (a2.get(start1) + a2.get(end1) > target1)
                // end を減らす
                end1--;
            if (a2.get(start1) + a2.get(end1) < target1)
                // start を増やす
                start1++;
        }
        System.out.println("No such values are found!");
        return false;
    }

    // ドライバ関数
    public static void main(String[] args){
        BinarySearchTree tree1 = new BinarySearchTree();
        /*
          16
         /  \
       11    21
      /  \   /  \
     9   13 17   26
        */
        tree1.insert(16);
        tree1.insert(11);
        tree1.insert(21);
        tree1.insert(9);
        tree1.insert(13);
        tree1.insert(17);
        tree1.insert(26);

        tree1.isPairPresent(tree1.root1, 34);
    }
}

出力結果

Pair Found: 13 + 21 = 34