트리 자료구조 | 이진 트리, BST, 순회 완벽 정리
이 글의 핵심
트리 자료구조: 이진 트리, BST, 순회 트리 기본 개념·트리 순회.
시리즈 안내
#04 | 📋 전체 목차 | 이전: #03 해시 테이블 · 다음: #05 그래프
🎯 이 글을 읽으면 (읽는 시간: 22분)
TL;DR: 계층 구조를 표현하는 트리 자료구조를 완벽하게 마스터합니다. 이진 트리, BST, 트리 순회(전위/중위/후위)를 이해하고, 파일 시스템부터 코딩 테스트까지 실전 활용 능력을 습득합니다. 이 글을 읽으면:
- ✅ 트리, 이진 트리, BST 개념 완벽 이해
- ✅ 전위/중위/후위/레벨 순회 패턴 마스터
- ✅ 트리 문제 해결 능력 (깊이, 경로, 균형) 습득 실무 활용:
- 🔥 파일 시스템, DOM 트리 구조
- 🔥 데이터베이스 인덱스 (B-Tree)
- 🔥 코딩 테스트 (LeetCode Tree 문제) 난이도: 중급 | 실습 문제: 10개 | Python + C++: 모두 포함
들어가며
”계층 구조의 완벽한 표현”
트리는 계층 구조를 표현하는 자료구조입니다. 파일 시스템, DOM, 조직도 등 모두 트리입니다.
코딩 테스트 준비하며 깨달은 것
알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 성능 문제에 부딪히면, 알고리즘 지식이 얼마나 중요한지 깨닫게 됩니다. 예를 들어, 사용자 검색 기능이 느려서 고민하다가 해시 테이블을 적용하니 응답 시간이 10초에서 0.1초로 줄어든 경험이 있습니다. 코딩 테스트는 단순히 취업을 위한 관문이 아니라, 문제 해결 능력을 키우는 훈련장입니다. 처음엔 브루트 포스로 풀다가, 시간 복잡도를 개선하는 과정에서 “아, 이렇게 생각하면 되는구나” 하는 깨달음을 얻을 때의 쾌감은 말로 표현하기 어렵습니다. 이 글에서는 단순히 정답 코드만 제시하는 게 아니라, 문제를 어떻게 접근하고 최적화하는지 사고 과정을 함께 공유하겠습니다.
1. 트리 기본 개념
용어
1 ← 루트(Root)
/ \
2 3 ← 자식(Child)
/ \
4 5 ← 리프(Leaf)
- 노드(Node): 1, 2, 3, 4, 5
- 간선(Edge): 노드를 연결하는 선
- 부모(Parent): 2의 부모는 1
- 자식(Child): 1의 자식은 2, 3
- 형제(Sibling): 2와 3
- 깊이(Depth): 루트부터 거리 (4의 깊이 = 2)
- 높이(Height): 리프까지 최대 거리 (트리 높이 = 2)
- 레벨(Level): 같은 깊이의 노드들Python 구현
아래는 값(val)과 왼쪽·오른쪽 자식 포인터를 갖는 노드를 정의하고, 루트에서 아래로 가지를 뻗어 연결하는 예입니다. 조직도나 가계도처럼 한 부모 아래에 자식이 달리는 구조를 코드로 만든 것입니다.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 트리 생성
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)2. 트리 순회
전위 순회 (Preorder)
부모 → 왼쪽 → 오른쪽 순서로 방문합니다:
def preorder(node):
# 기저 조건: 노드가 없으면 빈 리스트 반환
if not node:
return []
# 전위 순회 순서:
# 1. 부모 노드 먼저 방문: [node.val]
# 2. 왼쪽 서브트리 순회: preorder(node.left)
# 3. 오른쪽 서브트리 순회: preorder(node.right)
return [node.val] + preorder(node.left) + preorder(node.right)
# 트리 구조:
# 1
# / \
# 2 3
# / \
# 4 5
#
# 순회 과정:
# 1. 노드 1 방문 → [1]
# 2. 왼쪽(2) 이동 → [1, 2]
# 3. 왼쪽(4) 이동 → [1, 2, 4]
# 4. 4는 리프 → 백트랙
# 5. 오른쪽(5) 이동 → [1, 2, 4, 5]
# 6. 백트랙 후 오른쪽(3) → [1, 2, 4, 5, 3]
#
# 결과: [1, 2, 4, 5, 3]전위 순회 활용:
- 트리 복사 (부모부터 생성)
- 트리 직렬화 (파일 저장)
- 수식 트리의 전위 표기법 (Prefix notation) 반복문 구현 (스택 사용):
def preorder_iterative(root):
if not root:
return []
result = []
stack = [root] # 스택에 루트 추가
while stack:
# 스택에서 노드 꺼내기 (LIFO)
node = stack.pop()
result.append(node.val) # 방문
# 오른쪽 먼저 push (나중에 pop)
if node.right:
stack.append(node.right)
# 왼쪽 나중에 push (먼저 pop)
if node.left:
stack.append(node.left)
return result중위 순회 (Inorder)
왼쪽 → 부모 → 오른쪽:
def inorder(node):
if not node:
return []
return inorder(node.left) + [node.val] + inorder(node.right)
# 결과: [4, 2, 5, 1, 3]
# BST에서는 오름차순!후위 순회 (Postorder)
왼쪽 → 오른쪽 → 부모:
def postorder(node):
if not node:
return []
return postorder(node.left) + postorder(node.right) + [node.val]
# 결과: [4, 5, 2, 3, 1]레벨 순회 (Level Order)
BFS 사용:
from collections import deque
def level_order(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
node = queue.popleft()
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
# 결과: [1, 2, 3, 4, 5]3. 이진 탐색 트리 (BST)
BST 규칙
왼쪽 < 부모 < 오른쪽:
5
/ \
3 7
/ \ / \
2 4 6 8
중위 순회: [2, 3, 4, 5, 6, 7, 8] (정렬됨!)BST 삽입
BST의 규칙을 유지하며 새 값을 삽입합니다:
def insert_bst(root, val):
# 기저 조건: 빈 자리를 찾으면 새 노드 생성
if not root:
return TreeNode(val)
# BST 규칙: 왼쪽 < 부모 < 오른쪽
if val < root.val:
# val이 현재 노드보다 작으면 왼쪽 서브트리에 삽입
root.left = insert_bst(root.left, val)
else:
# val이 현재 노드보다 크거나 같으면 오른쪽 서브트리에 삽입
# (중복 허용 시 오른쪽에 삽입)
root.right = insert_bst(root.right, val)
# 현재 노드 반환 (재귀 호출 시 부모에게 연결)
return root
# 사용 예시
root = TreeNode(5) # 루트 노드 생성
root = insert_bst(root, 3) # 5보다 작으므로 왼쪽
root = insert_bst(root, 7) # 5보다 크므로 오른쪽
root = insert_bst(root, 2) # 3보다 작으므로 3의 왼쪽
# 결과 트리:
# 5
# / \
# 3 7
# /
# 2
# 삽입 과정 (val=2 삽입):
# 1. root(5): 2 < 5 → 왼쪽으로
# 2. node(3): 2 < 3 → 왼쪽으로
# 3. None: 빈 자리 → TreeNode(2) 생성
# 4. 재귀 반환: 3.left = TreeNode(2)
#
# 시간복잡도:
# - 평균: O(log n) - 균형 트리일 때
# - 최악: O(n) - 한쪽으로 치우친 트리일 때 (예: 1→2→3→4→5)반복문 구현:
def insert_bst_iterative(root, val):
# 빈 트리면 새 노드가 루트
if not root:
return TreeNode(val)
current = root
while True:
if val < current.val:
# 왼쪽으로 이동
if current.left is None:
# 빈 자리 발견 → 삽입
current.left = TreeNode(val)
break
current = current.left
else:
# 오른쪽으로 이동
if current.right is None:
# 빈 자리 발견 → 삽입
current.right = TreeNode(val)
break
current = current.right
return rootBST 검색
BST의 정렬 속성을 활용하여 효율적으로 검색합니다:
def search_bst(root, val):
# 기저 조건 1: 노드가 없으면 찾지 못함
if not root:
return None
# 기저 조건 2: 찾았음!
if root.val == val:
return root
# BST 규칙 활용: 왼쪽 < 부모 < 오른쪽
if val < root.val:
# val이 현재 노드보다 작으면 왼쪽 서브트리에만 있을 수 있음
# 오른쪽은 확인할 필요 없음 (모두 현재 노드보다 큼)
return search_bst(root.left, val)
else:
# val이 현재 노드보다 크면 오른쪽 서브트리에만 있을 수 있음
return search_bst(root.right, val)
# 트리 구조:
# 5
# / \
# 3 7
# / \ / \
# 2 4 6 8
# 검색 과정 (val=6 찾기):
# 1. root(5): 6 > 5 → 오른쪽으로 (왼쪽은 무시)
# 2. node(7): 6 < 7 → 왼쪽으로 (오른쪽은 무시)
# 3. node(6): 6 == 6 → 찾음!
#
# 총 3번 비교 (트리 높이만큼)
#
# 시간복잡도:
# - 평균: O(log n) - 균형 트리일 때 (매번 절반씩 제거)
# - 최악: O(n) - 한쪽으로 치우친 트리일 때
# 예: 1→2→3→4→5 (연결 리스트와 동일)
# 일반 배열 검색과 비교:
# 배열 (정렬 안 됨): O(n) - 모든 요소 확인 필요
# 배열 (정렬됨): O(log n) - 이진 탐색 가능
# BST: O(log n) - 삽입/삭제도 O(log n)으로 유지반복문 구현:
def search_bst_iterative(root, val):
current = root
while current:
if current.val == val:
# 찾았음!
return current
elif val < current.val:
# 왼쪽으로 이동
current = current.left
else:
# 오른쪽으로 이동
current = current.right
# 찾지 못함
return None
# 반복문이 재귀보다 메모리 효율적
# (함수 호출 스택 오버헤드 없음)BST의 장점:
# 정렬된 데이터 유지
# 중위 순회 시 자동으로 오름차순
def get_sorted(root):
return inorder(root) # O(n)
# 최소/최대값 찾기
def find_min(root):
# 가장 왼쪽 노드가 최소값
while root.left:
root = root.left
return root.val
def find_max(root):
# 가장 오른쪽 노드가 최대값
while root.right:
root = root.right
return root.val4. 실전 문제
문제 1: 트리 높이
def max_depth(root):
"""
트리의 최대 깊이
"""
if not root:
return 0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return max(left_depth, right_depth) + 1
# 테스트
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(max_depth(root)) # 3문제 2: 대칭 트리
def is_symmetric(root):
"""
트리가 좌우 대칭인지 확인
"""
def is_mirror(left, right):
if not left and not right:
return True
if not left or not right:
return False
return (left.val == right.val and
is_mirror(left.left, right.right) and
is_mirror(left.right, right.left))
return is_mirror(root.left, root.right) if root else True
# 테스트
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.right.right = TreeNode(3)
print(is_symmetric(root)) # True문제 3: 최소 공통 조상 (LCA)
def lowest_common_ancestor(root, p, q):
"""
두 노드의 최소 공통 조상 (BST)
"""
if not root:
return None
# 둘 다 왼쪽
if p.val < root.val and q.val < root.val:
return lowest_common_ancestor(root.left, p, q)
# 둘 다 오른쪽
if p.val > root.val and q.val > root.val:
return lowest_common_ancestor(root.right, p, q)
# 갈라지는 지점 = LCA
return root실전 팁
트리 문제 접근법
# 1. 재귀 생각
# 대부분 트리 문제는 재귀로 풀림
# 2. Base Case 명확히
# if not root: return ...
# 3. 순회 방법 선택
# 전위: 부모 먼저 처리
# 중위: BST 정렬
# 후위: 자식 먼저 처리
# 레벨: 최단 경로정리
핵심 요약
- 트리: 계층 구조, 루트-자식 관계
- 순회: 전위, 중위, 후위, 레벨
- BST: 왼쪽 < 부모 < 오른쪽, O(log n) 검색
- 재귀: 대부분 재귀로 해결
추천 문제
백준:
- 1991번: 트리 순회
- 11725번: 트리의 부모 찾기 프로그래머스:
- 길 찾기 게임 LeetCode:
- 104. Maximum Depth
- 101. Symmetric Tree
관련 글
심화 부록: 구현·운영 관점
이 부록은 앞선 본문에서 다룬 주제(「트리 자료구조 | 이진 트리, BST, 순회 완벽 정리」)를 구현·런타임·운영 관점에서 다시 압축합니다. 도메인별 세부 구현은 글마다 다르지만, 입력 검증 → 핵심 연산 → 부작용(I/O·네트워크·동시성) → 관측의 흐름으로 장애를 나누면 원인 추적이 빨라집니다.
내부 동작과 핵심 메커니즘
flowchart TD A[입력·요청·이벤트] --> B[파싱·검증·디코딩] B --> C[핵심 연산·상태 전이] C --> D[부작용: I/O·네트워크·동시성] D --> E[결과·관측·저장]
sequenceDiagram participant C as 클라이언트/호출자 participant B as 경계(런타임·게이트웨이·프로세스) participant D as 의존성(API·DB·큐·파일) C->>B: 요청/이벤트 B->>D: 조회·쓰기·RPC D-->>B: 지연·부분 실패·재시도 가능 B-->>C: 응답 또는 오류(코드·상관 ID)
- 불변 조건(Invariant): 버퍼 경계, 프로토콜 상태, 트랜잭션 격리, FD 상한 등 단계별로 문장으로 적어 두면 디버깅 비용이 줄어듭니다.
- 결정성: 순수 층과 시간·네트워크·스케줄에 의존하는 층을 분리해야 테스트와 장애 분석이 쉬워집니다.
- 경계 비용: 직렬화, 인코딩, syscall 횟수, 락 경합, 할당·GC, 캐시 미스를 의심 목록에 둡니다.
- 백프레셔: 생산자가 소비자보다 빠를 때 버퍼·큐·스트림에서 속도를 줄이는 신호를 어디에 둘지 정의합니다.
프로덕션 운영 패턴
| 영역 | 운영 관점 질문 |
|---|---|
| 관측성 | 요청 단위 상관 ID, 에러율·지연 p95/p99, 의존성 타임아웃·재시도가 대시보드에 보이는가 |
| 안전성 | 입력 검증·권한·비밀·감사 로그가 코드 경로마다 일관적인가 |
| 신뢰성 | 재시도는 멱등 연산에만 적용되는가, 서킷 브레이커·백오프·DLQ가 있는가 |
| 성능 | 캐시·배치 크기·커넥션 풀·인덱스·백프레셔가 데이터 규모에 맞는가 |
| 배포 | 롤백 룬북, 카나리/블루그린, 마이그레이션·피처 플래그가 문서화되어 있는가 |
| 용량 | 피크 트래픽·디스크·FD·스레드 풀 상한을 주기적으로 검증하는가 |
스테이징은 데이터 양·네트워크 RTT·동시성을 프로덕션에 가깝게 맞출수록 재현율이 올라갑니다.
확장 예시: 엔드투엔드 미니 시나리오
앞선 본문 주제(「트리 자료구조 | 이진 트리, BST, 순회 완벽 정리」)를 배포·운영 흐름에 맞춰 옮긴 체크리스트입니다. 도메인에 맞게 단계 이름만 바꿔 적용할 수 있습니다.
- 입력 계약 고정: 스키마·버전·최대 페이로드·타임아웃·에러 코드를 경계에 둔다.
- 핵심 경로 계측: 요청 ID, 단계별 지연, 외부 호출 결과 코드를 로그·메트릭·트레이스에서 한 흐름으로 본다.
- 실패 주입: 의존성 타임아웃·5xx·부분 데이터·락 대기를 스테이징에서 재현한다.
- 호환·롤백: 설정/마이그레이션/클라이언트 버전을 되돌릴 수 있는지 확인한다.
- 부하 후 검증: 피크 대비 p95/p99, 에러율, 리소스 상한, 알림 임계값을 점검한다.
handle(request):
ctx = newCorrelationId()
validated = validateSchema(request)
authorize(validated, ctx)
result = domainCore(validated)
persistOrEmit(result, idempotentKey)
recordMetrics(ctx, latency, outcome)
return result문제 해결(Troubleshooting)
| 증상 | 가능 원인 | 조치 |
|---|---|---|
| 간헐적 실패 | 레이스, 타임아웃, 외부 의존성, DNS | 최소 재현 스크립트, 분산 트레이스·로그 상관관계, 재시도·서킷 설정 점검 |
| 성능 저하 | N+1, 동기 I/O, 락 경합, 과도한 직렬화, 캐시 미스 | 프로파일러·APM으로 핫스팟 확인 후 한 가지씩 제거 |
| 메모리 증가 | 캐시 무제한, 구독/리스너 누수, 대용량 버퍼, 커넥션 미반납 | 상한·TTL·힙/FD 스냅샷 비교 |
| 빌드·배포만 실패 | 환경 변수, 권한, 플랫폼 차이, lockfile | CI 로그와 로컬 diff, 런타임·이미지 버전 핀 |
| 설정 불일치 | 프로필·시크릿·기본값, 리전 | 스키마 검증된 설정 단일 소스와 배포 매트릭스 표준화 |
| 데이터 불일치 | 비멱등 재시도, 부분 쓰기, 캐시 무효화 누락 | 멱등 키·아웃박스·트랜잭션 경계 재검토 |
권장 순서: (1) 최소 재현 (2) 최근 변경 범위 축소 (3) 환경·의존성 차이 (4) 관측으로 가설 검증 (5) 수정 후 회귀·부하 테스트.
배포 전에는 git add → git commit → git push 후 npm run deploy 순서를 권장합니다.
자주 묻는 질문 (FAQ)
Q. 이 내용을 실무에서 언제 쓰나요?
A. 트리 자료구조: 이진 트리, BST, 순회 완벽 정리. 트리 기본 개념·트리 순회로 흐름을 잡고 원리·코드·실무 적용을 한글로 정리합니다. 알고리즘·자료구조·트리 중심으로 설명합니다. Start now. 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.
Q. 선행으로 읽으면 좋은 글은?
A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.
Q. 더 깊이 공부하려면?
A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.
같이 보면 좋은 글 (내부 링크)
이 주제와 연결되는 다른 글입니다.
이 글에서 다루는 키워드 (관련 검색어)
알고리즘, 자료구조, 트리, Tree, BST, 이진트리, 코딩테스트 등으로 검색하시면 이 글이 도움이 됩니다.