C++로 구하는 AVL 트리의 최소 노드 개수: 주어진 높이 기준

문제 정의

AVL 트리는 스스로 균형을 유지하는 이진 탐색 트리(BST)의 일종으로, 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 반드시 -1, 0, 1 중 하나여야 합니다. 이번 글에서는 AVL 트리의 높이가 주어졌을 때, 그 트리가 가질 수 있는 최소 노드 개수를 구하는 방법을 알아보겠습니다.

높이(height) = 0이면 AVL 트리는 1개의 노드를 가질 수 있습니다.
높이(height) = 5이면 AVL 트리는 최소 20개의 노드를 가져야 합니다.

알고리즘: 점화식 세우기

AVL 트리의 높이 균형 속성에 따르면, 어떤 노드의 양쪽 서브트리 높이 차이도 1을 넘을 수 없습니다. 따라서 최소한의 노드로 트리를 구성하려면 한쪽 서브트리는 높이 h-1까지 채우고, 나머지 한쪽은 높이 h-2까지만 허용하면 됩니다. 여기에 루트 노드 1개를 더하면 다음과 같은 재귀 점화식이 만들어집니다.

1. 높이가 0이면 1을 반환한다
2. 높이가 1이면 2를 반환한다
3. 높이가 1보다 크면 (1 + getMinAVLNodes(h - 1) + getMinAVLNodes(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

마무리 및 성능 팁

이 알고리즘은 직관적이지만, 단순 재귀 방식은 동일한 하위 문제를 반복 계산하기 때문에 시간 복잡도가 지수적으로 증가할 수 있습니다. 실무에서는 메모이제이션(memoization)을 적용하거나, N(0)=1, N(1)=2부터 시작해 바닥부터 차례로 값을 채워 올라가는 동적 계획법(DP) 방식으로 개선하면 O(h) 시간에 효율적으로 답을 구할 수 있습니다.