C++で実装する完全二分木インサーター(CBTInserter)の解説とコード例

完全二分木(Complete Binary Tree)とは、最後のレベルを除くすべてのレベルが完全に埋まっており、かつ最後のレベルのノードはすべて可能な限り左に寄せられている二分木のことです。

本記事では、完全二分木を初期状態として受け取り、以下の操作をサポートするデータ構造 CBTInserter をC++で実装する方法を解説します。

• CBTInserter(TreeNode root):ルートノード root を持つ木を初期化します。
• CBTInserter.insert(int v):値 v を持つノードを挿入し、木が完全二分木の状態を保つようにします。挿入されたノードの親の値を返り値として返します。
• CBTInserter.get_root():木のルートノードを返します。

動作例

例として、木を [1,2,3,4,5,6] で初期化し、その後 7 と 8 を挿入してから get_root() を呼び出した場合を考えます。このとき出力は次のようになります。

• 7 を挿入 → 親は 3(7 はノード 3 の子として挿入されるため)
• 8 を挿入 → 親は 4(8 はノード 4 の子として挿入されるため)
• get_root() の結果 → [1,2,3,4,5,6,7,8]

アルゴリズムのアプローチ

この問題はキュー(queue)を使った幅優先探索(BFS)の考え方で効率的に解けます。手順は以下の通りです。

1. キュー q と root を定義します。
2. コンストラクタでは、与えられた完全二分木を受け取り、root を設定したうえで root をキューに追加します。
3. 無限ループ内で以下を繰り返します。
   • 現在のノードに左の子が存在するなら、それをキューに追加します。存在しなければループを抜けます。
   • 右の子が存在するなら、それをキューに追加し、先頭ノードを削除して次の候補ノードへ進みます。存在しなければループを抜けます。
4. これにより、キューの先頭には「子を追加できる最初のノード」が保持されます。

insert メソッドの処理

1. 値 v を受け取ります。
2. parent := キューの先頭要素、temp := 値 v を持つ新規ノードとし、temp をキューに追加します。
3. parent の左の子が存在しない場合は parent->left = temp とします。すでに存在する場合はキューの先頭を削除し、temp を parent の右の子として設定します。
4. parent の値を返します。

get_root メソッドの処理

保持している root をそのまま返すだけです。

C++による実装例

以下の実装を見ると、理解がより深まるでしょう。

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
      int val;
      TreeNode *left, *right;
      TreeNode(int data){
         val = data;
         left = NULL;
         right = NULL;
    }
};
void insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
    } else {
         q.push(temp->left);
      }
      if(!temp->right){
         if(val != NULL)
            temp->right = new TreeNode(val);
         else
            temp->right = new TreeNode(0);
         return;
    } else {
         q.push(temp->right);
    }
 }
}
TreeNode *make_tree(vector<int> v){
   TreeNode *root = new TreeNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
  }
   return root;
}
void tree_level_trav(TreeNode*root){
   if (root == NULL) return;
   cout << "[";
   queue<TreeNode *> q;
   TreeNode *curr;
   q.push(root);
   q.push(NULL);
   while (q.size() > 1) {
      curr = q.front();
      q.pop();
      if (curr == NULL){
         q.push(NULL);
    } else {
         if(curr->left)
            q.push(curr->left);
         if(curr->right)
            q.push(curr->right);
         if(curr == NULL || curr->val == 0){
            cout << "null" << ", ";
         } else{
            cout << curr->val << ", ";
         }
    }
  }
   cout << "]"<<endl;
}
class CBTInserter {
public:
   queue <TreeNode*> q;
   TreeNode* root;
   CBTInserter(TreeNode* root) {
      this->root = root;
      q.push(root);
      while(1){
         if(root->left){
            q.push(root->left);
         }
         else break;
         if(root->right){
            q.push(root->right);
            q.pop();
            root = q.front();
         }
         else break;
    }
  }
   int insert(int v) {
      TreeNode* parent = q.front();
      TreeNode* temp = new TreeNode(v);
      q.push(temp);
      if(!parent->left){
         parent->left = temp;
    } else {
         q.pop();
         parent->right = temp;
    }
      return parent->val;
  }
   TreeNode* get_root() {
      return root;
  }
};
main(){
   vector<int> v = {1,2,3,4,5,6};
   TreeNode *root = make_tree(v);
   CBTInserter ob(root);
   cout << (ob.insert(7)) << endl;
   cout << (ob.insert(8)) << endl;
   tree_level_trav(ob.get_root());
}

入力

木を [1,2,3,4,5,6] として初期化し、7 と 8 を挿入した後、ルートを取得する

出力

3
4
[1, 2, 3, 4, 5, 6, 7, 8]

計算量について

コンストラクタでは木全体を一度走査するため O(N)(N はノード数)の時間がかかりますが、insert 操作自体は O(1) で完了します。これは、挿入可能な位置を常にキューの先頭で管理しているためです。この仕組みにより、何度挿入を繰り返しても高速な操作が実現できます。