C++で二分木から最大の完全二分部分木を検索するアルゴリズム

基本概念

与えられた二分木の中から、最大の完全二分部分木のサイズを求めるのが本記事のテーマです。

完全二分木とは – 最後のレベルを除くすべてのレベルがノードで完全に埋まっており、最後のレベルのノードができるだけ左側に寄せられている二分木を指します。すべての完全（パーフェクト）二分木は必ず完全二分木でもありますが、その逆は成り立ちません。また、ある木が完全二分木でない場合、それは完全（パーフェクト）二分木でもないという点にも注意してください。

入力例1

      2
     / \
    3   4
   / \ / \
  5  6 7  8
 / \ /
9 10 11

出力例1

Size : 10
Inorder Traversal : 9 5 10 3 11 6 2 7 4 8
この木は完全二分木です。

入力例2

      51
     / \
   31   61
   / \  / \
  6 21 46  71
 /
11

出力例2

Size : 4（右部分木について）
Inorder Traversal : 11 46 61 71
この木は完全二分木ではありません。

解法のアプローチ

基本的な考え方は、木をボトムアップ（下から上へ）の順序で走査することです。再帰によって子ノードから親ノードへ処理が戻る際に、部分木に関する情報を親へ渡せます。この情報を活用すれば、親ノードが完全二分木の条件を満たしているかどうかを定数時間で判定できます。

最大の完全二分部分木を特定するために、左右の子部分木は次の情報を親へ返す必要があります。

• 左または右の子部分木が完全（パーフェクト）二分木であるか、また完全二分木であるかを示すbool型のフラグ。

• さらに、再帰呼び出しから得た左右の子の情報をもとに、親の部分木が完全二分木かどうかを次の3つのケースで判定します。

  • ケースA： 左部分木が完全（パーフェクト）であり、右部分木が完全二分木で、両者の高さが等しい場合、根を含む部分木全体が完全二分木になります。サイズは「左部分木＋右部分木＋1（現在の根）」です。

  • ケースB： 左部分木が完全二分木であり、右部分木が完全（パーフェクト）で、左の高さが右よりちょうど1大きい場合、根を含む部分木は完全二分木になります。ただし、この場合左の子が完全（パーフェクト）ではないため、部分木自体は完全（パーフェクト）二分木とはみなせません。

  • ケースC： 上記以外の場合、この部分木は完全二分木とみなせず、左右の部分木でこれまでに見つかった最大サイズの完全二分部分木をそのまま返します。つまり、木が完全二分木でなければ、完全（パーフェクト）二分木でもないということになります。

C++実装例

// 本アプローチのC++実装
#include <bits/stdc++.h>
using namespace std;

// 木のノード構造体
struct node1 {
    int data;
    struct node1* left;
    struct node1* right;
};

// 新しいノードを生成する関数
struct node1* newNode(int data){
    struct node1* node1 = (struct node1*)malloc(sizeof(struct node1));
    node1->data = data;
    node1->left = NULL;
    node1->right = NULL;
    return node1;
};

// findCompleteBinaryTree関数の戻り値となる構造体
struct returnType {
    // 部分木が完全（パーフェクト）二分木かどうか
    bool isPerfect;
    // 部分木が完全二分木かどうか
    bool isComplete;
    // 木のサイズ
    int size1;
    // 最大の完全二分部分木の根ノード
    node1* rootTree;
};

// サイズから木の高さを求めるヘルパー関数
int getHeight(int size1){
    return ceil(log2(size1 + 1));
}

// 最大の完全二分部分木を返す関数
returnType findCompleteBinaryTree(struct node1* root){
    // 戻り値として返すreturnTypeを宣言
    returnType rt1;
    // 根がNULLの場合、サイズ0の完全（パーフェクト）かつ完全な二分木とみなす
    if (root == NULL) {
        rt1.isPerfect = true;
        rt1.isComplete = true;
        rt1.size1 = 0;
        rt1.rootTree = NULL;
        return rt1;
    }
    // 左右の子に対する再帰呼び出し
    returnType lv1 = findCompleteBinaryTree(root->left);
    returnType rv1 = findCompleteBinaryTree(root->right);
    // ケースA：左部分木が完全（パーフェクト）で右部分木が完全二分木、
    // かつ両者の高さが等しい場合、根を含む部分木は完全二分木になる。
    // サイズは左右の部分木の合計に1（現在の根）を加えたもの。
    if (lv1.isPerfect == true && rv1.isComplete == true && getHeight(lv1.size1) == getHeight(rv1.size1)) {
        rt1.isComplete = true;
        // 右部分木が完全（パーフェクト）であれば根も完全（パーフェクト）
        rt1.isPerfect = (rv1.isPerfect ? true : false);
        rt1.size1 = lv1.size1 + rv1.size1 + 1;
        rt1.rootTree = root;
        return rt1;
    }
    // ケースB：左部分木が完全二分木で右部分木が完全（パーフェクト）、
    // かつ左の高さが右より1だけ大きい場合、根を含む部分木は完全二分木になる。
    // ただし左の子が完全（パーフェクト）ではないため、部分木自体は完全（パーフェクト）にはならない。
    if (lv1.isComplete == true && rv1.isPerfect == true && getHeight(lv1.size1) == getHeight(rv1.size1) + 1) {
        rt1.isComplete = true;
        rt1.isPerfect = false;
        rt1.size1 = lv1.size1 + rv1.size1 + 1;
        rt1.rootTree = root;
        return rt1;
    }
    // ケースC：それ以外の場合、この部分木は完全二分木とみなせないため、
    // 左右の部分木でこれまでに見つかった最大の完全二分部分木をそのまま返す。
    rt1.isPerfect = false;
    rt1.isComplete = false;
    rt1.size1 = max(lv1.size1, rv1.size1);
    rt1.rootTree = (lv1.size1 > rv1.size1 ? lv1.rootTree :
    rv1.rootTree);
    return rt1;
}

// 木の中間順巡回（inorder traversal）を出力する関数
void inorderPrint(node1* root){
    if (root != NULL) {
        inorderPrint(root->left);
        cout << root->data << " ";
        inorderPrint(root->right);
    }
}

// ドライバーコード
int main(){
    // 木の構築
    struct node1* root = newNode(50);
    root->left = newNode(30);
    root->right = newNode(60);
    root->left->left = newNode(5);
    root->left->right = newNode(20);
    root->right->left = newNode(45);
    root->right->right = newNode(70);
    root->right->left->left = newNode(10);
    // 最大サイズの完全二分部分木を取得
    struct returnType ans1 = findCompleteBinaryTree(root);
    cout << "Size : " << ans1.size1 << endl;
    // 見つかった部分木の中間順巡回を出力
    cout << "Inorder Traversal : ";
    inorderPrint(ans1.rootTree);
    return 0;
}

出力結果

Size : 4
Inorder Traversal : 10 45 60 70

このプログラムでは、ノード45を根とする部分木（45・60・70・10）が最大の完全二分部分木として検出され、そのサイズ4と中間順巡回の結果が出力されます。

計算量

このアルゴリズムは各ノードを一度だけ訪問するため、時間計算量はO(n)、再帰の深さに依存する空間計算量はO(h)（hは木の高さ）となります。ボトムアップ方式により各ノードでの判定が定数時間で済む点が、この手法の大きな利点です。