이진 트리(Binary Tree)의 핵심 속성 총정리

이진 트리의 주요 속성

이 글에서는 이진 트리(Binary Tree) 자료 구조가 가지는 중요한 속성들을 살펴보겠습니다. 먼저 아래와 같은 이진 트리가 있다고 가정해 보겠습니다.

이진 트리의 대표적인 속성들은 다음과 같습니다.

1. 레벨별 최대 노드 수

레벨 l에서 가질 수 있는 최대 노드 수는 2^l-1입니다. 여기서 레벨(level)이란 루트에서 해당 노드까지의 경로에 포함된 노드의 개수를 의미하며, 루트 자신도 포함됩니다. 이때 루트의 레벨은 1로 간주합니다.

2. 높이별 최대 노드 수

높이가 h인 이진 트리에 존재할 수 있는 최대 노드 수는 2^h − 1입니다. 여기서 높이(height)는 루트에서 리프(leaf) 노드까지의 경로에 있는 노드 수의 최댓값을 뜻하며, 노드가 하나뿐인 트리의 높이는 1로 정의합니다.

3. 노드 수 대비 최소 높이

n개의 노드를 가진 이진 트리에서 가능한 최소 높이, 즉 최소 레벨 수는 log₂(n+1)입니다. 만약 리프 노드의 높이를 0으로 간주하는 경우에는 공식이 log₂(n+1) − 1로 바뀝니다.

4. 리프 노드 수 대비 최소 레벨 수

리프 노드가 L개인 이진 트리는 최소한 log₂(L+1)개의 레벨을 가져야 합니다.

5. 리프 노드와 내부 노드의 개수 관계

모든 노드가 0개 또는 2개의 자식을 가지는 이진 트리(포화 이진 트리 형태)에서는, 리프 노드의 수가 항상 두 개의 자식을 가진 노드의 수보다 정확히 하나 더 많습니다.

참고(N.B.) 이진 트리는 트리(tree)의 한 종류이므로, 그래프 이론에서 정의되는 트리의 모든 일반적인 성질을 그대로 가집니다.