자료구조: 완전 이진 트리 (Complete Binary Tree)

완전 이진 트리 (Complete Binary Tree) 완벽 가이드

소프트웨어 엔지니어링 인터뷰에서 트리(Tree) 자료구조는 단골 출제 주제입니다. 그중에서도 힙(Heap)과 깊은 연관이 있는 **완전 이진 트리(Complete Binary Tree)**에 대해 자세히 알아보겠습니다.

1. 완전 이진 트리란?

완전 이진 트리는 이진 트리(Binary Tree)의 한 종류로, 다음 두 가지 조건을 만족하는 트리입니다.

1. 마지막 레벨을 제외한 모든 레벨의 노드가 완전히 채워져 있어야 합니다.
2. 마지막 레벨의 노드는 왼쪽부터 오른쪽으로 차례대로 채워져 있어야 합니다.

즉, 노드를 삽입할 때 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 빈자리를 채워나가는 형태의 트리입니다.

2. 다른 이진 트리와의 비교

트리 관련 용어는 헷갈리기 쉬우므로 명확히 구분하는 것이 중요합니다.

• 포화 이진 트리 (Perfect Binary Tree): 모든 내부 노드가 두 개의 자식을 가지고 있으며, 모든 리프 노드가 같은 레벨(깊이)에 있는 트리입니다. (삼각형 형태로 완벽하게 꽉 찬 트리)
• 정 이진 트리 (Full/Strictly Binary Tree): 모든 노드가 0개 또는 2개의 자식을 가지는 트리입니다. (자식이 1개인 노드가 없음)
• 완전 이진 트리 (Complete Binary Tree): 포화 이진 트리처럼 꽉 차 있지는 않지만, 왼쪽부터 차곡차곡 채워진 트리입니다. 포화 이진 트리는 완전 이진 트리에 포함됩니다.

3. 완전 이진 트리의 특성

• 높이 (Height): 노드의 개수가 $N$일 때, 완전 이진 트리의 높이 $h$는 $O(\log N)$입니다. 정확히는 $\lfloor {\log }_{2}N\rfloor$ 입니다. 이는 트리의 탐색, 삽입, 삭제 등의 연산이 매우 효율적으로 이루어질 수 있음을 의미합니다.
• 노드의 개수: 높이가 $h$인 완전 이진 트리가 가질 수 있는 노드의 최대 개수는 $2^{h+1}-1$ 개(포화 이진 트리일 때)이며, 최소 개수는 $2^h$ 개입니다.

4. 배열을 이용한 완전 이진 트리의 표현

완전 이진 트리의 가장 큰 장점 중 하나는 1차원 배열을 이용하여 매우 효율적으로 구현할 수 있다는 것입니다. 왼쪽부터 차례대로 번호를 매기면 빈 공간(낭비되는 메모리) 없이 배열에 순서대로 매핑됩니다.

노드의 번호(인덱스)를 1부터 시작한다고 가정할 때, 인덱스 $i$에 위치한 노드의 관계는 다음과 같이 간단한 수식으로 표현됩니다. (인덱스 0을 사용하지 않으면 계산이 훨씬 직관적입니다.)

• 현재 노드의 인덱스: $i$
• 왼쪽 자식 노드의 인덱스: $2i$
• 오른쪽 자식 노드의 인덱스: $2i+1$
• 부모 노드의 인덱스: $\lfloor i/2\rfloor$

(만약 인덱스를 0부터 시작한다면: 왼쪽 자식 $2i+1$, 오른쪽 자식 $2i+2$, 부모 $\lfloor (i-1)/2\rfloor$)

이렇게 수식만으로 부모/자식 노드로 즉각적인 접근($O(1)$)이 가능하므로, 포인터를 사용하는 연결 리스트(Linked List) 구현보다 메모리 오버헤드가 적고 접근 속도가 빠릅니다.

5. 완전 이진 트리의 활용

완전 이진 트리는 구조적 규칙성 덕분에 다음과 같은 곳에서 핵심적으로 사용됩니다.

1. 힙 (Heap): 완전 이진 트리를 기반으로 하는 대표적인 자료구조입니다. 최댓값이나 최솟값을 $O(\log N)$에 찾고 삽입/삭제할 수 있도록 도와줍니다.
2. 힙 정렬 (Heap Sort): 힙 자료구조를 이용한 정렬 알고리즘입니다.

요약

완전 이진 트리는 노드가 위에서 아래로, 왼쪽에서 오른쪽으로 차례대로 채워지는 이진 트리입니다. 이 특성 덕분에 빈틈없이 배열에 저장할 수 있으며, 인덱스 계산만으로 부모-자식 노드 간의 빠른 이동이 가능합니다. 인터뷰에서 힙(Heap)과 관련된 질문을 받는다면, 그 근간이 되는 완전 이진 트리의 개념과 배열 구현의 이점을 함께 설명하는 것이 좋습니다.