통합 요약노트
Ch.6 트리 기초
이진 트리, 순회(전위/중위/후위/레벨), BST, 트리 높이와 균형
이 챕터의 내용
트리란? — 폴더, 가계도, DOM
계층적 관계를 표현해야 할 때 트리가 유일한 해답입니다. 면접에서도 가장 자주 출제됩니다.
지금 이 파일을 열기까지 몇 개의 폴더를 거쳤나요?
C:\Users\폴더 구조 — 이것이 트리입니다. 루트 드라이브 아래 폴더(노드)가 가지를 뻗고, 파일(리프)이 끝에 달려 있죠
트리의 핵심 규칙: 사이클이 없다. 어떤 노드에서 출발해도 자기 자신으로 돌아오는 경로가 없습니다
이진트리 순회 — pre/in/post/level order
Pre/In/Post/Level — 이 4가지만 알면 모든 트리 문제의 기초를 세울 수 있습니다.
배열은 인덱스 0부터 끝까지. 트리는? 선택지가 4가지입니다
전위·중위·후위는 DFS(깊이 우선), 레벨 순회는 BFS(너비 우선)입니다
전위 = 루트를 먼저 방문. Pre(먼저) + order(순서)
재귀로 트리 생각하기 — max depth, invert tree
'왼쪽 서브트리와 오른쪽 서브트리가 이미 풀렸다면?' — 이 질문 하나로 대부분 해결됩니다.
트리의 마법: 서브트리도 트리다
재귀적 사고 3단계: 1. Base case: None이면 무엇을 반환? 2. 가정: 왼쪽/오른쪽 서브트리 답을 안다면? 3. 결합: 두 답을 어떻게 합치는가?
이 3단계를 외우세요. 면접에서 트리 문제를 만나면 자동으로 이 순서를 따릅니다
BST — 정렬된 트리, 탐색/삽입
정렬 + 빠른 탐색 + 빠른 삽입 — BST가 왜 자료구조의 핵심인지 알아봅시다.
이진 탐색 트리의 규칙은 딱 하나입니다
왼쪽 서브트리의 모든 값 < 루트 < 오른쪽 서브트리의 모든 값 이 규칙이 모든 서브트리에서 재귀적으로 성립합니다
찾고자 하는 값이 현재 노드보다 작으면 왼쪽, 크면 오른쪽으로 이동
트리 높이와 균형 — AVL 개념
회전(Rotation)이라는 간단한 연산 하나로 항상 O(log n)을 보장합니다.
같은 7개의 데이터. 트리 모양에 따라 성능이 7배 차이납니다
n = 100만이면? 균형: 20번 비교 vs 편향: 100만 번 비교. 5만 배 차이입니다
AVL 트리의 규칙은 단순합니다. 모든 노드에서 | 왼쪽 높이 - 오른쪽 높이 | ≤ 1
면접실전 — 트리 Top 5 문제
문제 유형 → 패턴 → 코드 파이프라인을 만들어봅시다.
LeetCode #104 이진 트리의 최대 깊이를 구하라
면접관이 iterative로도 풀 수 있나요? 라고 물으면 BFS(레벨 순회)로 층 수를 세면 됩니다
LeetCode #226 이진 트리를 좌우 반전하라
챕터6 종합퀴즈 — 트리 마스터
실전 면접 수준의 문제들로 자신감을 키워봅시다.
이진 트리에서 높이가 h일 때 최대 노드 수는?
트리와 그래프의 가장 큰 차이점은?
다음 트리의 중위 순회(Inorder) 결과는? 1 / \ 2 3 / \ 4 5
- 트리 = 비순환 계층 구조, 이진 트리가 면접 핵심
- 4가지 순회: Pre/In/Post(DFS) + Level(BFS)
- 재귀적 사고 3단계: Base → 가정 → 결합
- BST: 왼쪽 < 루트 < 오른쪽, 균형이면 O(log n)
- 면접 Top 5: maxDepth, invert, validate, LCA, levelOrder
핵심 용어 모음
트리(Tree)
노드와 간선으로 이루어진 계층적 비순환 자료구조
루트(Root)
최상위 노드 — 부모가 없다
리프(Leaf)
자식이 없는 말단 노드
높이(Height)
루트에서 가장 깊은 리프까지의 간선 수
전위(Preorder)
루트 → 왼쪽 → 오른쪽
중위(Inorder)
왼쪽 → 루트 → 오른쪽
후위(Postorder)
왼쪽 → 오른쪽 → 루트
레벨(Level order)
위에서 아래로, 같은 층 먼저
균형 인수
height(left) - height(right), -1/0/1만 허용
회전
균형이 깨지면 회전으로 복구
성능 보장
탐색/삽입/삭제 모두 O(log n)
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 코스 시작하기