C++で連続ツリー（Continuous Tree）を判定するアルゴリズムと実装例

連続ツリー（Continuous Tree）とは

連続ツリーとは、ルートノードから葉ノードまでのすべての経路において、親ノードとそのすべての直接の子ノードとの値（重み）の絶対差が常に1となるような木のことです。

ルートから葉への経路上の任意のノードを選んだとき、次の条件が必ず成り立ちます。

|ノードの値 − 左の子ノードの値| = 1（右の子ノードについても同様に成り立つ）

図解と具体例

具体例を見ながら理解を深めましょう。

下の木は、親ノードとその子ノードの値の絶対差が常に1であるため、連続ツリーとみなされます。

一方、下の木は親子ノード間の絶対差が1になっていない箇所があるため、連続ツリーの条件を満たしていません。

木が連続しているかを判定するアルゴリズム

判定は再帰的に行います。手順は以下のとおりです。

• ルートがNULLの場合は1を返す（終了条件）。
• 葉ノードに到達した場合は1を返す。その経路はここまで連続していたことを意味する。
• 左の部分木が空の場合は、現在のノードと右の子の値の絶対差を計算して連続性を確認し、右の部分木に対して再帰的に処理を続ける。
• 右の部分木が空の場合は、現在のノードと左の子の値の絶対差を計算して連続性を確認し、左の部分木に対して再帰的に処理を続ける。
• どちらの子も存在する場合は、左右両方の子との絶対差を計算して連続性を確認し、左右の部分木に対して再帰的に処理を続ける。

擬似コード（C++実装）

// 木が連続しているかどうかを判定する関数
struct btreeNode{
    int data;
    btreeNode* left, * right;
};
int isContinuous(btreeNode *root){
    // ノードがNULLの場合は1を返す（終了条件）
    if (root == NULL)
        return 1;
    // 葉ノードに到達した場合、この経路はここまで連続しているはず
    if (root->left == NULL && root->right == NULL)
        return 1;
    // 左の子が存在しない場合
    if (root->left == NULL)
        return (abs(root->data - root->right->data) == 1) && isContinuous(root->right);
    // 右の子が存在しない場合
    if (root->right == NULL)
        return (abs(root->data - root->left->data) == 1) && isContinuous(root->left);
    // 左右両方の子との絶対差を計算
    return abs(root->data - root->left->data)==1 && abs(root->data - root->right->data)==1 &&
        isContinuous(root->left) && isContinuous(root->right);
}

計算量について

このアルゴリズムは木のすべてのノードを一度ずつ訪問するため、ノード数をnとすると時間計算量はO(n)となります。また、再帰呼び出しの深さは木の高さに依存するため、平衡な木であれば空間計算量はO(log n)、最悪ケース（線形リスト状の木）ではO(n)となります。