【C++】指定された高さのAVL木における最小ノード数の求め方

問題概要

AVL木の高さが与えられたとき、その木が取り得るノード数の最小値を求めるのが本問題の目的です。

高さ = 0 の場合、AVL木は最低でも1個のノードを持つ
高さ = 5 の場合、AVL木の最小ノード数は20

アルゴリズム

AVL木では、すべてのノードにおいて左部分木と右部分木の高さの差が -1、0、1 のいずれかに収まっていなければならないという高さ平衡条件を維持する必要があります。この性質を利用すると、次のような漸化式を立てることができます。

1. 高さ = 0 のとき … 1 を返す
2. 高さ = 1 のとき … 2 を返す
3. 高さ > 1 のとき … 1 + getMinAVLNodes(h - 1) + getMinAVLNodes(h - 2) を返す

漸化式の直感的な説明

高さ h のAVL木をできるだけ少ないノードで構成するには、根ノード1個に対して、片側には高さ h-1 の部分木、もう片側には高さ h-2 の部分木を配置します。この操作を再帰的に繰り返すことで最小ノード数が求まります。なお、この漸化式はフィボナッチ数列とよく似た構造を持っている点も特徴的です。

C++による実装例

#include <iostream>
using namespace std;

int getMinAVLNodes(int h){
    if (h < 0) {
        return 0;
    }
    if (h == 0 || h == 1) {
        return h + 1;
    }
    return 1 + getMinAVLNodes(h - 1) + getMinAVLNodes(h - 2);
}

int main(){
    int h = 5;
    cout << "Minimum nodes for " << h << " height = " << getMinAVLNodes(h) << endl;
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Minimum nodes for 5 height = 20

計算量と改善のポイント

この素朴な再帰実装では、同じ引数に対する計算が何度も重複して発生するため、時間計算量は入力の高さに対して指数オーダーになります。フィボナッチ数列の計算と同様に、メモ化や動的計画法(DP)を使って途中結果を配列などに保存しておけば、O(h) 時間・O(h) 空間まで効率化できます。大きな高さを扱う場合は、こうした最適化を検討するとよいでしょう。