트리와 운행법, 수식 표기
쉽게 말하면
트리는 뿌리(루트)에서 가지가 뻗어 나가는 모양의 자료 구조예요. 자식이 최대 둘인 트리를 이진 트리라고 해요. 트리의 모든 노드를 한 번씩 방문하는 순서가 세 가지 있어요. 루트를 먼저 보면 전위, 가운데 보면 중위, 마지막에 보면 후위예요. 수식도 같은 원리로 연산자를 앞에 쓰면 전위 표기, 가운데 쓰면 중위 표기(우리가 평소 쓰는 식), 뒤에 쓰면 후위 표기예요.
시험용 정의
트리는 사이클이 없는 계층형 비선형 구조다. 맨 위 노드가 근(루트) 노드, 자식이 없는 노드가 단말(리프) 노드, 한 노드의 자식 수가 차수, 노드 차수 중 가장 큰 값이 트리의 차수다. 이진 트리는 모든 노드의 차수가 2 이하인 트리로, 레벨 k의 최대 노드 수는 2k−1, 깊이 k인 트리의 최대 노드 수는 2k−1이다. 운행법은 루트(Root)를 방문하는 시점에 따라 전위(Root → Left → Right), 중위(Left → Root → Right), 후위(Left → Right → Root)로 나뉜다. 수식 표기법도 연산자 위치에 따라 전위(Prefix), 중위(Infix), 후위(Postfix) 표기로 나뉜다.
비유로 이해하기
가계도로 운행을 떠올리자. 전위는 '나를 먼저 소개하고 큰아이, 작은아이', 중위는 '큰아이, 나, 작은아이', 후위는 '큰아이, 작은아이, 마지막에 나'다.
자세히
먼저 알아 둘 말
| 말 | 뜻 |
|---|---|
| 근(루트) 노드 | 트리 맨 위의 노드 |
| 단말(리프) 노드 | 자식이 없는 노드. 차수가 0 |
| 차수 | 한 노드가 가진 자식 수. 트리의 차수 = 노드 차수의 최댓값 |
| 레벨 | 루트를 1로 두고 아래로 1씩 증가 |
| 깊이(높이) | 트리의 최대 레벨 |
| 형제 노드 | 부모가 같은 노드들 |
운행법 예
A
/ \
B C
/ \ \
D E F- 전위 (Root-L-R): A B D E C F
- 중위 (L-Root-R): D B E A C F
- 후위 (L-R-Root): D E B F C A
요령: 큰 덩어리부터 '루트, 왼쪽 서브트리, 오른쪽 서브트리'로 나눠 차례로 펼친다.
수식 표기 변환 (괄호 치기 방법)
중위식 (A + B) * C − D / E
- 우선순위대로 모든 연산에 괄호: ( ( (A + B) * C ) − (D / E) )
- 후위: 연산자를 자기 괄호의 닫는 쪽으로 →
A B + C * D E / − - 전위: 연산자를 자기 괄호의 여는 쪽으로 →
− * + A B C / D E
후위식 계산은 스택으로 한다. 피연산자는 push, 연산자를 만나면 두 개를 pop해 계산한 결과를 push. 예: 3 4 + 5 * → 7 → 35
이진 트리 공식
| 항목 | 공식 |
|---|---|
| 레벨 k의 최대 노드 수 | 2^(k−1) |
| 깊이 k 이진 트리의 최대 노드 수 | 2^k − 1 (포화 이진 트리) |
| 단말 노드 수 n0와 차수 2 노드 수 n2 | n0 = n2 + 1 |
기출에서 더 나온 것
| 말 | 뜻 |
|---|---|
| 이진 탐색 트리 | 왼쪽엔 작은 값, 오른쪽엔 큰 값. 한쪽으로 치우치면 검색이 선형 검색처럼 느려진다 |
| AVL 트리 | 왼쪽·오른쪽 높이 차이를 1 이하로 유지하는 균형 이진 탐색 트리 |
| 2-3 트리 · 레드-블랙 트리 | 스스로 균형을 맞추는 탐색 트리. 최악에도 검색 효율이 좋다 |
| 순회의 영어 이름 | 전위(Preorder) 루트-왼쪽-오른쪽, 중위(Inorder) 왼쪽-루트-오른쪽, 후위(Postorder) 왼쪽-오른쪽-루트 |
시험에 이렇게 나와요
- 전위(Preorder) → 루트-왼쪽-오른쪽, 중위(Inorder) → 왼쪽-루트-오른쪽, 후위(Postorder) → 왼쪽-오른쪽-루트
- 트리의 차수 → 자식 수가 가장 많은 노드의 자식 수, 단말 노드 → 자식이 없는 노드
- 전위식을 후위식으로 바꾸기, 후위식 계산하기 → 스택으로 연산자와 피연산자를 처리
- 사이클이 없고 계층으로 이어진 그래프 → 트리
확인 문제
Q1. 중위 표기식 A + B * C 를 후위 표기식으로 바꾸면?
- A B + C *
- + A * B C
- A B C * +
- A + B C *
정답 보기
3번 A B C * +
곱셈이 먼저라 (A + (B * C))로 괄호를 친다. 괄호마다 연산자를 닫는 괄호 자리로 옮기면 A (B C *) + → A B C * +.
Q2. 본문 예시 트리(A의 자식 B·C, B의 자식 D·E, C의 오른쪽 자식 F)를 후위 운행한 결과는?
- D B E A C F
- D E B F C A
- A B D E C F
- D E F B C A
정답 보기
2번 D E B F C A
왼쪽 서브트리(D E B), 오른쪽 서브트리(F C), 루트(A).
Q3. 후위 표기식 2 3 4 * +의 계산 결과는?
- 9
- 14
- 20
- 24
정답 보기
2번 14
3 * 4 = 12, 2 + 12 = 14.
Q4. 중위식 A * B + C * D 를 전위식으로 바꾸면?
- + A * B * C D
- A B * C D * +
- * + A B C D
- + * A B * C D
정답 보기
4번 + * A B * C D
((A*B) + (C*D)) → + (* A B) (* C D).
Q5. 깊이가 4인 이진 트리가 가질 수 있는 최대 노드 수는?
- 8
- 15
- 16
- 31
정답 보기
2번 15
15개다. 깊이 k인 이진 트리의 최대 노드 수는 2^k - 1 = 16 - 1이다.
헷갈리기 쉬운 O·X
중위 운행은 Left → Right → Root 순서로 방문한다.
정답 보기
X 그건 후위. 중위는 Left → Root → Right.
자식이 없는 노드를 단말 노드라고 한다.
정답 보기
O
트리의 차수는 전체 노드 수를 뜻한다.
정답 보기
X 노드들의 차수(자식 수) 중 최댓값이다.