이진 트리 순회와 높이, 재귀 깊이가 성능을 가르는 원리
이진 트리 순회는 전위·중위·후위와 레벨 네 가지로 나뉘고, 높이는 루트에서 리프까지의 간선 수다. 파이썬 코드로 네 순회와 높이 계산을 살펴보고, 높이가 O(log n)과 O(n)을 가르는 원리와 재귀 스택 오버플로를 피하는 반복 순회까지 정리한다.
목차
이진 트리 순회는 트리에 담긴 모든 노드를 정해진 규칙대로 한 번씩 방문하는 작업이다. 방문 시점을 언제로 잡느냐에 따라 전위·중위·후위 세 가지 깊이 우선 순회와, 트리를 층 단위로 훑는 레벨(너비 우선) 순회로 나뉜다. 트리의 높이는 루트에서 가장 먼 리프까지 이어지는 간선의 개수이고, 이 높이가 순회에 필요한 재귀 깊이와 탐색 성능을 그대로 정한다. 순회 네 가지의 차이는 코드 몇 줄이면 드러나지만, 높이가 왜 O(log n)과 O(n)을 가르는지까지 알아야 실무에서 느린 탐색과 스택 오버플로를 피한다.
이 글은 각 노드가 자식을 최대 둘까지 갖는 이진 트리를 기준으로 순회와 높이의 개념, 그리고 파이썬 코드 구현에 초점을 둔다. 예제는 파이썬으로 쓰고, 재귀 한도 같은 언어별 사실은 파이썬 공식 문서를 근거로 삼는다. AVL 트리나 레드블랙 트리처럼 삽입·삭제할 때 스스로 균형을 맞추는 자가 균형 트리의 재조정 알고리즘은 다루지 않는다.
이진 트리의 높이와 깊이
먼저 용어를 맞춘다. 트리는 값을 담는 점인 노드와 노드를 잇는 선인 간선으로 이루어진다. 맨 위 노드가 루트, 자식이 없는 끝 노드가 리프다. 이진 트리는 모든 노드가 왼쪽·오른쪽 자식을 최대 하나씩만 갖는 트리다.
높이(height)와 깊이(depth)는 자주 헷갈리지만 방향이 반대다. 깊이는 루트에서 특정 노드까지 내려오는 간선 수이고, 높이는 특정 노드에서 가장 먼 리프까지 내려가는 간선 수다. 트리 전체의 높이는 루트의 높이, 곧 루트에서 가장 깊은 리프까지의 간선 수와 같다.
여기서 관례를 하나 정해야 한다. 간선을 세면 노드가 하나뿐인 트리의 높이는 0, 빈 트리의 높이는 -1이다. 노드 개수로 세는 관례를 쓰면 각각 1과 0이 되어 값이 하나씩 커진다. 이 글은 간선 기준(빈 트리 -1)을 쓴다. 면접이나 문서에서 높이 값이 하나 어긋난다면 대개 이 관례 차이다.
높이는 노드 수 n에 따라 범위가 정해진다. 자식이 고르게 찬 균형 트리라면 높이가 약 ⌊log₂ n⌋까지 낮아지고, 한쪽으로만 이어진 편향 트리라면 높이가 n − 1까지 커진다. 노드가 100만 개일 때 완전히 균형 잡힌 트리의 높이는 약 20(2²⁰ ≈ 1,048,576)이지만, 한 줄로 늘어진 트리의 높이는 999,999다. 같은 노드 수인데 높이가 5만 배 차이 난다. 이 격차가 뒤에서 성능을 가르는 핵심이다.
트리는 교과서 밖에서도 흔하다. 파일 시스템의 디렉터리, 브라우저의 DOM, 데이터베이스 인덱스가 모두 트리 구조다. 이들을 뒤지거나 화면에 그리는 일이 결국 순회이고, 응답 속도를 좌우하는 것이 높이다.
깊이 우선 순회: 전위·중위·후위
세 순회는 방문하는 노드는 같고, 부모 노드를 언제 처리하느냐만 다르다. 전위는 부모를 먼저(부모→왼쪽→오른쪽), 중위는 왼쪽 다음에(왼쪽→부모→오른쪽), 후위는 마지막에(왼쪽→오른쪽→부모) 처리한다. 왼쪽을 오른쪽보다 먼저 보는 것은 세 순회가 똑같다.
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorder(node):
if node is None:
return
print(node.val) # 부모 먼저
preorder(node.left)
preorder(node.right)
def inorder(node):
if node is None:
return
inorder(node.left)
print(node.val) # 왼쪽 다음 부모
inorder(node.right)
def postorder(node):
if node is None:
return
postorder(node.left)
postorder(node.right)
print(node.val) # 마지막에 부모세 함수의 뼈대는 똑같다. 왼쪽 서브트리를 재귀로 처리하고 오른쪽 서브트리를 재귀로 처리하되, 그 사이 어디에서 자기 노드를 처리하느냐만 옮겨 놓았다.
| 순회 | 방문 순서 | 대표 용도 |
|---|---|---|
| 전위(preorder) | 부모 → 왼쪽 → 오른쪽 | 트리 복제, 구조 직렬화 |
| 중위(inorder) | 왼쪽 → 부모 → 오른쪽 | 이진 탐색 트리를 정렬 순서로 출력 |
| 후위(postorder) | 왼쪽 → 오른쪽 → 부모 | 트리 삭제·해제, 수식 트리 계산 |
| 레벨(level order) | 위에서 아래로, 같은 층은 왼쪽부터 | 층별 처리, 트리 최단 거리 |
중위 순회가 특히 쓸모 있다. 이진 탐색 트리(왼쪽 자식 < 부모 < 오른쪽 자식 규칙을 지키는 트리)를 중위로 훑으면 값이 오름차순으로 나온다. 후위 순회는 자식을 다 처리한 뒤 부모를 처리하므로 트리를 통째로 해제하거나 수식 트리를 아래에서 위로 계산할 때 맞다. 컴파일러가 소스 코드를 추상 구문 트리(AST)로 바꿔 다루는 과정에서도 이 후위 계산이 등장한다. 전위 순회는 부모를 먼저 기록하므로 트리 구조를 그대로 복제하거나 직렬화할 때 쓴다.
전위와 중위 순회 결과를 함께 알면 원래 트리를 유일하게 복원할 수 있다. 중위가 왼쪽·오른쪽 서브트리의 경계를 알려 주고, 전위의 첫 값이 루트를 짚어 주기 때문이다. 트리를 저장했다가 다시 세울 때 이 성질을 쓴다.
레벨 순회는 언제 쓰나
레벨 순회는 같은 층의 노드를 위에서 아래로, 같은 층 안에서는 왼쪽에서 오른쪽으로 방문한다. 트리에서 루트로부터 몇 단계 떨어졌는가가 곧 거리이므로, 층 단위 처리나 최단 거리 계산이 필요할 때 쓴다.
깊이 우선 순회가 재귀(내부적으로 스택)로 굴러가는 것과 달리, 레벨 순회에는 큐가 필요하다. 먼저 넣은 노드를 먼저 꺼내야 층 순서가 유지되기 때문이다. 이 대목은 스택과 큐의 LIFO·FIFO 차이를 먼저 짚어 두면 훨씬 선명하다.
from collections import deque
def level_order(root):
if root is None:
return
q = deque([root])
while q:
node = q.popleft()
print(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)파이썬에서는 collections.deque를 큐로 쓴다. 리스트의 pop(0)은 앞을 꺼낼 때 나머지 원소를 한 칸씩 당겨 O(n)이 들지만, deque.popleft()는 O(1)이라 큐에 알맞다. 각 노드를 큐에 한 번 넣고 한 번 빼므로 전체는 O(n) 시간이 든다.
레벨 순회는 트리를 한 줄 문자열로 저장하는 직렬화의 기본형이기도 하다. 층 순서대로 값을 이어 붙이고 빈 자리를 표시해 두면, 같은 순서로 읽어 트리를 그대로 복원한다.
트리 높이는 어떻게 구하나
높이는 재귀로 구한다. 빈 노드면 -1을 돌려주고, 아니면 왼쪽·오른쪽 서브트리 높이 중 큰 값에 1을 더한다. 앞에서 정한 정의를 코드로 그대로 옮긴 꼴이다.
def height(node):
if node is None:
return -1 # 빈 트리는 -1 (간선 기준)
return 1 + max(height(node.left), height(node.right))이 함수는 모든 노드를 한 번씩 방문하므로 O(n) 시간이 든다. 노드 개수 기준 관례를 쓰면 빈 노드에서 0을 돌려주고 그대로 큰 값에 1을 더하면 된다. 어느 관례든 트리를 한 번 훑는 비용은 같다. 재귀 대신 레벨 순회로 층수를 세어도 같은 높이를 얻는데, 큐로 세는 편은 편향 트리에서 콜스택을 아끼는 이점이 있다. 그 이유는 다음 절에서 이어진다.
높이가 성능을 좌우하는 이유
순회 자체는 어떤 트리든 모든 노드를 한 번 방문하므로 늘 O(n)이다. 성능이 갈리는 곳은 탐색·삽입·삭제처럼 루트에서 한쪽 경로만 따라 내려가는 연산이다. 이 연산들의 비용은 높이에 비례한다.
이진 탐색 트리에서 값을 찾을 때는 루트에서 시작해 찾는 값이 크면 오른쪽, 작으면 왼쪽으로 한 단계씩 내려간다. 최악에는 리프까지 내려가므로 비교 횟수가 높이만큼이다. 균형이 잡혀 높이가 log₂ n이면 O(log n), 한쪽으로 편향돼 높이가 n − 1이면 O(n)으로 떨어진다.
| 구분 | 높이 | 탐색 복잡도 | 재귀 순회 스택 |
|---|---|---|---|
| 균형 트리 | 약 log₂ n | O(log n) | O(log n) |
| 편향 트리 | n − 1 | O(n) | O(n) |
앞의 100만 노드 예로 돌아가면, 균형 트리에서는 최대 약 20번 비교로 값을 찾지만 편향 트리에서는 최악에 100만 번 가까이 비교한다. 재귀로 순회할 때 쌓이는 콜스택도 높이만큼 깊어진다. 균형 트리는 스택 깊이가 약 20이라 문제없지만, 편향 트리는 스택이 노드 수만큼 깊어져 언어의 재귀 한도를 넘긴다. 자가 균형 트리가 높이를 log n 근처로 눌러 두는 이유가 여기 있다.
데이터베이스가 B-트리 계열 인덱스를 쓰는 것도 같은 이유다. 노드 하나에 자식을 수백 개씩 두어 높이를 서너 단계로 억누르면, 수억 건에서도 디스크 접근을 몇 번으로 끝낸다. 이진 트리든 다진 트리든 원리는 하나다. 높이를 낮게 유지하면 탐색이 빨라진다.
재귀 스택을 넘길 때: 반복 순회
편향 트리를 재귀로 순회하면 콜스택이 깊이만큼 쌓여 런타임이 죽을 수 있다. 파이썬 공식 문서에 따르면 재귀 한도는 무한 재귀가 C 스택을 넘치게 해 파이썬이 죽는 것을 막는 안전장치이며, 한도를 넘으면 RecursionError가 발생한다. CPython 기본 인터프리터에서 sys.getrecursionlimit()은 1000을 돌려주므로, 깊이가 1000을 넘는 편향 트리를 재귀로 훑으면 여기서 걸린다.
sys.setrecursionlimit()으로 한도를 올릴 수도 있지만, 파이썬 공식 문서는 한도를 너무 높이면 C 스택이 실제로 넘쳐 인터프리터가 죽을 수 있으니 조심하라고 못 박는다. 근본 해법은 재귀를 명시적 스택으로 바꾼 반복 순회다. 스택을 힙 메모리에 두면 콜스택 한도와 무관하게 깊은 트리도 훑는다.
def preorder_iter(root):
if root is None:
return
stack = [root]
while stack:
node = stack.pop()
print(node.val)
if node.right: # 오른쪽을 먼저 넣어야
stack.append(node.right)
if node.left: # 왼쪽이 먼저 꺼내진다
stack.append(node.left)전위 순회를 반복으로 옮기면 이렇게 된다. 오른쪽 자식을 먼저 스택에 넣어야 왼쪽이 먼저 꺼내진다는 점만 주의하면 된다. 중위·후위도 같은 방식으로 명시적 스택을 써서 옮길 수 있다. 공간을 더 아끼려면 리프의 빈 포인터를 잠시 이어 붙여 추가 공간을 O(1)로 줄이는 모리스 순회 같은 기법도 있지만, 코드가 까다로워 트리 깊이가 확실히 얕다면 재귀가 읽기 편하다.
순회 선택 기준
정렬된 순서가 필요하면 중위, 자식부터 처리해야 하면 후위, 구조를 위에서부터 남겨야 하면 전위, 층 단위나 최단 거리가 필요하면 레벨 순회를 고른다. 트리 깊이가 수백을 넘길 여지가 있으면 재귀 대신 반복이나 레벨 순회로 콜스택을 지킨다. 순회 코드는 짧지만, 다루는 트리의 높이가 어디까지 커질 수 있는지를 먼저 가늠하는 습관이 실무에서 사고를 막는다.
