이진 트리의 모양·높이·순회를 구분하고 재귀와 반복 구현, 순환·공유 검사, 직렬화·복원, 지름·균형·수식 평가를 실제 예제로 설명한다.
개요: 자식 위치가 둘인 계층 구조
이진 트리(binary tree)는 각 노드가 왼쪽과 오른쪽이라는 두 자식 위치를 갖는 트리다. 각 위치는 비어 있거나 다른 이진 트리의 루트를 가리킨다. 루트가 없는 빈 트리도 정의에 포함할 수 있다. 왼쪽만 있는 노드와 오른쪽만 있는 노드는 다른 구조다.
문서의 예제 트리는 A를 루트로 하며 왼쪽 B 아래에 D,E가 있고 오른쪽 C 아래에는 오른쪽 자식 F만 있다. 같은 여섯 값을 담더라도 어떤 자식 위치에 놓는지에 따라 탐색·순회와 표현 의미가 달라진다.
이진 트리 자체에는 값이 정렬되어 있다는 조건이 없다. 이진 탐색 트리는 왼쪽·오른쪽 하위 트리의 값 범위 조건을 추가하고, 이진 힙은 완전한 모양과 부모·자식 우선순위 조건을 추가한 구조다. 일반 이진 트리에서 자동으로 로그 시간 검색이 되는 것은 아니다.
이 문서는 용어와 모양, 재귀·반복 순회, 구조 검증, 직렬화·복원, 높이·지름·균형과 수식 평가를 설명한다. Python 3.9.6에서 실행한 예제를 사용하며 값 중복과 실제 노드 동일성을 구분한다.
노드·루트·부모·잎·하위 트리
루트는 전체 구조의 시작 노드다. 루트를 제외한 각 노드에는 부모가 정확히 하나 있고, 부모를 따라가면 루트에 도달한다. 자식이 없는 노드는 잎이다. 한 노드와 그 아래 모든 후손은 그 노드를 루트로 하는 하위 트리를 이룬다.
이 문서의 TreeNode는 값과 왼쪽·오른쪽 참조만 저장한다. 부모 참조는 저장하지 않는다. 위로 이동할 필요가 있는 알고리즘은 별도 부모 정보나 방문 경로를 보관해야 한다. 모든 트리 구현이 부모 필드를 가진다고 가정하지 않는다.
아래 A의 왼쪽 하위 트리는 B,D,E 세 노드다. C의 왼쪽 위치는 비어 있으며 F는 잎이다. 값 None을 담은 실제 노드와 자식 위치 None도 다르다. TreeNode(None)은 노드가 존재하며 값만 None이다.
클래스가 left와 right를 갖는다고 아무 연결이나 올바른 트리가 되지는 않는다. 자기 자신을 자식으로 넣거나 같은 노드를 두 부모가 공유하면 일반적인 트리 계약을 벗어난다. 뒤에서 별도 구조 검사를 구현한다.
예제 코드
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def sample_tree():
return TreeNode('A', TreeNode('B', TreeNode('D'), TreeNode('E')),
TreeNode('C', None, TreeNode('F')))
def size_of(node):
if node is None:
return 0
return 1 + size_of(node.left) + size_of(node.right)
def height_of(node):
if node is None:
return -1
return 1 + max(height_of(node.left), height_of(node.right))
def recursive_order(root, order):
if order not in ('pre', 'in', 'post'):
raise ValueError('invalid order')
result = []
def visit(node):
if node is None:
return
if order == 'pre':
result.append(node.value)
visit(node.left)
if order == 'in':
result.append(node.value)
visit(node.right)
if order == 'post':
result.append(node.value)
visit(root)
return result
root = sample_tree()
print(root.value, root.left.value, root.right.value)
print(root.right.left is None)
print(root.right.right.left is None and root.right.right.right is None)
print(TreeNode(None) is None)
실행 결과
A B C
True
True
False깊이와 높이는 어느 방향의 거리인가
깊이는 루트에서 해당 노드까지의 거리이고 높이는 해당 노드에서 가장 먼 후손까지 내려가는 거리다. 이 문서에서는 간선 수로 센다. 루트의 깊이는 0, 잎의 높이는 0이며 빈 트리의 높이는 −1로 정의한다.
노드 수로 높이를 세는 자료도 있으므로 수치만 비교하면 한 차이가 날 수 있다. 빈 트리 −1을 쓰면 비어 있지 않은 트리의 높이를 1+max(왼쪽 높이,오른쪽 높이)로 일관되게 계산할 수 있다.
예제에서 D의 깊이는 2이고 B의 높이는 1이며 전체 높이는 2다. 깊이는 자신의 조상 경로, 높이는 후손 구조에 달려 있다. 루트만 하나인 트리는 깊이와 높이가 모두 0이다.
크기 size는 노드 수로 높이와 다르다. 같은 크기의 트리도 완만하게 갈라지면 낮고 한쪽으로만 이어지면 높다. 알고리즘의 보조 공간과 검색 비용을 분석할 때 n과 h를 구분한다.
예제 코드
root = sample_tree()
print(size_of(root), height_of(root))
print(size_of(None), height_of(None))
print(size_of(TreeNode('only')), height_of(TreeNode('only')))
실행 결과
6 2
0 -1
1 0포화·완전·정 이진 트리의 차이
포화 이진 트리(perfect binary tree)는 모든 내부 노드가 두 자식을 갖고 모든 잎이 같은 깊이에 있는 형태다. 높이 h를 간선 수로 셀 때 노드 수는 2^(h+1)−1이다. 빈 트리 처리와 용어 번역은 자료마다 다를 수 있으므로 정의를 먼저 확인한다.
완전 이진 트리(complete binary tree)는 마지막 층 이전이 모두 차 있고 마지막 층을 왼쪽부터 채운 형태다. 마지막 층에 빈자리가 있을 수 있으므로 포화와 같지 않다. 배열 기반 이진 힙에서 사용하는 모양 조건이다.
정 이진 트리(full 또는 proper binary tree)는 각 노드의 자식 수가 0 또는 2인 형태를 말한다. 한 자식만 가진 노드는 없지만 잎의 깊이가 모두 같을 필요는 없다. full이라는 말을 perfect의 의미로 쓰는 자료도 있어 영어 단어만 외우는 것보다 조건을 직접 쓰는 편이 낫다.
예제 A-B,C / B-D,E / C-오른쪽F는 C의 왼쪽이 비고 오른쪽만 있으므로 완전하지도, 모든 내부 노드가 두 자식을 갖지도 않는다. 노드 수만 보고 모양을 판정할 수 없다.
균형과 로그 높이는 자동 조건이 아니다
한쪽 자식만 계속 이어지는 n노드 이진 트리의 높이는 n−1이다. 각 노드에 자식이 최대 둘이라는 제약은 아래로 얼마나 길어질지 제한하지 않는다. 이진 트리라는 말만으로 O(log n) 탐색을 주장하면 안 된다.
균형이라는 말도 정의가 필요하다. AVL 계열에서 사용하는 높이 균형은 모든 노드의 왼쪽·오른쪽 하위 트리 높이 차이가 1 이하라는 조건이다. 루트에서만 차이가 작다고 전체가 균형인 것은 아니다.
다른 균형 트리는 다른 불변식으로 높이를 제한한다. 이진 힙의 완전한 모양은 값 범위 기반 검색을 제공하지 않으며, 균형 이진 탐색 트리는 회전과 재색칠 같은 별도 유지 작업을 할 수 있다. 모양과 값 조건은 서로 다른 축이다.
아래 같은 7노드라도 한쪽 사슬의 높이는 6, 포화한 형태의 높이는 2다. n이 같아도 재귀 호출 깊이와 루트에서 잎까지 이동 비용이 달라진다는 것을 보여 준다.
예제 코드
chain = None
for value in range(7):
chain = TreeNode(value, chain)
perfect = TreeNode(0, TreeNode(1, TreeNode(3), TreeNode(4)),
TreeNode(2, TreeNode(5), TreeNode(6)))
print(size_of(chain), height_of(chain))
print(size_of(perfect), height_of(perfect))
실행 결과
7 6
7 2크기와 높이의 재귀식
빈 하위 트리는 크기 0이다. 현재 노드가 있으면 크기는 1+왼쪽 크기+오른쪽 크기다. 두 하위 트리가 각각 정확한 크기를 반환한다는 가정에서 부모의 크기가 맞다는 귀납적 설명이 가능하다.
높이는 양쪽 높이 중 큰 값에 1을 더한다. 빈 높이 −1 때문에 잎에서는 1+max(−1,−1)=0이 된다. 크기는 두 값을 더하지만 높이는 최댓값을 선택하므로 반환값의 의미가 다르다.
각 함수를 한 번 실행하면 모든 노드를 한 번 방문해 O(n) 시간이다. 호출 스택은 현재 루트에서 내려간 경로에 비례하여 O(h+1)이다. 반환 결과 정수 하나만 보고 보조 공간이 무조건 O(1)이라고 설명하면 재귀 스택을 놓친다.
각 노드마다 height_of를 다시 호출하는 더 큰 알고리즘은 같은 하위 트리를 중복 순회할 수 있다. 지름이나 균형 검사는 필요한 정보를 한 번에 묶어 반환하면 중복 계산을 줄일 수 있으며 뒤에서 구현한다.
전위·중위·후위 순회를 같은 트리로 비교하기
전위 순회는 현재 노드, 왼쪽, 오른쪽 순서다. 중위는 왼쪽, 현재 노드, 오른쪽이며 후위는 왼쪽, 오른쪽, 현재 노드다. 세 방식은 방문하는 노드 집합은 같지만 현재 노드의 값을 처리하는 시점이 다르다.
예제 전위는 A,B,D,E,C,F이고 중위는 D,B,E,A,C,F, 후위는 D,E,B,F,C,A다. 전위는 부모를 먼저 기록하는 표현, 후위는 자식 결과를 먼저 알아야 하는 계산에 자연스럽다. 중위는 이진 탐색 트리의 값 순서를 읽을 때 쓰이지만 일반 트리에서는 정렬을 보장하지 않는다.
recursive_order는 result 하나에 append한다. 각 재귀 호출이 왼쪽 목록+현재+오른쪽 목록을 새로 이어 붙이는 방식은 편향 트리에서 반복 복사가 누적될 수 있으므로 결과 수집 방법도 비용에 영향을 준다.
아래 세 결과를 단순히 외우기보다 재귀식의 어느 위치에 처리 문장이 놓이는지 확인한다. 빈 트리는 어느 순회에서도 빈 결과다. 출력 목록 공간은 O(n)이고 호출 스택 공간은 따로 O(h+1)이다.
예제 코드
root = sample_tree()
for order in ['pre', 'in', 'post']:
print(order, ''.join(recursive_order(root, order)))
print(recursive_order(None, 'pre'))
실행 결과
pre ABDECF
in DBEACF
post DEBFCA
[]반복 전위: 오른쪽을 먼저 스택에 넣는 이유
스택은 마지막에 넣은 것을 먼저 꺼낸다. 전위의 왼쪽 우선 순서를 만들려면 현재 노드를 처리한 뒤 오른쪽 자식을 먼저 넣고 왼쪽을 나중에 넣는다. 다음 pop에서 왼쪽이 먼저 나온다.
왼쪽부터 push하면 오른쪽이 먼저 방문되어 A,C,F,B,E,D처럼 다른 순서가 된다. 유효한 탐색일 수는 있어도 약속한 왼쪽 우선 전위는 아니다. 스택에 넣는 순서와 실제 처리 순서를 구분한다.
스택에는 현재 경로를 따라 아직 처리하지 않은 형제 하위 트리들이 보관된다. 이진 트리에서 보조 스택은 O(h+1)으로 제한할 수 있지만 출력 결과 목록은 O(n)이다. “재귀를 제거했다”는 사실만으로 모든 추가 메모리가 사라지지는 않는다.
아래 세 반복 순회 함수 중 preorder의 결과를 먼저 확인한다. inorder와 postorder의 상태 의미는 다음 절에서 설명한다. 순환이나 공유 자식이 없는 정상 트리를 입력으로 가정한다.
예제 코드
def preorder(root):
result = []
stack = [] if root is None else [root]
while stack:
node = stack.pop()
result.append(node.value)
if node.right is not None:
stack.append(node.right)
if node.left is not None:
stack.append(node.left)
return result
def inorder(root):
result, stack = [], []
current = root
while current is not None or stack:
while current is not None:
stack.append(current)
current = current.left
current = stack.pop()
result.append(current.value)
current = current.right
return result
def postorder(root):
result = []
stack = [] if root is None else [(root, False)]
while stack:
node, expanded = stack.pop()
if expanded:
result.append(node.value)
continue
stack.append((node, True))
if node.right is not None:
stack.append((node.right, False))
if node.left is not None:
stack.append((node.left, False))
return result
print(''.join(preorder(sample_tree())))
print(preorder(None))
실행 결과
ABDECF
[]반복 중위: 아직 처리하지 않은 조상을 저장한다
중위 순회에서는 현재 노드 값을 읽기 전에 왼쪽 하위 트리를 끝내야 한다. current를 왼쪽으로 내려가면서 만나는 노드를 스택에 넣는다. 더 내려갈 수 없으면 스택에서 하나 꺼내 값을 처리하고 그 노드의 오른쪽 하위 트리로 이동한다.
스택은 단순한 “방문한 노드 목록”이 아니라 왼쪽 처리가 끝난 뒤 다시 돌아와 자신의 값을 처리해야 하는 조상들이다. 이 상태 의미를 알면 왜 current가 None이어도 stack이 남아 있으면 반복을 계속해야 하는지 이해할 수 있다.
각 노드는 한 번 스택에 들어가고 한 번 나온다. 안쪽 while이 있다고 O(n²)이 되는 것이 아니라 전체 push/pop 횟수를 세어 O(n)임을 알 수 있다. 스택의 최대 깊이는 트리 높이와 관련된다.
아래 결과 D,B,E,A,C,F는 값의 알파벳 정렬이 아니다. 일반 이진 트리의 중위 결과가 정렬된다는 잘못된 기대를 피한다. 정렬 성질을 얻으려면 이진 탐색 트리의 하위 범위 불변식이 필요하다.
예제 코드
root = sample_tree()
print(''.join(inorder(root)))
print(inorder(root) == sorted(inorder(root)))
실행 결과
DBEACF
False반복 후위: 다시 돌아올 상태를 표시한다
후위에서는 두 자식을 처리한 뒤 부모를 처리해야 한다. (노드,확장 여부)를 스택에 넣어 처음 만났을 때는 자식 작업을 추가하고, 나중에 확장 완료 상태로 다시 만났을 때 값을 처리한다.
stack에 현재 완료 항목, 오른쪽 초기 항목, 왼쪽 초기 항목을 그 순서로 넣으면 LIFO에 따라 왼쪽→오른쪽→현재가 된다. 완료 표시가 없으면 부모를 너무 일찍 처리하거나 같은 자식을 반복해서 넣을 수 있다.
이 방식은 재귀 호출의 “자식 호출에서 돌아온 뒤 실행할 부분”을 데이터로 표현한 것이다. 각 노드당 고정 개수의 상태만 다루므로 시간 O(n), 출력 외 보조 스택 O(h+1)이다. 일반 그래프에 적용하려면 방문 상태와 순환 처리 규칙이 더 필요하다.
후위는 수식 평가, 하위 트리 통계와 자식 자원을 먼저 처리해야 하는 작업에 유용하다. 실제 메모리 해제에서는 언어의 소유권·예외·소멸자 계약도 함께 고려해야 한다.
예제 코드
print(''.join(postorder(sample_tree())))
print(postorder(TreeNode(7)))
실행 결과
DEBFCA
[7]레벨 순회와 큐의 한 층 경계
레벨 순회는 루트부터 깊이가 작은 층을 먼저 처리한다. 큐에 루트를 넣고 앞에서 꺼내면서 존재하는 왼쪽·오른쪽 자식을 뒤에 넣으면 같은 깊이의 노드들이 다음 깊이보다 먼저 처리된다.
층별로 결과를 묶으려면 반복 시작 시점의 큐 길이를 저장한 범위만 처리한다. 그 동안 새로 넣는 자식은 다음 층에 속한다. 계속 변하는 큐 길이를 종료 기준으로 읽으면 현재 층과 다음 층을 섞을 수 있다.
아래 levels_of는 [['A'],['B','C'],['D','E','F']]를 반환한다. 전체 시간 O(n), 출력 O(n)이며 큐는 최대 폭 w에 비례하는 O(w) 공간을 사용한다. 큐가 인접한 두 층의 일부를 동시에 보유해도 같은 점근 상한으로 설명할 수 있다.
깊지만 좁은 트리와 얕지만 넓은 트리에서 DFS 스택과 BFS 큐의 최대 크기는 다를 수 있다. 재귀냐 반복이냐만 비교하지 말고 높이 h와 폭 w를 함께 본다.
예제 코드
def levels_of(root):
from collections import deque
if root is None:
return []
queue = deque([root])
result = []
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.value)
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
result.append(level)
return result
print(levels_of(sample_tree()))
print(levels_of(None))
실행 결과
[['A'], ['B', 'C'], ['D', 'E', 'F']]
[]배열 표현과 빈 위치의 비용
완전한 모양에서는 루트 인덱스 0, 왼쪽 2i+1, 오른쪽 2i+2로 배열에 저장할 수 있다. 이진 힙은 이 표현을 활용해 노드 포인터 없이 구조를 계산한다. 일반 이진 트리에도 위치를 배정할 수 있지만 빈칸이 많이 생길 수 있다.
오른쪽으로만 이어지는 깊이 h의 노드 인덱스는 2^(h+1)−2다. 노드는 h+1개뿐인데 그 위치까지 밀집 배열을 확보하면 지수적으로 많은 슬롯이 필요할 수 있다. 연결 표현이나 실제 존재하는 인덱스만 저장하는 사전을 고려할 이유다.
아래 오른쪽 사슬의 인덱스는 0,2,6,14,30이다. 노드 5개를 저장하려고 길이 31의 배열을 쓰는 모습이다. 어떤 모양에서 배열 표현이 효율적인지 설명할 때 완전성 조건이 빠지면 안 된다.
값 None이 허용되면 배열의 빈 위치 표시와 실제 None 값을 구분하는 별도 태그가 필요할 수 있다. 저장 형식은 노드 값의 표현 범위와 함께 설계한다.
예제 코드
indices = []
index = 0
for _ in range(5):
indices.append(index)
index = 2 * index + 2
print(indices)
print(len(indices), indices[-1] + 1)
실행 결과
[0, 2, 6, 14, 30]
5 31자식 공유와 순환을 검사하기
두 부모가 같은 노드를 자식으로 가리키면 DAG 형태의 공유 구조가 될 수 있지만 이 문서의 일반 트리는 아니다. 자기 자신이나 조상으로 돌아가는 자식 링크는 순환을 만든다. 단순 재귀 순회는 공유 부분을 중복 세거나 순환에서 종료하지 못할 수 있다.
validate_tree는 본 노드 객체를 집합에 저장한다. 같은 노드가 다시 나오면 순환 또는 공유 자식으로 거부한다. 값이 같은 서로 다른 노드는 정상적으로 허용한다. 이 검사는 둘을 구분해 진단하지는 않지만 트리 입력 계약을 확인하는 데 충분하다.
root에서 도달 가능한 구조만 검사하므로 어디에도 연결되지 않은 외부 노드들의 상태는 다루지 않는다. 시간과 방문 집합 공간은 O(n)이다. 모든 순회 앞에 검사를 붙이면 단순 순회의 O(h) 보조 공간 계약과 달라질 수 있으므로 경계에서 한 번 검증할지 정한다.
검사 중 구조가 동시에 바뀌지 않는다는 전제가 필요하다. 클래스 필드를 바꿀 권한이 있는 외부 코드가 검사 직후 링크를 수정하면 검사의 결과를 계속 보장할 수 없다.
예제 코드
def validate_tree(root):
seen = set()
stack = [] if root is None else [root]
while stack:
node = stack.pop()
if not isinstance(node, TreeNode):
raise ValueError('invalid child type')
if node in seen:
raise ValueError('cycle or shared child')
seen.add(node)
if node.right is not None:
stack.append(node.right)
if node.left is not None:
stack.append(node.left)
return len(seen)
print(validate_tree(sample_tree()))
shared = TreeNode('same')
invalid = TreeNode('root', shared, shared)
try:
validate_tree(invalid)
except ValueError:
print('shared rejected')
loop = TreeNode('loop')
loop.left = loop
try:
validate_tree(loop)
except ValueError:
print('cycle rejected')
print(validate_tree(TreeNode('x', TreeNode('x'), TreeNode('x'))))
실행 결과
6
shared rejected
cycle rejected
3깊은 트리와 재귀 한계
재귀 순회는 트리의 재귀 정의를 간결하게 표현하지만 호출 깊이가 높이에 비례한다. 편향 트리를 큰 크기로 받으면 Python의 재귀 제한이나 실행 환경의 스택 자원에 닿을 수 있다. 노드 수가 작다는 가정 없이 재귀 구현을 외부 입력에 무조건 적용하지 않는다.
재귀 제한을 크게 올리는 것만으로 안전한 입력 처리가 완성되지 않는다. 필요한 실제 메모리, 최악 높이와 응답 시간도 제한해야 한다. 반복 스택 방식은 언어 호출 스택의 제약을 피하지만 자체 자료구조의 메모리 비용은 남는다.
아래는 노드 2,000개를 반복으로 연결한 뒤 반복 전위·중위·후위 순회를 확인한다. 재귀 함수를 일부러 실패시켜 실행 환경을 불안정하게 만들지 않는다. 순회 출력 길이와 구조 검증이 모두 2,000이어야 한다.
깊은 트리를 역직렬화하는 코드도 재귀를 사용할 수 있다. 한 부분만 반복으로 바꾸고 전체 파이프라인이 깊이 제한에 안전하다고 결론 내리지 않는다. 이 문서의 decode_tree는 학습용 재귀 구현이며 깊이 제한이 있는 입력에 사용한다.
예제 코드
root = None
for value in range(2000):
root = TreeNode(value, root)
print(len(preorder(root)), len(inorder(root)), len(postorder(root)))
print(validate_tree(root))
실행 결과
2000 2000 2000
2000직렬화에는 빈 자식 위치도 기록한다
노드 값의 전위 목록만 저장하면 구조를 유일하게 복원할 수 없다. A의 왼쪽에 B가 있는 트리와 오른쪽에 B가 있는 트리는 전위 값이 모두 A,B다. 어느 자식 위치가 비었는지 정보가 필요하다.
encode_tree는 ['node',값]과 ['empty']라는 태그를 사용해 전위 순서로 기록한다. 실제 노드 값 None과 빈 위치를 구분한다. n개 노드의 유한 이진 트리에는 n+1개의 빈 자식 위치가 있으므로 토큰 수는 2n+1이다.
decode_tree는 node 뒤에 왼쪽과 오른쪽 표현을 각각 읽는다. 부족한 입력, 알 수 없는 토큰과 남는 토큰을 거부한다. 단순히 읽을 수 있는 앞부분만 복원하고 뒤를 무시하면 잘못된 자료를 정상으로 받아들일 수 있다.
노드 값은 이 예제에서 JSON으로 표현 가능한 값이라고 가정한다. 임의 객체의 정체성이나 공유 관계를 보존하는 형식이 아니며 원래 트리의 구조와 값을 새 노드들로 복원한다. 외부 대용량 입력에는 크기·깊이 제한을 별도로 둔다.
예제 코드
def encode_tree(root):
tokens = []
stack = [root]
while stack:
node = stack.pop()
if node is None:
tokens.append(['empty'])
else:
tokens.append(['node', node.value])
stack.append(node.right)
stack.append(node.left)
return tokens
def decode_tree(tokens):
iterator = iter(tokens)
def read():
try:
token = next(iterator)
except StopIteration:
raise ValueError('truncated tree') from None
if token == ['empty']:
return None
if not isinstance(token, list) or len(token) != 2 or token[0] != 'node':
raise ValueError('invalid token')
node = TreeNode(token[1])
node.left = read()
node.right = read()
return node
root = read()
marker = object()
if next(iterator, marker) is not marker:
raise ValueError('trailing token')
return root
import json
root = TreeNode(None, TreeNode('X'), None)
tokens = encode_tree(root)
print(tokens)
restored = decode_tree(json.loads(json.dumps(tokens)))
print(restored.value, restored.left.value, restored.right)
print(len(tokens), 2 * size_of(root) + 1)
실행 결과
[['node', None], ['node', 'X'], ['empty'], ['empty'], ['empty']]
None X None
5 5잘못된 직렬화와 값 중복 검사
직렬화 복원은 정상 입력의 왕복만 확인해서는 부족하다. 빈 토큰열, 자식 하나가 빠진 node, 정상 트리 뒤에 붙은 불필요한 토큰과 잘못된 태그를 각각 검사해야 한다. 오류가 어디서 발생하는지 구분하면 형식 계약이 명확해진다.
중복 값이 있다고 해서 형식이 모호해지는 것은 아니다. 빈 자식 태그를 기록했기 때문에 모든 값이 X여도 구조를 구분할 수 있다. 전위 값만 저장하는 방식과 달리 구조 정보가 따로 존재하기 때문이다.
아래 네 잘못된 입력은 모두 ValueError가 나고, 같은 값 X를 가진 왼쪽 자식과 오른쪽 자식 트리의 토큰은 다르다. 값의 순서만 대조하는 검증이 놓칠 수 있는 구조 차이를 확인한다.
JSON 문법을 통과했다는 사실은 이진 트리 형식까지 유효하다는 뜻이 아니다. 전송 형식 검사와 응용 스키마 검사는 다른 단계이며, 값의 허용 타입과 범위도 필요하면 추가로 검증한다.
예제 코드
invalid = [[], [['node', 1], ['empty']], [['empty'], ['empty']], [['bad']]]
rejected = 0
for tokens in invalid:
try:
decode_tree(tokens)
except ValueError:
rejected += 1
print(rejected)
left = TreeNode('X', TreeNode('X'), None)
right = TreeNode('X', None, TreeNode('X'))
print(preorder(left) == preorder(right))
print(encode_tree(left) == encode_tree(right))
실행 결과
4
True
False같은 트리 비교와 거울상 변환
두 트리가 같으려면 대응하는 노드 값뿐 아니라 빈 위치와 왼쪽·오른쪽 구조도 같아야 한다. 순회 값 하나만 비교하면 일부 다른 모양이 같은 값열을 가질 수 있다. same_tree는 대응 노드 쌍을 스택으로 비교한다.
mirror_tree는 각 노드의 왼쪽·오른쪽 참조를 교환한다. 새 데이터 노드를 만들지 않는 제자리 변환이므로 원본 구조가 바뀐다. 다른 코드가 같은 노드를 참조하고 있다면 그 코드에서도 변경을 보게 된다.
거울상 변환을 두 번 하면 원래 구조로 돌아온다. 이 성질은 테스트에 사용할 수 있지만 한 번의 변환이 올바른지는 별도 예상 결과로도 확인한다. 단순히 두 번 아무것도 하지 않는 잘못된 함수도 왕복 성질만은 통과할 수 있기 때문이다.
아래 예제의 거울 전위는 A,C,F,B,E,D다. 두 번 변환한 뒤 직렬화한 원본과 구조 비교가 True다. 빈 트리와 원소 하나도 같은 규칙으로 처리된다.
예제 코드
def same_tree(a, b):
stack = [(a, b)]
while stack:
left, right = stack.pop()
if left is None or right is None:
if left is not right:
return False
continue
if left.value != right.value:
return False
stack.append((left.left, right.left))
stack.append((left.right, right.right))
return True
def mirror_tree(root):
stack = [] if root is None else [root]
while stack:
node = stack.pop()
node.left, node.right = node.right, node.left
if node.left is not None:
stack.append(node.left)
if node.right is not None:
stack.append(node.right)
return root
root = sample_tree()
original = decode_tree(encode_tree(root))
mirror_tree(root)
print(''.join(preorder(root)))
mirror_tree(root)
print(same_tree(root, original))
print(same_tree(TreeNode('X', TreeNode('X')), TreeNode('X', None, TreeNode('X'))))
실행 결과
ACFBED
True
False지름과 높이 균형을 한 번에 계산하기
트리의 지름은 두 노드 사이 최장 경로의 길이다. 이 문서는 간선 수를 사용하며 빈 트리와 노드 하나의 지름은 0으로 정의한다. 최장 경로가 반드시 루트를 지나지는 않으므로 양쪽 하위 트리의 지름도 비교해야 한다.
현재 노드를 지나는 경로 길이는 왼쪽 높이+오른쪽 높이+2다. 빈 하위 트리 높이 −1을 쓰므로 한쪽만 있는 경우도 같은 식으로 처리된다. 현재 지름은 이 값과 두 하위 지름의 최댓값이다.
height와 diameter, balanced를 묶어 반환하면 각 노드를 한 번 방문한다. 균형은 두 하위 트리가 각각 균형이고 두 높이 차이가 1 이하여야 한다. 현재 노드의 높이 차이만 검사하면 하위의 불균형을 놓친다.
전체 시간 O(n), 호출 스택 O(h+1)이다. 매 노드에서 height_of를 처음부터 다시 호출하면 편향 트리에서 O(n²)이 될 수 있으므로 필요한 정보를 하위 결과로 전달하는 것이 중요하다.
예제 코드
def tree_metrics(root):
def visit(node):
if node is None:
return -1, 0, True
left_height, left_diameter, left_balanced = visit(node.left)
right_height, right_diameter, right_balanced = visit(node.right)
height = 1 + max(left_height, right_height)
through = left_height + right_height + 2
diameter = max(left_diameter, right_diameter, through)
balanced = (left_balanced and right_balanced
and abs(left_height - right_height) <= 1)
return height, diameter, balanced
return visit(root)
print(tree_metrics(sample_tree()))
print(tree_metrics(None))
chain = TreeNode(1, TreeNode(2, TreeNode(3)))
print(tree_metrics(chain))
실행 결과
(2, 4, True)
(-1, 0, True)
(2, 2, False)전위와 중위에서 구조를 복원하기
노드 값이 모두 고유하면 전위의 첫 값은 루트이고, 중위에서 그 값의 왼쪽 부분은 왼쪽 하위 트리, 오른쪽은 오른쪽 하위 트리다. 같은 규칙을 재귀적으로 적용하여 트리를 복원할 수 있다.
매번 중위 목록을 선형 검색하고 슬라이스하면 반복 비용과 복사 공간이 커질 수 있다. 아래 구현은 값→중위 인덱스 사전을 만들고 [left,right) 범위를 전달한다. 전위는 하나의 cursor로 차례로 소비한다.
값 집합과 길이가 맞고 값이 고유해야 하며, 각 루트 위치가 현재 하위 구간 안에 있어야 한다. 같은 값 집합이라도 순회 두 개의 조합이 일관되지 않으면 오류로 처리한다. 사전 조회를 평균 상수로 보는 모델에서 시간 O(n), 인덱스 사전 O(n)과 재귀 O(h+1) 공간을 사용한다.
중복 값이 있으면 어느 중위 위치를 루트로 택할지 모호할 수 있다. 이 구현은 중복 입력을 거부하며, 앞의 빈 위치 태그 직렬화와 서로 다른 계약이다. 여러 복원 문제를 같은 문제로 취급하지 않는다.
예제 코드
def reconstruct(pre, ino):
if len(pre) != len(ino) or len(set(pre)) != len(pre) or set(pre) != set(ino):
raise ValueError('unique matching values required')
positions = {value: index for index, value in enumerate(ino)}
cursor = 0
def build(left, right):
nonlocal cursor
if left == right:
return None
if cursor == len(pre):
raise ValueError('missing root')
value = pre[cursor]
cursor += 1
split = positions[value]
if not left <= split < right:
raise ValueError('inconsistent traversals')
node = TreeNode(value)
node.left = build(left, split)
node.right = build(split + 1, right)
return node
return build(0, len(ino))
root = sample_tree()
restored = reconstruct(preorder(root), inorder(root))
print(same_tree(root, restored))
for pre, ino in [(['X', 'X'], ['X', 'X']), (['A', 'B', 'C'], ['C', 'A', 'B'])]:
try:
reconstruct(pre, ino)
except ValueError:
print('invalid traversals')
실행 결과
True
invalid traversals
invalid traversals수식 트리의 후위 평가
이항 연산 수식은 연산자를 내부 노드, 피연산자를 잎으로 표현할 수 있다. (3+5)×(9−4)는 루트 곱셈 아래에 덧셈과 뺄셈 하위 트리가 있는 구조다. 괄호의 결합 관계가 트리에 들어 있으므로 단순 문자열의 우선순위 처리와 구분된다.
후위 평가에서는 두 하위 수식을 먼저 계산한 다음 현재 연산을 적용한다. 아래 함수는 정수 잎과 +,−,* 세 연산만 허용하고 연산자에는 자식 둘이 모두 있어야 한다. 지원 범위를 제한해 임의 문자열을 코드로 실행하는 eval을 사용하지 않는다.
이 함수는 파서가 아니다. 이미 올바른 트리 구조를 입력으로 받으며 괄호가 포함된 문자열을 토큰화해 트리로 만드는 과정은 별도다. 표현과 계산을 나누면 오류를 어느 단계에서 검증해야 하는지 명확해진다.
노드를 한 번씩 처리하므로 작은 고정 비용 산술 모델에서 O(n)이지만 큰 정수 곱셈 비용은 값의 크기에 따라 달라진다. 숫자 표현과 연산 비용을 생략한 모델이라는 전제를 유지한다.
예제 코드
def evaluate(node):
if node is None:
raise ValueError('missing expression')
if node.left is None and node.right is None:
if type(node.value) is not int:
raise ValueError('integer leaf required')
return node.value
if node.left is None or node.right is None:
raise ValueError('binary operator needs two children')
left, right = evaluate(node.left), evaluate(node.right)
if node.value == '+':
return left + right
if node.value == '-':
return left - right
if node.value == '*':
return left * right
raise ValueError('unsupported operator')
expression = TreeNode('*', TreeNode('+', TreeNode(3), TreeNode(5)),
TreeNode('-', TreeNode(9), TreeNode(4)))
print(evaluate(expression))
print(postorder(expression))
try:
evaluate(TreeNode('+', TreeNode(1), None))
except ValueError:
print('incomplete expression rejected')
실행 결과
40
[3, 5, '+', 9, 4, '-', '*']
incomplete expression rejected일반 이진 트리에서 값 검색의 비용
값의 위치를 찾으려면 일반 이진 트리는 필요한 노드들을 순회해야 한다. 왼쪽이 작고 오른쪽이 크다는 조건이 없으므로 현재 값과 목표를 비교해 한쪽을 버리는 판단을 할 수 없다. 최악 시간은 O(n)이다.
값이 중복될 수 있다면 첫 일치 노드 하나, 모든 일치 노드, 값 존재 여부 중 어떤 결과를 원하는지도 정해야 한다. 같은 값을 가진 두 노드의 조상이나 경로를 찾을 때는 값 대신 노드 정체성 또는 고유 ID가 필요하다.
이진 탐색 트리에서조차 높이가 n−1이면 검색이 선형이 될 수 있다. 로그 시간 검색을 설명하려면 값 범위 불변식과 높이를 제한하는 조건을 함께 확인한다. 이진 힙에서는 루트 극값 외 임의 값 검색을 같은 방식으로 보장하지 않는다.
트리 구조를 사용한다는 사실보다 어떤 질문을 빠르게 답하도록 구성했는지가 중요하다. 수식 트리는 결합 관계, 힙은 우선순위, 탐색 트리는 값 범위를 나타내며 같은 두 자식 필드를 서로 다른 규칙으로 활용한다.
모든 작은 트리 모양을 생성해 검사하기
노드 n개의 이진 트리는 루트 하나와 왼쪽 크기 l, 오른쪽 크기 n−1−l의 두 모양으로 나눌 수 있다. l을 0부터 n−1까지 바꾸고 양쪽 가능한 모양을 조합하면 작은 모든 모양을 생성할 수 있다.
다음 검사는 n=0부터 7까지 626개 모양을 만든다. 각 모양에 전위 순서의 고유 값을 붙인 새 노드들을 만들며, 모양 캐시의 불변 튜플을 실제 가변 노드로 공유하지 않는다. 서로 다른 테스트의 구조가 섞이지 않게 하기 위해서다.
재귀·반복 세 순회, 크기·높이, 레벨 결과의 원소 수, 직렬화 왕복, 전위·중위 복원과 두 번 거울 변환을 대조한다. 모든 값이 동일한 구조도 따로 만들어 값 중복이 직렬화에 영향을 주지 않는지 확인한다.
완전 열거는 이 범위의 편향·완전·비대칭 형태를 모두 다룬다. 크기 7보다 큰 모든 입력의 증명은 아니며 재귀 제한·메모리 부족·동시 수정은 별도다. 입력 계약과 구조 불변식을 설명한 뒤 구현을 확인하는 검사로 사용한다.
예제 코드
from functools import lru_cache
@lru_cache(None)
def shapes(size):
if size == 0:
return (None,)
return tuple((left, right)
for left_size in range(size)
for left in shapes(left_size)
for right in shapes(size - 1 - left_size))
def materialize(shape, counter):
if shape is None:
return None
node = TreeNode(next(counter))
node.left = materialize(shape[0], counter)
node.right = materialize(shape[1], counter)
return node
from itertools import count
checks = 0
for size in range(8):
for shape in shapes(size):
root = materialize(shape, count())
assert validate_tree(root) == size_of(root) == size
assert preorder(root) == recursive_order(root, 'pre')
assert inorder(root) == recursive_order(root, 'in')
assert postorder(root) == recursive_order(root, 'post')
levels = levels_of(root)
assert sum(map(len, levels)) == size
assert len(levels) - 1 == height_of(root)
encoded = encode_tree(root)
assert len(encoded) == 2 * size + 1
assert same_tree(root, decode_tree(encoded))
assert same_tree(root, reconstruct(preorder(root), inorder(root)))
mirror_tree(root); mirror_tree(root)
assert encoded == encode_tree(root)
pending = [] if root is None else [root]
while pending:
node = pending.pop()
node.value = 'same'
pending.extend(child for child in [node.left, node.right] if child is not None)
assert same_tree(root, decode_tree(encode_tree(root)))
checks += 1
print(checks)
실행 결과
626지름을 모든 시작점의 거리와 대조하기
지름 함수의 결과는 트리를 방향 없는 인접 관계로 바꾼 뒤 모든 시작점에서 BFS로 거리를 구하는 기준 방법과 비교할 수 있다. 효율은 낮지만 작은 입력에서 가장 긴 최단 거리를 독립적으로 구한다.
다음 코드는 앞 절의 shapes와 materialize 정의 뒤에 실행한다. n=0부터 6까지 197개 모양을 검사한다. root를 통과하지 않는 최장 경로와 한쪽 사슬, 잎 하나의 경계를 포함한다. 빈 트리는 지름 0이라는 문서 계약을 적용한다.
높이 균형도 각 노드에서 두 하위 높이를 직접 다시 계산하는 느린 기준과 비교한다. 최적 구현과 같은 계산을 단순히 복제하지 않고, 다른 방식으로 결과를 확인하는 것이 목적이다.
검증 코드는 작은 구조에서만 실행하므로 O(n²) 기준 해법을 허용한다. 본문 tree_metrics의 선형 구현과 테스트용 기준 비용을 혼동하지 않는다. 실제 작업에서는 큰 트리의 지름을 모든 시작점 BFS로 계산할 필요가 없다.
예제 코드
from collections import deque
from itertools import count
def reference(root):
if root is None:
return 0, True
adjacency = {}
stack = [root]
balanced = True
while stack:
node = stack.pop()
adjacency.setdefault(node, [])
balanced = balanced and abs(height_of(node.left) - height_of(node.right)) <= 1
for child in [node.left, node.right]:
if child is not None:
adjacency[node].append(child)
adjacency.setdefault(child, []).append(node)
stack.append(child)
longest = 0
for start in adjacency:
distance = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in adjacency[node]:
if neighbor not in distance:
distance[neighbor] = distance[node] + 1
queue.append(neighbor)
longest = max(longest, max(distance.values()))
return longest, balanced
checks = 0
for size in range(7):
for shape in shapes(size):
root = materialize(shape, count())
height, diameter, balanced = tree_metrics(root)
assert height == height_of(root)
assert (diameter, balanced) == reference(root)
checks += 1
print(checks)
실행 결과
197이진 트리를 구현할 때의 판단 기준
먼저 트리가 나타내는 의미와 불변식을 정한다. 단순 계층인지, 값 범위 검색인지, 우선순위인지에 따라 같은 left·right 필드가 수행하는 역할이 다르다. 값의 중복 허용 여부와 노드 식별 방식도 결정한다.
다음으로 최대 높이와 폭, 입력 검증 위치, 변경 중 참조 수명을 확인한다. 재귀가 간단하더라도 편향 입력의 호출 깊이를 고려하고, 반복 방식에서도 출력과 스택·큐 공간을 분리해 계산한다.
저장·전송이 필요하면 빈 자식 위치와 값 표현을 명확히 기록한다. 단순 순회 값만으로 충분한지, 고유 값 전제가 있는지, 공유 구조를 허용하는지에 따라 복원 가능성이 달라진다. 외부 입력의 크기와 깊이 제한도 형식의 일부다.
구현 검증은 정상 모양 하나뿐 아니라 빈 트리·잎 하나·한쪽 사슬·중복 값·공유 자식·순환을 포함한다. 재귀 정의, 반복 상태와 독립 기준 대조를 함께 사용하면 이진 탐색 트리, 힙, 구문 트리와 균형 트리로 확장할 기반을 만들 수 있다.