C++の二分探索木（BST）で合計が指定値と等しくなるペアを検索する方法

このチュートリアルでは、二分探索木（BST）の中から、合計が指定された数値と等しくなるペアを見つけるプログラムを作成します。

木のノードの値を2つの異なるリストに格納し、それらを比較することでペアを効率的に探します。それでは、問題を解くための手順を見ていきましょう。

• 二分木用の構造体 Node を作成します。

• 新しいノードを二分探索木に挿入する関数を書きます。

  • 二分探索木では、根より小さい要素はすべて左側に、大きい要素はすべて右側に配置されることを覚えておきましょう。

• 木の左側と右側のノードを格納するための空のリストを2つ初期化します。

• 左または右のノードが NULL になるか、両方のリストが空になるまで、二分探索木を反復処理します。

  • ループを使って、すべての要素を左側ノードのリストに格納します。

  • ループを使って、すべての要素を右側ノードのリストに格納します。

  • 各リストから最後のノードを取得します。

  • 2つの値をチェックします。

    • 左側のノードの値が右側のノードの値以上の場合は、ループを抜けます。

    • 2つの値の合計が指定された数値と等しい場合は、結果を出力してループを抜けます。

    • 2つの値の合計が指定された数値より小さい場合は、左側のリストから最後のノードを削除し、そのノードの右側へ移動します。

    • 2つの値の合計が指定された数値より大きい場合は、右側のリストから最後のノードを削除し、そのノードの左側へ移動します。

実装例

それでは、実際のコードを見てみましょう。

#include<bits/stdc++.h>
using namespace std;
struct Node{
   int data;
   Node *left, *right, *root;
   Node(int data) {
      this->data = data;
      left = NULL;
      right = NULL;
      root = NULL;
   }
};
Node* insertNewNode(Node *root, int data){
   if (root == NULL) {
      root = new Node(data);
      return root;
   }
   if (root->data < data) {
      root->right = insertNewNode(root->right, data);
   }
   else if (root->data > data) {
      root->left = insertNewNode(root->left, data);
   }
   return root;
}
void findThePairs(Node *node, int target) {
   vector<Node*> left_side_nodes;
   vector<Node*> right_side_nodes;
   Node *current_left = node;
   Node *current_right = node;
   while (current_left != NULL || current_right != NULL || (left_side_nodes.size() > 0 && right_side_nodes.size() > 0)) {
      while (current_left != NULL) {
         left_side_nodes.push_back(current_left);
         current_left = current_left->left;
      }
      while (current_right != NULL) {
         right_side_nodes.push_back(current_right);
         current_right = current_right->right;
      }
      Node *left_side_node = left_side_nodes[left_side_nodes.size() - 1];
      Node *right_side_node = right_side_nodes[right_side_nodes.size() - 1];
      int left_side_value = left_side_node->data;
      int right_side_value = right_side_node->data;
      if (left_side_value >= right_side_value) {
         break;
      }
      if (left_side_value + right_side_value < target) {
         left_side_nodes.pop_back();
         current_left = left_side_node->right;
      }
      else if (left_side_value + right_side_value > target) {
         right_side_nodes.pop_back();
         current_right = right_side_node->left;
      }
      else {
         cout << left_side_node->data << " " << right_side_node->data << endl;
         break;
      }
   }
}
int main() {
   Node *root = NULL;
   root = insertNewNode(root, 25);
   root = insertNewNode(root, 20);
   root = insertNewNode(root, 30);
   root = insertNewNode(root, 15);
   root = insertNewNode(root, 21);
   root = insertNewNode(root, 19);
   root = insertNewNode(root, 31);
   findThePairs(root, 36);
}

出力

上記のプログラムを実行すると、次の結果が得られます。

15 21

まとめ

このアルゴリズムは、BSTを「最小値方向（昇順）」と「最大値方向（降順）」の2方向から同時にたどることで、ソート済み配列における双方向ポインタ（two pointer）手法と同じ考え方でペアを検索できます。時間計算量・空間計算量はともに O(n) となり、BSTの性質を活かした効率的なアプローチです。

このチュートリアルについて質問がある場合は、コメント欄でお気軽にお知らせください。