C++で二分探索木（BST）を最大ヒープに変換する方法

はじめに

このチュートリアルでは、二分探索木（BST）を最大ヒープに変換するプログラムについて解説します。

入力として二分探索木が与えられ、それを最大ヒープへと変換することが目的です。ただし、単にヒープ化するだけではなく、「要素同士を比較した際に二分探索木としての順序条件が引き続き成立する」ように変換しなければなりません。つまり、変換後の木は次の2つの性質を同時に満たす必要があります。

• 最大ヒープの性質：すべての親ノードの値が、その子ノードの値以上である
• 二分探索木の性質：任意のノードについて、左部分木の値 ≤ そのノードの値 ≤ 右部分木の値 が成り立つ

アルゴリズムの考え方

この変換は、次の2段階の手順で実現できます。

1. 中順走査（Inorder Traversal）を実行する
   二分探索木を中順走査すると、昇順にソートされた値の配列が得られます。
2. 後順走査（Postorder Traversal）の順序で値を書き戻す
   得られたソート済み配列の値を、木を後順走査する順番（左 → 右 → 親）で各ノードに代入していきます。

後順走査では最後に親ノードを訪問するため、配列の先頭（最小値）から順に埋めていくと、根ノードには必ず最大値が割り当てられます。その結果、すべての親ノードが子ノード以上の値を持つ最大ヒープとなり、かつBSTの順序性も維持されます。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
// BSTのノード構造体
struct Node {
   int data;
   Node *left, *right;
};
// ノードの生成
struct Node* getNode(int data) {
   struct Node* newNode = new Node;
   newNode->data = data;
   newNode->left = newNode->right = NULL;
   return newNode;
}
// 後順走査のプロトタイプ宣言
void postorderTraversal(Node*);
// 中順走査により昇順ソート済みの配列を作成する
void inorderTraversal(Node* root, vector<int>& arr) {
   if (root == NULL)
      return;
   inorderTraversal(root->left, arr);
   arr.push_back(root->data);
   inorderTraversal(root->right, arr);
}
// 後順走査の順序で配列の値をノードへコピーする
void convert_BSTHeap(Node* root, vector<int> arr, int* i){
   if (root == NULL)
      return;
   convert_BSTHeap(root->left, arr, i);
   convert_BSTHeap(root->right, arr, i);
   // 配列からノードへデータをコピー
   root->data = arr[++*i];
}
// 最大ヒープへの変換
void convert_maxheap(Node* root) {
   vector<int> arr;
   int i = -1;
   inorderTraversal(root, arr);
   convert_BSTHeap(root, arr, &i);
}
// 後順走査の結果を出力する
void postorderTraversal(Node* root) {
   if (!root)
      return;
   postorderTraversal(root->left);
   postorderTraversal(root->right);
   cout << root->data << " ";
}
int main() {
   struct Node* root = getNode(4);
   root->left = getNode(2);
   root->right = getNode(6);
   root->left->left = getNode(1);
   root->left->right = getNode(3);
   root->right->left = getNode(5);
   root->right->right = getNode(7);
   convert_maxheap(root);
   cout << "後順走査の結果:" << endl;
   postorderTraversal(root);
   return 0;
}

出力結果

後順走査の結果:
1 2 3 4 5 6 7

コードの解説

このプログラムの流れを整理すると、次のようになっています。

1. inorderTraversal()：BSTを中順走査し、昇順ソート済みの配列 arr を作成します。
2. convert_BSTHeap()：木を後順走査しながら、インデックス i を進めつつ配列の値を各ノードに代入します。再帰呼び出しが「左 → 右 → 自身」の順に行われるため、親ノードには必ず子ノードより大きい値が割り当てられます。
3. convert_maxheap()：上記の2つの関数を呼び出して変換全体を実行します。
4. postorderTraversal()：変換後の木を後順走査して結果を出力し、正しく変換できたかを確認します。

計算量

• 時間計算量：O(n) — 中順走査と後順走査をそれぞれ1回ずつ実行するためです。
• 空間計算量：O(n) — ソート済みの値を一時的に保持するための補助配列が必要になります。