함께 배우는 수업 · 컴퓨터/정보

트리와 이진 탐색 트리 (BST)

계층적 비선형 자료구조인 트리의 구조와 이진 트리 3대 순회(전위·중위·후위), 이진 탐색 트리(BST)의 원리, 힙(Heap)과 균형 트리(B-Tree)를 학습합니다.

이 수업에서 해 볼 일

이진 탐색 트리의 순서 조건으로 탐색 경로를 정한다

먼저 알면 좋은 것: 연결 리스트의 노드(Node)와 포인터 구조 · 재귀 함수(Recursion)와 스택 동작 원리 · 로그 함수($\log_2 N$)와 이진 분할의 개념

오늘의 목표

가입 없이 시작할 수 있어요. 설명을 읽고, 함께 연습한 뒤, 처음 보는 문제에서 직접 확인합니다.

판단 과정과 비교 사례

BST에서는 각 노드의 왼쪽에 작은 키, 오른쪽에 큰 키를 둔다. 탐색할 때 현재 노드와 값을 비교하고 선택한 서브트리 안에서 같은 규칙을 반복한다.루트 30에 12와 40을 넣고 18을 넣으면 30에서 왼쪽, 12에서 오른쪽으로 이동한다. '루트보다 작다'는 조건만으로 마지막 부모까지 정해지지는 않는다.전위는 루트부터, 중위는 왼쪽→루트→오른쪽, 후위는 루트를 마지막에 방문한다. 힙의 부모·자식 크기 규칙과 BST의 전체 서브트리 정렬 규칙도 구분하자.

1. 트리의 기본 성질과 이진 트리 3대 순회(Traversal)

- 트리(Tree)의 핵심 특징: 사이클(Cycle)이 없는 연결 그래프로,

N

개의 노드를 가진 트리의 간선(Edge) 수는 항상 $N - 1$ 개입니다. 최상단 노드를 루트(Root), 자식이 없는 말단 노드를 리프(Leaf / 단말 노드)라고 합니다. - 이진 트리 (Binary Tree): 모든 노드의 자식이 최대 2개(왼쪽 자식, 오른쪽 자식) 이하인 트리입니다. 높이가

h

인 포화 이진 트리의 전체 노드 수는

2^h - 1

개(루트 레벨을 1로 둘 때)입니다. - 이진 트리 깊이 우선 순회 3가지 (현재 노드 $V$ 를 언제 방문하는지로 구분): 1. 전위 순회 (Pre-order: $V \rightarrow L \rightarrow R$ ): 루트(자신)를 먼저 방문한 뒤 왼쪽 서브트리 ➔ 오른쪽 서브트리 순으로 방문 (폴더 구조 복사, 전위 표기식). 2. 중위 순회 (In-order: $L \rightarrow V \rightarrow R$ ): 왼쪽 서브트리 ➔ 루트(자신) ➔ 오른쪽 서브트리 순으로 방문 (이진 탐색 트리에서 오름차순 정렬 결과 출력!). 3. 후위 순회 (Post-order: $L \rightarrow R \rightarrow V$ ): 왼쪽 서브트리 ➔ 오른쪽 서브트리 ➔ 루트(자신)를 마지막에 방문 (하위 폴더 용량 합산, 안전한 트리 메모리 해제).순회 이름의 '전(Pre)·중(In)·후(Post)'는 왼쪽(L)과 오른쪽(R)의 순서가 아니라(L은 항상 R보다 먼저!), '부모(Root) 노드를 언제 방문하느냐(맨 앞 / 가운데 / 맨 뒤)'를 뜻합니다.

2. 이진 탐색 트리 (Binary Search Tree, BST)와 편향 트리 문제

- BST의 불변 규칙: 트리 내의 모든 노드

X

에 대하여 다음 대소 관계가 엄격히 성립합니다:

\text{왼쪽 서브트리의 모든 값} < X\text{의 값} < \text{오른쪽 서브트리의 모든 값}

- 탐색·삽입·삭제 원리와 시간 복잡도: - 찾고자 하는 값을 현재 노드와 비교하여 작으면 왼쪽으로, 크면 오른쪽으로 내려가므로 매 단계마다 탐색 대상이 절반으로 줄어듭니다. - 평균(균형 잡힌 경우): 트리의 높이가

O(\log N)

이므로 탐색·삽입·삭제 모두 $O(\log N)$ 에 수행됩니다. - 최악(편향 트리, Skewed Tree): 만약 정렬된 데이터 [10, 20, 30, 40, 50]을 순서대로 BST에 삽입하면 오른쪽으로만 길게 늘어선 일자형 사슬(사실상 연결 리스트)이 되어 높이가

N

이 되고, 시간 복잡도가 $O(N)$ 으로 급격히 악화됩니다.

예제로 살펴보기

빈 이진 탐색 트리(BST)에 50, 30, 70, 20, 40, 60, 80을 순서대로 삽입했을 때 만들어지는 트리에 대해 전위 순회(Pre-order), 중위 순회(In-order), 후위 순회(Post-order) 결과를 각각 구하시오.

1) 트리 구조 형성: - 루트는 50입니다. - 50의 왼쪽 자식은 30(그 자식으로 왼쪽 20, 오른쪽 40)이 배치됩니다. - 50의 오른쪽 자식은 70(그 자식으로 왼쪽 60, 오른쪽 80)이 배치됩니다. 2) 전위 순회 (Root → L → R): 50 ➔ 30 ➔ 20 ➔ 40 ➔ 70 ➔ 60 ➔ 80 3) 중위 순회 (L → Root → R): 20 ➔ 30 ➔ 40 ➔ 50 ➔ 60 ➔ 70 ➔ 80 (정확히 오름차순으로 정렬됨!) 4) 후위 순회 (L → R → Root): 20 ➔ 40 ➔ 30 ➔ 60 ➔ 80 ➔ 70 ➔ 50 (루트 50이 가장 마지막에 출력됨)

확인: 이진 트리의 전위(VLR)·중위(LVR)·후위(LRV) 순회는 부모 노드(V)의 방문 시점에 따라 구분된다.

3. 자가 균형 트리(AVL, Red-Black), 힙(Heap), 데이터베이스 B-Tree

- 자가 균형 이진 탐색 트리 (Self-Balancing BST): - 편향 트리로 퇴화하는 것을 막기 위해 삽입·삭제 시 노드 회전(Rotation)을 통해 스스로 높이를

O(\log N)

으로 유지하는 트리입니다 (예: AVL 트리, C++ std::map과 Java TreeMap, 리눅스 스케줄러에 쓰이는 Red-Black 트리). - 힙 (Heap) vs 이진 탐색 트리 (BST) 구분: - 힙(Heap)은 완전 이진 트리로서 부모 노드가 자식 노드보다 항상 크거나(최대 힙) 작기만(최소 힙) 하면 되며, 왼쪽 자식과 오른쪽 자식 사이의 대소 관계는 없습니다. 최댓값/최솟값을

O(1)

에 확인하고

O(\log N)

에 추출하는 우선순위 큐 구현에 특화되어 있습니다. - 데이터베이스 인덱스의 심장, B-Tree / B+Tree: - 디스크(SSD/HDD)에서 데이터를 읽을 때는 트리 높이를 극도로 낮춰야 디스크 I/O 횟수가 줄어듭니다. 따라서 DB 인덱스는 자식 노드를 2개가 아니라 수백 개씩 거느리는 다진 균형 탐색 트리인 B+Tree를 사용하여 수억 건의 데이터도 단 3~4번의 탐색으로 찾아냅니다.흔히 하는 오해: '힙(Heap)과 이진 탐색 트리(BST)는 같은 것 아닌가?' -> 전혀 다릅니다! BST는 전체 데이터의 정렬 및 임의 값 검색(O(log N))을 위한 구조이고, 힙은 오직 가장 큰 값(Max)이나 가장 작은 값(Min)을 빠르게 꺼내기 위해 부모-자식 간 대소만 유지하는 완전 이진 트리입니다.

참고 근거와 확인 범위

Harvard CS50 · Lecture 5: Data structures ↗
이진 탐색 트리의 삽입·탐색과 성능

설명·예제·문제 구성 및 오류 수정 책임: 프리런. 위 자료는 표시한 주제를 확인하거나 더 읽기 위한 근거이며, 외부 기관의 공식 수업이나 감수본을 뜻하지 않습니다.

참고 자료 연결 점검: 2026-11-02. 제작 방식·검수 범위와 수정 기록에서 확인 범위를 볼 수 있습니다. 오류는 상단의 의견 보내기 또는 contact@freelearn.io로 알려 주세요.

이 단원의 개념서 읽기 →