포화이진트리의 구조와 용량 계산, 활용 패턴

리프 높이가 맞춰진 이진 트리

포화이진트리(Perfect Binary Tree)는 모든 내부 노드가 정확히 두 자식을 가지며, 모든 리프가 같은 레벨에 있는 이진 트리다. 자식의 완결성과 리프 레벨의 균일성을 함께 만족하므로, 이진 트리의 구조적 밀도와 균형을 분석할 때 기준점이 된다.

정 이진 트리(Full/Proper Binary Tree)는 각 노드의 자식 수가 0 또는 2인 트리다. 리프가 모두 같은 레벨에 있을 필요는 없다. 완전 이진 트리(Complete Binary Tree)는 레벨 순서로 왼쪽부터 빈틈없이 채우되, 마지막 레벨만 부분적으로 비어 있을 수 있다.

Full Binary Tree는 문헌에 따라 정 이진 트리 또는 포화이진트리를 뜻하기도 한다. 한국어 용어에서는 포화를 Perfect, 정을 Full/Proper로 나누어 쓰는 편이 혼동을 줄인다.

레벨과 높이로 계산하는 노드 수

루트의 레벨을 L=1로 두면 포화이진트리의 총 노드 수 N은 2^L − 1이다. 리프 수는 2^(L−1), 내부 노드 수는 2^(L−1) − 1이 된다.

높이를 간선 수 h로 정의하면 h=L−1이고, 총 노드 수는 2^(h+1) − 1, 리프 수는 2^h로 표현된다.

정 이진 트리에서는 내부 노드 수를 I, 리프 수를 F라고 할 때 F = I + 1, 총 노드 수는 N = 2I + 1이라는 관계가 성립한다.

모든 노드의 수가 2^(n−1)이라는 표현은 일반적으로 맞지 않는다. 포화이진트리의 정확한 노드 수 공식은 N = 2^L − 1, 또는 N = 2^(h+1) − 1이다.

배열로 다루기 쉬운 균형 구조

리프가 같은 레벨에 배치되므로 포화이진트리는 균형을 보장한다. 높이는 h = O(log N)이며, 탐색과 갱신의 상한을 분석하기 좋다.

노드를 1-기반 배열에 넣으면 부모 인덱스 i의 자식은 2i, 2i+1이고, 부모는 ⌊i/2⌋로 찾을 수 있다. 포인터 오버헤드를 줄이고 캐시 지역성을 높이는 배치가 가능하다.

서브트리 역시 같은 포화 또는 정 구조를 재귀적으로 유지한다. 이 성질은 균등한 과업 분배와 병렬 분할에 맞는다. 목표 높이 또는 리프 수가 정해지면 총 노드 수와 메모리 요구량을 바로 산출할 수 있으며, 전처리에서 다음 2의 거듭제곱까지 패딩해 구조를 정형화할 수도 있다.

⤢✕

구간 연산과 메모리 분할에서의 적용

세그먼트 트리와 레인지 쿼리 구조에서는 길이 n인 배열을 다음 2^k ≥ n 크기까지 패딩한 뒤 리프에 배치한다. 내부 노드는 합이나 최솟값 같은 결합 연산을 상향식으로 구성한다. 이 방식은 구간 쿼리를 O(log N)에 처리하고, 포인트 또는 구간 갱신도 O(log N)에 수행한다. 균형 깊이 덕분에 최악과 평균의 차이가 줄고 상수 인자를 예측하기 쉽다.

버디 메모리 할당자(Buddy Allocator)는 2^k 크기의 메모리를 요청 크기에 맞을 때까지 1/2씩 나눈다. 메모리를 반납하면 버디 블록을 병합한다. 완전한 2진 분할 트리 형태를 사용하므로 병합 여부를 빠르게 판별할 수 있고 메타데이터도 단순해진다.

게임 트리나 결정 트리에서 최대 깊이 d와 균등한 분기 규칙을 적용할 때도 포화형 구조가 기준이 된다. 레벨별로 확장하고 탐색·평가를 진행하면 2^d − 1을 기준으로 노드 수를 예측할 수 있어 시간과 메모리 상한을 세우고 병렬 배치를 구성하기 좋다.

FFT와 합병 정렬처럼 분할 정복을 병렬화할 때는 포화형 태스크 트리로 워크 스틸링 균형화를 설계할 수 있다. 스레드 풀만으로 작업을 구성하는 경우보다 작업 그래프의 깊이와 폭을 추정하기 쉽다.

깊이와 용량을 미리 산정하는 방법

탐색과 갱신은 O(log N) 깊이에서 이뤄지며, 최악과 평균의 편차를 작게 유지할 수 있다. 배열로 표현하면 포인터를 제거해 구조체 오버헤드를 줄일 수 있고, 노드당 수바이트를 절감한다. 순차 접근 패턴은 캐시 미스율 감소에도 유리하다.

루트 레벨을 1로 두고 L=20일 때 총 노드 수는 N=2^20−1=1,048,575, 리프 수는 2^19=524,288이다. 이처럼 용량을 사전에 계산하면 메모리 블록 예약과 GC·파편화 리스크 완화에 활용할 수 있다.

구분	성능(깊이)	확장성(증설/패딩)	일관성(형태)	안정성(분석 용이)	운영 편의(배열 매핑)
포화(Perfect)	O(log N), 최악=평균	2의 거듭제곱 단위 증설 권장	리프 레벨 동일	수식/상한 명확	매우 용이
정(Full/Proper)	O(height), 균형 미보장	구조 유연, 불균형 가능	자식 0/2만 허용	일부 성질만 보장	용이
완전(Complete)	O(log N), 힙 최적	n±1 노드 증감 용이	마지막 레벨만 부분 비움	실용적 상한 확보	매우 용이

구조 조건을 확인하는 구현

포화 여부를 판별할 때는 루트 노드에서 왼쪽 가장자리를 따라 높이 h를 계산하고, 전체 노드 수를 센다. 이어서 cnt == 2^(h+1) − 1인지 확인하면서 모든 내부 노드가 두 자식을 가지는지도 검증한다.

빈 트리(None)는 포화로 보거나 정책에 따라 False로 처리할 수 있다. 한쪽 자식만 있는 노드를 만나면 즉시 False다. 큰 트리에서는 overflow를 고려해 64비트 정수를 사용한다.

from collections import deque
from typing import Optional

class Node:
    __slots__ = ("val", "left", "right")
    def __init__(self, val, left: Optional["Node"]=None, right: Optional["Node"]=None):
        self.val, self.left, self.right = val, left, right

def height_left_spine(root: Optional[Node]) -> int:
    # 간선 기준 높이 h 반환
    h, cur = -1, root
    while cur:
        h += 1
        cur = cur.left
    return h

def is_perfect(root: Optional[Node]) -> bool:
    if root is None:
        return True
    # 높이 h와 기대 노드수
    h = height_left_spine(root)
    expected = (1 << (h + 1)) - 1
    # BFS로 노드 수와 구조 확인
    q = deque([root])
    count = 0
    while q:
        node = q.popleft()
        count += 1
        l, r = node.left, node.right
        if (l is None) ^ (r is None):  # 한쪽만 있으면 실패
            return False
        if l: q.append(l)
        if r: q.append(r)
    return count == expected