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