C++を使用して指定された高さのAVLツリー内のノードの最小数。

問題の説明

AVLツリーの高さを考えると、タスクはツリーが持つことができるノードの最小数を見つけることです。

If height = 0 then AVL tree can have one 1 node
If height = 5 then AVL tree can have minimum 20 nodes

アルゴリズム

AVLツリーでは、高さのバランスプロパティを維持する必要があります。つまり、左右のサブツリーの高さの差は、ノードごとに-1、0、または1を超えることはできません。このプロパティを使用して、以下の漸化式を作成できます-

1. If height = 0 then return 1
2. If height = 1 then return 2
3. If height > 1 then return (1 + getMinAVLNodes(h – 1) + getMinAVLNodes(h – 2))

例

#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