이 글에서 정리하는 내용
트리의 정의와 기본 용어부터 트리 표현 방법, 이진 트리의 종류, 높이와 노드 수 공식, 이진 탐색 트리의 검색 원리, 최소 신장 트리와 크루스칼·프림 알고리즘까지 시험과 이해에 필요한 흐름으로 한 번에 정리합니다. 특히 트리와 이진 트리의 차이, 공식 적용 기준, 알고리즘 문제 풀이 순서를 함께 익히는 데 초점을 맞춥니다.
트리는 왜 그래프와 다르게 다뤄질까
트리는 그래프의 한 종류이지만, 모든 그래프가 트리는 아닙니다. 트리는 사이클이 없고 모든 노드가 서로 연결되어 있다는 점이 핵심입니다. 즉, 연결은 유지하면서도 빙글빙글 도는 경로가 없어야 합니다. 더 정확히 말하면 트리에서는 임의의 두 노드 사이를 잇는 단순 경로가 정확히 하나입니다. 그래서 두 노드 사이의 길을 생각할 때도 구조가 명확하게 정리되며, 이 특징 때문에 계층 구조를 표현하기에 적합합니다.
트리의 정의와 포레스트
트리
- 연결되어 있다
- 사이클이 없다
포레스트
- 트리가 여러 개 모여 있는 상태
- 서로 떨어져 있을 수 있다시험에서는 연결 그래프인지, 사이클이 있는지 두 가지를 함께 확인하면 빠릅니다. 연결은 되어 있는데 사이클이 있으면 일반 그래프이고, 사이클은 없지만 여러 덩어리로 나뉘어 있으면 포레스트입니다. 둘 다 만족해야 트리입니다.
또한 노드가 1개뿐인 경우는 사소한 트리로 볼 수 있고, 아무 노드도 없는 경우는 공백 트리로 다룹니다. 이런 예외도 용어 문제로 자주 나오므로 함께 익혀두는 편이 좋습니다. 트리는 노드가 n개이면 간선이 항상 n-1개라는 성질도 자주 함께 묶여 나옵니다.
트리 기본 용어 한 번에 정리
A ← 루트
/ \
B C
/ \ \
D E F
A: 루트
B, C: A의 자식
A: B, C의 부모
D, E: 형제
D, E, F: 리프루트는 시작점이 되는 노드이고, 자식은 아래로 직접 연결된 노드입니다. 부모는 그 반대 방향으로 바로 위에 있는 노드입니다. 자식이 없는 노드는 리프 노드라고 부릅니다. 같은 부모를 가진 노드는 형제입니다.
높이와 깊이도 자주 헷갈립니다. 깊이는 보통 루트에서 해당 노드까지 내려온 간선 수이고, 트리의 높이는 루트에서 가장 깊은 리프까지의 간선 수로 봅니다. 이 글에서도 그 기준으로 계속 설명하겠습니다. 다만 교재에 따라 레벨 수를 높이라고 부르는 경우도 있으므로, 공식 문제에서는 기준을 먼저 확인하는 습관이 필요합니다.
트리를 어떻게 표현할까
트리를 그림으로만 이해하면 개념 문제는 풀 수 있지만, 실제 저장과 구현을 생각하면 표현 방법을 알아야 합니다. 같은 트리라도 어떤 자료구조로 저장하느냐에 따라 접근 방식이 달라집니다. 공부할 때는 배열 표현, 연결 표현, 왼쪽 자식-오른쪽 형제 표현을 구분해 두면 좋습니다. 특히 완전한 형태에 가까운 이진 트리는 배열 표현과 잘 어울립니다. 일반 트리를 이진 트리처럼 바꾸어 생각하는 표현도 함께 익혀두면 흐름이 잘 잡힙니다.
배열 표현과 연결 표현
완전 이진 트리 예시
인덱스: 1 2 3 4 5 6 7
값 : A B C D E F G
부모 i
왼쪽 자식 2i
오른쪽 자식 2i + 1배열 표현은 특히 완전 이진 트리에서 강력합니다. 인덱스 규칙만 알면 부모와 자식을 바로 찾을 수 있기 때문입니다. 힙을 배울 때 이 방식이 자주 등장합니다. 다만 빈칸이 많아지는 트리에서는 메모리 낭비가 커질 수 있습니다.
연결 표현은 각 노드가 자신의 자식이나 형제를 가리키는 방식입니다. 일반 트리나 모양이 불규칙한 트리를 다룰 때 더 자연스럽습니다. 실제 자료구조 문제에서는 포인터나 참조 개념과 함께 연결해서 이해하면 좋습니다. 반대로 규칙적인 이진 트리는 배열로 표현했을 때 부모와 자식 계산이 빠르다는 장점이 있습니다.
왼쪽 자식-오른쪽 형제 표현
일반 트리
A의 자식: B, C, D
변환 후
A의 왼쪽 자식: B
B의 오른쪽 형제: C
C의 오른쪽 형제: D일반 트리는 자식 수가 제각각이라 이진 구조로 바로 다루기 어렵습니다. 이때 첫 번째 자식은 왼쪽 자식으로, 다음 형제는 오른쪽 형제로 연결하면 일반 트리를 이진 트리처럼 표현할 수 있습니다. 이 방식은 트리를 이진 구조로 바꾸어 생각하는 연습에 도움이 됩니다.
이진 트리와 높이 공식 이해하기
이진 트리는 각 노드가 최대 두 개의 자식을 가지는 트리입니다. 여기서 중요한 점은 단순히 자식이 두 개 이하라는 것만이 아니라, 왼쪽 자식과 오른쪽 자식이 구분된다는 점입니다. 그래서 자식이 하나만 있어도 왼쪽인지 오른쪽인지가 의미를 가집니다. 이진 트리는 모양이 비슷해 보여도 분류 기준이 다르기 때문에 정의를 정확히 붙잡는 편이 중요합니다. 시험에서는 같은 그림을 두고도 어떤 이진 트리인지 묻는 경우가 많습니다.
완전 이진 트리와 포화 이진 트리 비교
완전 이진 트리
- 마지막 레벨만 덜 찰 수 있다
- 마지막 레벨은 왼쪽부터 채운다
포화 이진 트리
- 모든 내부 노드가 자식 2개를 가진다
- 모든 리프가 같은 레벨에 있다완전 이진 트리는 마지막 레벨을 제외하면 모두 꽉 차 있고, 마지막 레벨도 왼쪽부터 순서대로 채워집니다. 반면 포화 이진 트리는 모든 내부 노드가 정확히 두 자식을 가지며, 모든 리프가 같은 높이에 있습니다. 시험에서는 그림을 보고 마지막 레벨이 왼쪽부터 채워졌는지, 모든 리프 레벨이 같은지를 먼저 보면 구분이 빨라집니다.
용어는 교재마다 조금씩 다를 수 있습니다. 어떤 자료는 모든 내부 노드가 자식 2개인 형태를 정이진 트리 또는 full binary tree로 부르고, 모든 리프 깊이가 같은 형태를 perfect binary tree로 따로 구분합니다. 이 글에서는 포화 이진 트리를 리프의 깊이까지 모두 같은 형태로 통일해서 설명하겠습니다.
높이와 노드 수 공식 정리
이 글의 기준
- 높이 0: 루트만 있는 상태
높이 h인 이진 트리의 최대 노드 수
= 2의 h+1제곱 - 1
노드 수가 n개일 때 최소 높이
= log2(n + 1)을 올림한 값 - 1공식은 높이 기준을 어떻게 잡느냐에 따라 모양이 달라 보일 수 있습니다. 이 글에서는 루트만 있으면 높이 0으로 봅니다. 그러면 높이 h인 이진 트리의 최대 노드 수는 포화 이진 트리일 때 나오며, 값은 2의 h+1제곱에서 1을 뺀 형태가 됩니다.
반대로 노드 수가 주어졌을 때 최소 높이는 가능한 한 꽉 채운 상태, 즉 가장 균형 잡힌 이진 트리를 생각하면 됩니다. 예를 들어 노드가 7개면 높이 2, 노드가 8개면 높이 3이 됩니다. 문제를 풀 때는 먼저 최대 노드 수 공식을 세워 범위를 비교하는 방식이 안전합니다. 이진 트리 문제는 높이 기준만 먼저 고정하면 계산 실수가 크게 줄어듭니다. 결국 공식 계산에서는 어떤 이진 트리를 가정하고 있는지도 함께 확인해야 합니다.
이진 탐색 트리와 최소 신장 트리
이 단원 후반은 트리의 활용을 보는 부분입니다. 하나는 검색을 빠르게 하기 위한 이진 탐색 트리이고, 다른 하나는 가중치가 있는 연결 무방향 그래프에서 비용이 가장 작은 연결 구조를 구하는 최소 신장 트리입니다. 이름은 모두 트리이지만, 전자는 자료구조 관점이고 후자는 그래프 알고리즘 관점이라는 차이가 있습니다.
이진 탐색 트리의 검색 원리
30
/ \
15 40
/ \ \
10 20 50
25 찾기
30보다 작다 → 왼쪽 이동
15보다 크다 → 오른쪽 이동
20보다 크다 → 오른쪽 이동
없으면 검색 실패이진 탐색 트리는 왼쪽 서브트리의 키는 루트보다 작고, 오른쪽 서브트리의 키는 루트보다 큽니다. 그래서 찾는 값과 현재 노드를 비교하면서 한쪽 서브트리만 선택해 내려갈 수 있습니다. 매번 전체를 다 볼 필요가 없다는 점이 핵심입니다.
또한 이진 탐색 트리는 중위 순회를 하면 키가 정렬된 순서로 출력된다는 성질도 함께 기억해 두면 좋습니다. 다만 항상 빠른 것은 아닙니다. 삽입 순서가 한쪽으로 치우치면 트리가 길쭉해져서 연결 리스트처럼 비효율적이 될 수 있습니다. 따라서 효율적인 검색이 가능한 트리인지 물으면, 보통 균형이 심하게 깨지지 않았는지도 함께 살펴봐야 합니다.
최소 신장 트리와 크루스칼·프림
가중 그래프 예시
A-B: 1
A-C: 4
B-C: 2
B-D: 5
C-D: 3
크루스칼
가중치가 작은 간선부터 본다
사이클이 생기면 제외한다
프림
시작 정점 하나를 잡는다
현재 트리에서 가장 싸게 확장되는 간선을 고른다최소 신장 트리는 모든 정점을 포함하면서 총 가중치 합이 가장 작은 트리입니다. 신장 트리이므로 모든 정점을 연결해야 하고, 트리이므로 사이클이 있으면 안 됩니다. 결국 연결은 유지하되 비용을 가장 작게 만드는 구조를 찾는 문제라고 이해하면 됩니다.
위 예시에서 크루스칼 알고리즘은 A-B 1, B-C 2, C-D 3 순서로 선택하면 끝납니다. 그다음 간선 A-C 4는 이미 A-B-C가 연결된 뒤라 사이클을 만들 수 있어 제외됩니다. 프림 알고리즘도 예를 들어 A에서 시작하면 A-B 1을 고르고, 이어서 현재 트리에서 바깥으로 나가는 가장 싼 간선인 B-C 2, C-D 3을 차례로 붙입니다. 둘 다 결과는 같을 수 있지만, 생각하는 출발점이 다릅니다.
크루스칼 알고리즘은 간선을 중심으로 작은 것부터 고릅니다. 대신 사이클이 생기는 간선은 버립니다. 프림 알고리즘은 정점 하나에서 시작해서 현재 만들어진 트리 바깥으로 가장 싸게 확장되는 간선을 붙여 갑니다. 둘 다 탐욕적 방법이지만, 출발 관점이 다르다는 점이 중요합니다.
| 알고리즘 | 핵심 관점 |
|---|---|
| 크루스칼 | 간선을 가중치 순으로 보며 사이클을 피한다 |
| 프림 | 현재 트리에서 가장 저렴한 확장을 반복한다 |
정리
트리는 사이클이 없는 연결 그래프라는 정의에서 출발합니다. 이 기준이 잡히면 포레스트와 자연스럽게 구분할 수 있고, 루트·부모·자식·리프·높이 같은 용어도 정리됩니다. 이후 트리를 배열이나 연결 구조로 어떻게 표현하는지 이해하면 자료구조 관점이 보이기 시작합니다.
이진 트리에서는 각 노드가 최대 두 자식을 가진다는 점과 왼쪽·오른쪽이 구분된다는 점이 핵심입니다. 완전 이진 트리와 포화 이진 트리를 그림으로 구분할 수 있어야 하고, 높이와 노드 수 공식을 기준에 맞춰 적용할 수 있어야 합니다. 마지막으로 BST는 검색 효율과 연결되고, MST는 가중 그래프에서 최소 비용 연결과 연결된다는 점까지 이어서 기억하면 이 장 전체 흐름이 훨씬 선명해집니다.
많이 받는 질문
Q. 트리는 왜 간선 수가 항상 노드 수보다 1개 적나요?
트리는 연결되어 있으면서도 사이클이 없어야 합니다. 노드를 모두 연결하려면 최소한의 간선이 필요하고, 그 최소 연결 구조가 바로 노드 수보다 1개 적은 간선 수입니다. 간선을 하나 더 넣으면 사이클이 생기기 쉽고, 하나 빼면 연결이 끊어집니다.
Q. 완전 이진 트리와 포화 이진 트리를 가장 빨리 구분하는 방법은 무엇인가요?
완전 이진 트리는 마지막 레벨이 왼쪽부터 차곡차곡 채워졌는지를 보면 되고, 포화 이진 트리는 모든 내부 노드가 자식 2개를 가지며 모든 리프가 같은 레벨인지 확인하면 됩니다. 문제 그림을 볼 때는 마지막 줄의 모양부터 확인하는 것이 빠릅니다.
Q. 크루스칼과 프림 중 무엇이 더 쉬운가요?
손으로 풀 때는 많은 경우 크루스칼이 직관적입니다. 작은 간선부터 보며 사이클만 피하면 되기 때문입니다. 다만 시작점에서 점점 확장되는 흐름을 좋아하면 프림이 더 자연스럽게 느껴질 수 있습니다. 시험에서는 둘 다 같은 그래프에 적용해 보며 차이를 익히는 것이 가장 좋습니다.