I-5 BST 순회 — root를 언제 읽는지만 알면 정렬 출력이 보인다
먼저 이 문제의 정체부터
Traversal은 트리의 모든 노드를 어떤 순서로 방문할지 정하는 규칙입니다. 이름 세 개를 통째로 외우기보다 root를 언제 출력하는지를 번역하세요. preorder는 자식보다 먼저, inorder는 왼쪽과 오른쪽 사이, postorder는 자식 뒤에 root를 읽습니다.
BST에서는 왼쪽 subtree의 모든 키가 root보다 작고 오른쪽 subtree의 모든 키가 root보다 큽니다. 따라서 작은 것→\(\text{루트}\to \)root→큰 것 순서인 left-root-right, 즉 inorder가 오름차순을 만듭니다.
이 성질은 트리 모양이 균형인지 아닌지와 무관합니다. BST 순서 invariant만 유지되면 재귀적으로 모든 왼쪽 값, root, 모든 오른쪽 값이 이어져 정렬된 결과가 됩니다.
0. 필요한 개념을 처음부터 배우기
개념 1 · 트리는 재귀 구조다
트리의 한 노드를 보면 root와 left subtree, right subtree로 다시 나눌 수 있습니다. 각 subtree도 똑같이 작은 트리입니다. 그래서 traversal 정의도 '왼쪽을 같은 방식으로 방문하고, root를 읽고, 오른쪽을 같은 방식으로 방문한다'처럼 재귀적으로 적습니다.
빈 subtree에서는 아무것도 출력하지 않는 것이 base case입니다. 이 base case가 있어 재귀 호출이 끝납니다.
수식으로 정확히 쓰기
핵심 규칙트리 = 루트 + 왼쪽 부분 트리 + 오른쪽 부분 트리
핵심 규칙\(\text{traverse}(\text{nil})=\)traverse(nil)=아무것도 하지 않음
이 절에서 꼭 기억할 것
- subtree도 같은 규칙을 적용한다.
- 방문 순서는 root의 위치로 구분한다.
개념 2 · 세 traversal 이름 해독
Preorder는 root-left-right입니다. pre는 root 처리를 두 subtree보다 먼저 한다는 뜻입니다. Inorder는 left-root-right로 root가 두 subtree 사이에 있습니다. Postorder는 left-right-root로 root가 마지막입니다.
왼쪽과 오른쪽의 상대 순서는 세 방식 모두 보통 left before right입니다. 달라지는 것은 root가 앞, 중간, 뒤 중 어디에 놓이는가입니다.
수식으로 정확히 쓰기
핵심 규칙전위 순회(preorder): N-L-R
핵심 규칙중위 순회(inorder): L-N-R
핵심 규칙후위 순회(postorder): L-R-N
이 절에서 꼭 기억할 것
- N은 현재 노드, 즉 루트
- pre/in/post는 N의 위치를 말한다.
개념 3 · BST 순서 invariant
BST의 각 노드에서 왼쪽 subtree의 모든 키는 node key보다 작거나 같고, 오른쪽 subtree의 모든 키는 크거나 같습니다. 중복 처리 규칙은 구현에 따라 한쪽으로 정하지만 정렬된 nondecreasing 출력이라는 핵심은 유지됩니다.
이 성질을 한 노드에서만 확인하는 것이 아니라 모든 subtree에 재귀적으로 적용합니다. 그래서 왼쪽 inorder 결과 자체가 정렬되어 있고, 그 뒤 root, 그 뒤 더 큰 오른쪽 inorder 결과가 옵니다.
수식으로 정확히 쓰기
∀x in L
key(x)≤key(root)∀y in R
key(root)≤key(y)이 절에서 꼭 기억할 것
- BST invariant가 있어야 inorder가 sorted다.
- 일반 binary tree에서는 inorder가 자동 정렬되지 않는다.
개념 4 · 왜 inorder가 정렬인지 증명
귀납적으로 왼쪽 subtree의 inorder가 오름차순이고 오른쪽 subtree의 inorder도 오름차순이라고 가정합니다. BST 성질상 왼쪽의 모든 값≤\(\text{루트}\le \)root≤오른쪽의 모든 값입니다.
따라서 정렬된 왼쪽 목록 뒤에 root를 붙이고, 다시 정렬된 오른쪽 목록을 붙이면 전체도 오름차순입니다. 빈 트리와 한 노드 트리는 자명하므로 재귀적 증명이 완성됩니다.
수식으로 정확히 쓰기
핵심 규칙\(\text{inorder}(T)=\text{inorder}(L) + [\text{루트}] + \text{inorder}(R)\)inorder(T)=inorder(L) + [root] + inorder(R)
이 절에서 꼭 기억할 것
- 단순 암기가 아니라 invariant+재귀로 설명할 수 있다.
- 출력은 중복이 있으면 nondecreasing이다.
개념 5 · 최소 반례 트리
root 2, left child 1, right child 3인 세 노드 BST를 사용하면 세 traversal을 즉시 비교할 수 있습니다. preorder는 2,1,3이고 postorder는 1,3,2라 정렬되지 않습니다. inorder만 1,2,3입니다.
이 작은 트리는 A, B, D를 동시에 깨 줍니다. 하지만 이 예시만으로 inorder가 모든 BST에서 정렬된다는 보편 명제를 증명한 것은 아니므로, 정답의 완전한 근거는 앞의 BST invariant입니다.
수식으로 정확히 쓰기
핵심 규칙pre: 2,1,3
핵심 규칙in: 1,2,3
핵심 규칙post: 1,3,2
이 절에서 꼭 기억할 것
- 반례와 증명의 역할을 구분한다.
- D='모두'는 A나 B 반례 하나만 있어도 깨진다.
1. 시험장에서 따라 할 풀이 순서
BST 불변식을 사용할 수 있음
순회 순서: 전위 NLR | 중위 LNR | 후위 LRN
\(\text{left} \to \text{루트} \to \text{right}\)left → root → right
\(\text{inorder}=\text{LNR}\)inorder=LNR
문제 조건 BST를 표시한다
일반 binary tree가 아니라 BST이므로 \(\text{left}\le \text{루트}\le \text{right}\)
left≤root≤right성질을 쓸 수 있습니다.핵심 규칙BST 불변식을 사용할 수 있음
세 이름을 기호로 바꾼다
\(\text{pre}=\text{NLR}, \text{in}=\text{LNR}, \text{post}=\text{LRN}\)
pre=NLR, in=LNR, post=LRN으로 적습니다.핵심 규칙순회 순서: 전위 NLR | 중위 LNR | 후위 LRN
오름차순 요구를 구조로 번역한다
작은 값 묶음, root, 큰 값 묶음 순서여야 합니다.
핵심 규칙\(\text{left} \to \text{루트} \to \text{right}\)
left → root → right정의와 맞춘다
left-root-right는 inorder입니다.
\[\text{inorder}=\text{LNR}\]inorder=LNR작은 트리로 다른 보기를 검사한다
2/1/3 트리에서 \(\text{pre}=2,1,3, \text{post}=1,3,2\)
pre=2,1,3, post=1,3,2이므로 정렬이 아닙니다.\[A=거짓, B=거짓\]A=거짓, B=거짓모두라는 D를 제거한다
preorder와 postorder 반례가 있으므로 every traversal은 거짓입니다.
\[D=거짓\]D=거짓일반 근거를 붙인다
모든 subtree에 BST invariant가 재귀 적용되므로 inorder 전체가 정렬됩니다.
핵심 규칙정답 C
2. 이 문제를 실제로 끝까지 풀기
BST의 현재 root를 r이라고 합시다. 왼쪽 subtree의 모든 key는 r 이하이고 오른쪽 subtree의 모든 key는 r 이상입니다. 오름차순 출력을 원하면 작은 값이 들어 있는 왼쪽 subtree를 먼저 모두 출력하고, 다음 r, 마지막으로 큰 값이 들어 있는 오른쪽 subtree를 출력해야 합니다.
이 순서가 바로 inorder의 left-root-right입니다. 왼쪽과 오른쪽 subtree에서도 같은 inorder 규칙을 적용하므로 각 부분도 정렬됩니다. 정렬된 작은 값 목록+[r]+정렬된 큰 값 목록은 전체 정렬 목록입니다.
preorder는 root를 먼저 읽으므로 2/1/3 트리에서 2,1,3을 출력합니다. 1이 2 뒤에 나와 오름차순이 아닙니다. postorder는 root를 마지막에 읽어 1,3,2가 되므로 역시 정렬이 아닙니다.
따라서 A와 B가 거짓이고, 이 둘까지 모두 정렬된다고 하는 D도 거짓입니다. 유일하게 C의 inorder traversal이 맞습니다.
시험 답안에서는 'inorder라서'만 쓰기보다 'BST에서 \(\text{left} \text{keys}\le \text{루트}\le \text{right} \text{keys}\)left keys≤root≤right keys이므로 left-root-right가 sorted'라는 한 줄을 붙이면 개념을 정확히 보여 줄 수 있습니다.
3. 선택지 A–D를 한 줄도 건너뛰지 않고 판정하기
-
A거짓
Preorder는 root-left-right라 작은 왼쪽 키보다 root를 먼저 출력할 수 있습니다.
빠른 확인법: 2/1/3 BST의 preorder는 2,1,3입니다.
-
B거짓
Postorder는 left-right-root라 큰 오른쪽 키가 root보다 먼저 나올 수 있습니다.
빠른 확인법: 2/1/3 BST의 postorder는 1,3,2입니다.
-
C참 — 정답 후보
Inorder는 left-root-right이고 BST에서 왼쪽의 모든 값≤\(\text{루트}\le \)
root≤오른쪽의 모든 값이므로 오름차순입니다.빠른 확인법: 구조의 순서와 값의 순서가 둘 다 L-N-R로 일치합니다.
-
D거짓
Preorder와 postorder에 간단한 반례가 있으므로 '모두'라는 문장은 거짓입니다.
빠른 확인법: A 또는 B 하나만 거짓이어도 D는 즉시 거짓입니다.
4. 초보자가 가장 자주 틀리는 이유
- pre/in/post를 왼쪽·오른쪽 순서의 차이로 잘못 이해한다.
- inorder가 모든 binary tree를 정렬한다고 생각한다. BST invariant가 필요합니다.
- root를 읽는 시점을 표시하지 않고 이름만 암기한다.
- 세 노드 반례를 정답의 일반 증명으로 착각한다.
- 중복 key가 있으면 strictly increasing이 아닐 수 있다는 점을 놓친다. 보통 nondecreasing입니다.
- D의 'jede'를 놓치고 각각을 검사하지 않는다.
5. 시험 답안 템플릿
BST에서는 왼쪽 subtree의 모든 \(\text{key}\le \text{루트}\le \)key≤root≤오른쪽 subtree의 모든 key이다. 따라서 left-root-right 순서로 재귀 방문하면 전체가 오름차순이며, 이것이 inorder traversal이다. preorder와 postorder는 2/1/3 BST에서 각각 2,1,3과 1,3,2이므로 반례가 있다. 정답 C.
6. 스스로 이해했는지 확인
Preorder의 방문 순서는?
정답: root-left-right, 즉 NLR입니다.
Inorder의 방문 순서는?
정답: left-root-right, 즉 LNR입니다.
Postorder의 방문 순서는?
정답: left-right-root, 즉 LRN입니다.
왜 inorder가 일반 binary tree에서도 항상 정렬되지는 않는가?
정답: \(\text{left}\le \text{루트}\le \text{right}\)left≤root≤right라는 BST 순서 invariant가 없기 때문입니다.
2/1/3 트리의 세 출력은?
정답: pre 2,1,3; in 1,2,3; post 1,3,2입니다.
I-5 정답은?
정답: C, inorder traversal입니다.
근거 자료
AuD Gedächtnisprotokoll SoSe 2025.md· Multiple Choice I.5
복기된 문제 문언과 선택지Vorlesung\03BasicDataStructures.pdf· pp. 66-67
BST traversal 정의와 inorder 성질Übung\AuD26_Sheet05-GrpSol.pdf· p. 8
preorder/inorder/postorder 예시Übung\AuD26_Sheet05-Sol.pdf· p. 21
BST traversal 공식 풀이