트리(tree)는 맨 위 노드 하나에서 아래로 갈라져 내려가며 자료를 계층으로 잇는 비선형 구조입니다. 회사 조직도나 폴더처럼 '무엇 아래에 무엇이 있나'가 중요한 자료는 한 줄로 세우면 그 관계가 사라집니다. 트리 문제는 대부분 노드 수·차수·단말 노드 수를 세는 계산이라, 이름마다 무엇을 세는지 정확히 알아야 합니다. 아래 그림은 트리 위에 이름표와 세는 값이 하나씩 붙고, 이진 트리가 층마다 채워지는 모습을 보입니다.
1트리의 이름 — 루트·부모·자식·단말
트리의 칸 하나를 노드(node), 노드를 잇는 선을 간선(edge)이라 합니다. 자료에 따라 간선을 가지(branch)라고도 부릅니다. 노드가 n개면 간선은 늘 n − 1개입니다. 루트가 아닌 노드마다 부모로 올라가는 간선이 하나씩 있기 때문입니다.
- 루트 노드(root node): 맨 위 노드. 부모가 없습니다. 자료에 따라 근 노드라고도 부릅니다.
- 부모·자식·형제: 바로 위 노드가 부모, 바로 아래 노드가 자식, 부모가 같은 노드끼리가 형제입니다.
- 단말 노드(terminal node): 자식이 없는 노드입니다. 자료에 따라 잎 노드(leaf node)라고도 부릅니다. 자식이 있는 노드는 비단말 노드입니다.
단말 노드는 맨 아래층에만 있지 않습니다. 그림의 C처럼 2층에 있어도 자식이 없으면 단말입니다.
2세는 값 — 차수와 높이
| 세는 값 | 무엇을 세나 | 그림의 트리 |
|---|---|---|
| 노드의 차수(degree) | 그 노드의 자식 수 | A 3 · B 2 · D 1 · E 2 |
| 트리의 차수 | 노드 차수 가운데 가장 큰 값 | 3 |
| 단말 노드 수 | 차수가 0인 노드 | 5(C·F·G·H·I) |
| 레벨(level) | 루트를 1로, 한 층 내려갈 때마다 1씩 더함 | H·I가 4 |
| 높이(height) | 가장 큰 레벨 | 4 |
차수는 자료에 따라 디그리, 높이는 깊이(depth)라고도 부릅니다. 레벨을 0부터 세는 자료도 있으니, 계산 문제에서는 루트의 레벨을 먼저 확인합니다.
3이진 트리 — 포화와 완전
이진 트리(binary tree)는 모든 노드의 자식이 둘 이하인 트리이고, 두 자식을 왼쪽 자식과 오른쪽 자식으로 가릅니다.
| 가르는 기준 | 포화 이진 트리(full binary tree) | 완전 이진 트리(complete binary tree) |
|---|---|---|
| 채운 모양 | 모든 층이 꽉 찼다 | 위층부터, 같은 층은 왼쪽부터 빈틈없이 채웠다 |
| 마지막 층 | 꽉 찼다 | 덜 차도 된다 |
| 높이 3일 때 노드 수 | 7개뿐 | 4~7개 |
포화 이진 트리는 완전 이진 트리이기도 하지만, 거꾸로는 아닙니다. 마지막 층에 빈자리를 두고 그 오른쪽에 노드가 있으면 완전 이진 트리가 아닙니다.
4이진 트리의 노드 수 셈
아래 식의 ^는 거듭제곱입니다. 2^3은 2를 세 번 곱한 8로, 그림의 2³과 같습니다.
- 레벨 i에는 노드가 많아야
2^(i-1)개입니다. 한 층 내려갈 때마다 두 배가 됩니다. - 높이 k인 이진 트리의 노드는 많아야
2^k - 1개입니다. 이것이 포화 이진 트리의 노드 수입니다. - 단말 노드 수는 차수가 2인 노드 수보다 하나 많습니다.
셋째 셈은 간선 수로 이끌어집니다. 차수가 0·1·2인 노드 수를 n0·n1·n2라 하면 간선은 n0 + n1 + n2 − 1개입니다. 간선은 자식마다 하나이니 n1 + 2 × n2개이기도 합니다. 두 식을 같게 놓으면 n0 = n2 + 1입니다.
예제
높이 4인 포화 이진 트리
| 단계 | 셈 | 값 |
|---|---|---|
| 레벨 1~4의 노드 | 1 + 2 + 4 + 8 | 15 |
| 식으로 | 2^4 - 1 | 15 |
| 단말 노드 | 레벨 4의 노드 | 8 |
| 차수 2인 노드 | 레벨 1~3의 노드 | 7 |
| 맞춰 보기 | 단말 8 = 차수 2인 노드 7 + 1 | 맞음 |
노드 10개인 완전 이진 트리의 높이
| 단계 | 셈 | 값 |
|---|---|---|
| 높이 3까지 꽉 채운 수 | 2^3 - 1 | 7 |
| 높이 4까지 꽉 채운 수 | 2^4 - 1 | 15 |
| 노드 10개가 드는 자리 | 7보다 많고 15 이하 | 높이 4 |
시험 포인트
- 필기: 트리의 차수는 노드 차수 가운데 가장 큰 값이고, 단말 노드는 차수가 0인 노드입니다. 높이는 가장 큰 레벨이며, 루트를 레벨 1로 셀 때 높이 k인 이진 트리의 노드는 많아야
2^k - 1개, 레벨 i의 노드는 많아야2^(i-1)개입니다. 이진 트리의 단말 노드 수는 차수 2인 노드 수 + 1입니다. 단말 노드를 맨 아래층에서만 세거나, 트리의 차수를 루트의 차수로 읽는 것이 흔한 실수입니다. - 실기: 계산한 값을 숫자로 씁니다. 이름은 차수(Degree)·단말 노드(Terminal Node)·포화 이진 트리(Full Binary Tree)·완전 이진 트리(Complete Binary Tree)로 씁니다.
확인 문제
1. 다음 표는 한 트리의 노드마다 자식을 적은 것입니다. 이 트리의 차수와 단말 노드 수를 고르세요.
| 노드 | 자식 |
|---|---|
| R | S, T, U |
| S | V |
| T | W, X, Y, Z |
- ① 차수 3 · 단말 6
- ② 차수 4 · 단말 6
- ③ 차수 4 · 단말 5
- ④ 차수 8 · 단말 6
정답
②입니다. 자식이 가장 많은 T의 차수 4가 트리의 차수입니다. 자식이 없는 U·V·W·X·Y·Z 여섯이 단말 노드입니다.
- ① 트리의 차수를 루트 R의 차수 3으로 읽었습니다.
- ③ 맨 아래층의 V·W·X·Y·Z만 셌습니다. U는 2층이지만 자식이 없어 단말입니다.
- ④ 간선 수 8을 차수로 읽었습니다.
2. 다음 (가)~(라)에 맞는 이름을 한글 이름과 영문으로 함께 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.
- (가) 한 노드에서 아래로 곧바로 뻗은 가지가 몇 개인지 센 값입니다.
- (나) 아래로 뻗은 가지가 하나도 없는 노드입니다.
- (다) 높이가 4이고 노드가 15개라, 노드를 더 넣을 자리가 없는 이진 트리입니다.
- (라) 노드 10개를 위층부터, 같은 층에서는 왼쪽부터 빈자리 없이 채운 이진 트리입니다.
정답
받는 답: (가) 차수(Degree) 또는 디그리 · (나) 단말 노드(Terminal Node) 또는 잎 노드(Leaf Node) · (다) 포화 이진 트리(Full Binary Tree) · (라) 완전 이진 트리(Complete Binary Tree)
(가)의 실마리는 '곧바로 뻗은 가지 수', (나)는 '가지가 없다', (다)는 '높이 4에 2^4 - 1개로 꽉 참', (라)는 '위에서 아래로, 왼쪽부터 빈자리 없이'입니다.
- 틀리는 꼴 완전 이진 트리 — (다)에: 포화 이진 트리도 완전 이진 트리이지만, '더 넣을 자리가 없다'는 모든 층이 꽉 찬 포화를 가리킵니다.
- 틀리는 꼴 포화 이진 트리 — (라)에: 높이 4에 노드 10개면 마지막 층이 덜 찼습니다.
- 틀리는 꼴 높이 — (가)에: 높이는 가장 큰 레벨이고, 노드 하나의 가지 수가 아닙니다.
3. 어떤 이진 트리의 노드가 20개이고, 그 가운데 차수가 1인 노드가 3개입니다. 단말 노드는 몇 개일까요? 답을 끝까지 쓴 뒤 정답을 펼치세요.
정답
받는 답: 9
차수 1인 노드 3개를 빼면 단말 노드와 차수 2인 노드가 합쳐 17개입니다. 단말 노드가 차수 2인 노드보다 하나 많으니 차수 2인 노드가 8개, 단말 노드가 9개입니다. 간선으로 맞춰 보면 3 + 2 × 8 = 19개이고, 노드 20 − 1과 같습니다.
- 틀리는 꼴 8: 차수 2인 노드 수를 답했습니다.
- 틀리는 꼴 17: 단말 노드와 차수 2인 노드를 합친 수입니다.