C++로 높이 H의 균형 이진 트리 개수 구하기

높이 H가 주어졌을 때, 그 높이를 가질 수 있는 균형 이진 트리(balanced binary tree)의 총 개수를 구하는 것이 이 글의 목표입니다.

핵심 개념 정리

이진 트리(binary tree)란 각 노드가 최대 두 개의 자식 노드, 즉 왼쪽 자식과 오른쪽 자식만을 가질 수 있는 트리 자료구조입니다.

높이 균형 이진 트리(height-balanced binary tree)는 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 깊이 차이가 0 또는 1인 이진 트리를 말합니다. 다시 말해, 트리 안의 모든 노드에서 좌우 서브트리의 높이 차이가 최대 1을 넘지 않아야 합니다.

다음 그림은 높이 h=3일 때 만들 수 있는 균형 이진 트리의 예를 보여줍니다.

입력

Height H=2

출력

Count of Balanced Binary Trees of Height H is : 3

설명 - 아래 그림은 높이 H=2일 때 가능한 균형 트리 세 가지를 나타낸 것입니다.

입력

Height H=3

출력

Count of Balanced Binary Trees of Height H is : 15

풀이 접근 방식

• 정수 H는 이진 트리의 높이를 나타냅니다.

• 함수 countBTheight(int h)는 트리의 높이를 입력받아, 높이가 h인 균형 이진 트리가 총 몇 개 존재하는지 반환합니다.

• 문제는 재귀(recursion) 방식으로 해결합니다.

• 트리의 높이가 1이면 노드가 하나뿐이므로 가능한 트리는 단 하나이며, 이 트리는 당연히 균형 상태입니다. (if(h==1), return 1)

• 그 외의 경우에는 루트보다 높이가 1 또는 2만큼 작은 왼쪽·오른쪽 서브트리들의 조합으로 전체 개수를 구합니다. 균형 트리에서는 좌우 서브트리의 높이 차이가 1 이하여야 하기 때문입니다.

• 함수는 최종적으로 계산된 개수를 결과로 반환합니다.

이 논리를 점화식으로 정리하면 다음과 같습니다.

T(h) = T(h-1) × ( T(h-1) + 2 × T(h-2) )

루트 아래 왼쪽·오른쪽 서브트리의 높이 조합은 (h-1, h-1), (h-1, h-2), (h-2, h-1) 세 가지 경우뿐이며, 각 경우의 트리 개수를 모두 더한 값이 곧 T(h)가 됩니다.

C++ 코드 예제

#include <iostream>
int countBTheight(int h){
    // 높이가 0 또는 1일 때 가능한 트리는 한 종류뿐이다
    if (h == 0 || h == 1)
        return 1;
    return countBTheight(h-1) * (2 * countBTheight(h-2) + countBTheight(h-1));
}
int main(){
    int H = 4;
    std::cout << "높이가 H인 균형 이진 트리의 개수: " << countBTheight(H);
}

실행 결과

높이가 H인 균형 이진 트리의 개수: 315

H=4일 때 만들 수 있는 균형 이진 트리의 개수는 총 315개입니다. 입력값 H를 바꾸어 호출하면 해당 높이에 대한 균형 트리 개수를 손쉽게 확인할 수 있습니다.