이진트리 구조와 순회 방식의 선택 기준
이진트리의 형태별 제약, 순회 방식, 저장 구조와 균형화 전략을 실무 관점에서 정리한다.
2026-08-14 · 최초 발행 2024-04-29
노드의 자식 수가 둘로 제한되는 구조
이진트리는 각 노드가 왼쪽과 오른쪽을 합쳐 최대 두 개의 자식을 갖는 유계 트리다. 탐색과 정렬, 우선순위 큐, 식 트리처럼 시스템 내부에서 반복적으로 쓰이는 구조는 이 제한을 바탕으로 성능과 구현 방식을 결정한다.
형태는 같아 보여도 제약은 다르다. 포화 이진트리는 모든 내부 노드가 정확히 두 자식을 가지며 모든 리프가 같은 레벨에 놓인다. 완전 이진트리는 마지막 레벨을 제외한 레벨이 모두 채워지고, 마지막 레벨은 왼쪽부터 채운다. 엄밀 이진트리는 각 노드의 자식 수를 0 또는 2로 제한해 자식이 하나뿐인 노드를 허용하지 않는다.
편향 이진트리는 자식이 한 방향으로 이어지는 선형 구조이며, 최악의 높이는 n이다. 반대로 Knuth 쓰레드 이진트리는 Null 링크를 중위 선행자 또는 후행자 링크로 바꾸어 순회 비용을 줄이는 변형이다. 이 용어의 사용에는 이견이 있어 최신 정보 확인이 필요하다.
높이가 탐색 비용을 결정한다
포화 트리의 높이가 h이면 노드 수는 정확히 2^(h+1)-1개다. 완전 트리에서는 최소 2^h개가 된다. 높이를 낮게 유지하는 일이 탐색과 갱신 비용 절감으로 이어지는 이유다.
균형이 유지되는 트리는 평균 O(log n)을 목표로 한다. 한쪽으로 기울면 최악 O(n)까지 성능이 저하된다. AVL, Red-Black, Treap, Splay 같은 BST 변형은 회전 연산으로 높이를 관리한다.
저장 방식도 형태에 따라 달라진다. 포인터 기반 연결 구조는 삽입과 삭제에 유연하지만 포인터 오버헤드가 있다. 완전 트리나 힙처럼 형태가 정해진 경우에는 배열 표현이 적합하다. 인덱스를 1부터 잡으면 왼쪽 자식은 2i, 오른쪽 자식은 2i+1로 매핑된다. 연속 메모리를 사용하므로 캐시 친화적이지만, 트리 형태에는 제약이 생긴다.
순회 순서가 달라지면 쓰임도 달라진다
순회는 노드를 방문하는 순서를 정한다.
- 전위 순회(preorder): 중 → 왼 → 오
- 중위 순회(inorder): 왼 → 중 → 오
- 후위 순회(postorder): 왼 → 오 → 중
재귀와 반복(스택) 방식으로 구현할 수 있으며, 모든 순회의 시간 복잡도는 O(n), 공간 복잡도는 O(h)다. BST의 중위 순회는 정렬된 순서를 제공한다. 전위와 후위 순회는 서브트리 복제·해제, 식 평가에 맞는다. 쓰레드 이진트리는 Null 링크를 이용해 중위 순회에서 스택과 재귀를 제거하고 순회의 상수 계수를 낮춘다.
루트가 Null이면 빈 시퀀스를 반환한다. 구조에 순환 참조가 생길 수 있다면 방문 마킹이나 구조 불변식으로 검증해야 한다. 높이 h가 큰 트리에서는 재귀 대신 반복 구현을 사용해 스택 오버플로우를 피한다.
인덱스부터 구간 질의까지
메모리 내 인덱스와 심볼 테이블에서는 균형 BST로 평균 O(log n) 탐색과 갱신을 확보할 수 있다. 다만 디스크 인덱스에는 B-Tree 계열이 권장된다.
우선순위 큐는 완전 이진트리와 배열을 결합한 힙으로 구현할 수 있다. 삽입과 삭제는 O(log n), 최댓값 또는 최솟값 접근은 O(1)이다. 식 트리(Expression/AST)는 전위·후위 순회를 통해 평가, 코드 생성, 최적화 파이프라인을 구성한다.
세그먼트 트리와 머지 트리는 구간 합·최댓값·할당·지연 전파 같은 범위 질의와 갱신에 O(log n)을 보장한다. 허프만 코딩 트리는 빈도 기반의 최적 접두 코딩을 만들고 압축률 개선에 쓰인다.
n=1,000,000일 때 log2 n은 약 20단계다. 균형 상태의 탐색·삽입·삭제는 평균 O(log n)이지만 편향된 경우 최악 O(n)이 된다. 순회는 O(n)이며, 쓰레드 트리를 적용하면 프레임과 스택 비용을 제거해 워크로드에 따라 10~30% 상수 시간 절감 사례를 기대할 수 있다.
노드마다 포인터 2개와 메타데이터의 오버헤드가 생긴다. 완전 트리는 연속 메모리 구조로 캐시 적중률을 높일 수 있다. 이진·순서·균형 조건 같은 불변식을 지키는 것이 성능 안정성의 전제이며, 회전 연산은 원자성과 테스트를 확보해야 한다.
형태별 제약과 운영 특성
| 유형 | 성능(탐색/순회) | 확장성(삽입/삭제) | 일관성(형태 제약) | 안정성(높이 보장) | 운영 편의 |
|---|---|---|---|---|---|
| 포화(Perfect) | 탐색 최적, 순회 O(n) | 정적 구조 전제 | 강함: 모든 레벨 가득 참 | 높이 = log2(n+1)-1 | 예측 가능, 재구성 비용 큼 |
| 완전(Complete) | 힙 등에서 우수 | 말단 삽입 유리 | 중간 | 평균 높이 ≈ log n | 배열 구현 용이 |
| 엄밀(Strict) | 편향 가능성 존재 | 구조 제약으로 삽입 제한 | 강함: 0 또는 2자식 | 보장 없음 | 검증 용이 |
| Knuth(쓰레드) | 순회 상수 계수 우수 | 포인터 관리 복잡 | 중간 | 높이 자체는 미보장 | 스택 없는 순회, 구현 난도 |
| 편향(Skewed) | 최악 O(n) | 단순하나 비효율 | 약함 | 높이 = n-1 | 디버그 용이, 실무 비권장 |
Python으로 구현한 순회
Python 3.10+와 표준 라이브러리만으로 재귀 순회와 스택 기반 중위 순회를 구현할 수 있다.
from collections import deque
from typing import Optional, Generator, Any
class Node:
__slots__ = ("key", "left", "right")
def __init__(self, key: Any, left: Optional["Node"]=None, right: Optional["Node"]=None):
self.key, self.left, self.right = key, left, right
# 재귀 순회
def preorder(root: Optional[Node]) -> Generator[Any, None, None]:
if not root:
return
yield root.key
yield from preorder(root.left)
yield from preorder(root.right)
def inorder(root: Optional[Node]) -> Generator[Any, None, None]:
if not root:
return
yield from inorder(root.left)
yield root.key
yield from inorder(root.right)
def postorder(root: Optional[Node]) -> Generator[Any, None, None]:
if not root:
return
yield from postorder(root.left)
yield from postorder(root.right)
yield root.key
# 반복(스택) 중위 순회
def inorder_iter(root: Optional[Node]):
stack, cur = [], root
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
yield cur.key
cur = cur.right
# 예시 트리 구성
# A
# / \
# B C
# / \ \
# D E F
root = Node("A",
Node("B", Node("D"), Node("E")),
Node("C", None, Node("F")))
print(list(preorder(root))) # ['A', 'B', 'D', 'E', 'C', 'F']
print(list(inorder(root))) # ['D', 'B', 'E', 'A', 'C', 'F']
print(list(postorder(root))) # ['D', 'E', 'B', 'F', 'C', 'A']
print(list(inorder_iter(root))) # 동일 결과깊은 트리를 다룰 때는 sys.setrecursionlimit 조정보다 반복 구현을 선택한다. 왼쪽·오른쪽 참조에 무한 루프가 없는지 확인하는 불변식 점검 단위 테스트도 필요하다.