5. Grundlegende Datenstrukturen (7 Punkte)

5(a) · 전위 순회(Preorder)와 중위 순회(Inorder)로 BST를 유일하게 복원하기

선행지식이 전혀 없어도 이 페이지 하나에서 용어를 배우고, 작은 예제를 거쳐 실제 시험 풀이와 검산까지 따라가도록 구성했습니다.

  1. 용어: 기호와 전제
  2. 직관: 비유와 작은 예
  3. 풀이: 실제 상태 변화
  4. 확인: 검산과 자가점검

자료의 성격과 정확성 경계

시험 문언과 숫자·배점은 비공식 복기 자료 lines 246-268에서 가져왔습니다. 정의와 알고리즘은 현재 강의 Lecture 03 pp.46-51, 66-71, 80-81 및 Sheet05-GrpSol pp.7-12로 교차 확인했습니다. 이 문제의 key는 모두 서로 다르며, duplicate가 있는 일반 BST에서는 강의나 구현이 정한 equality 방향을 먼저 밝혀야 합니다.

문제를 읽기 전에 알아둘 기호와 용어

기호를 모른 채 풀이를 외우지 않도록, 이 문제에서 실제로 쓰는 뜻과 작은 예를 먼저 확인합니다.

기호·용어뜻작은 예
노드(node / Knoten)키(key) 하나와 왼쪽·오른쪽 자식 연결을 담는 트리의 한 칸입니다.37이 전체 트리의 루트 노드입니다.
간선(edge / Kante)부모와 자식 사이를 잇는 선이며 왼쪽 간선과 오른쪽 간선은 서로 다른 의미를 가집니다.37에서 15로 가는 선은 왼쪽 간선입니다.
빈 포인터(nil)그 방향에 자식 노드가 없다는 뜻입니다. 값 0이나 실제 키가 아닙니다.\(56.\text{left}=\text{nil}\)56.left=nil이므로 search(50)는 그 자리에서 실패합니다.
왼쪽/오른쪽(L / R)현재 키와 목표를 비교한 뒤 각각 왼쪽 또는 오른쪽 자식으로 이동한다는 경로 표기입니다.23의 경로는 \(37(L)\to 15(R)\to 29(L)\)37(L)→15(R)→29(L)입니다.
이진 탐색 트리(BST)모든 노드에서 왼쪽 부분 트리의 키는 더 작고 오른쪽 부분 트리의 키는 더 큰 트리입니다.15의 왼쪽에는 7, 오른쪽에는 29가 놓입니다.
전위/중위 순회(Pre / In)전위 순회(Preorder)는 root-left-right, 중위 순회(Inorder)는 left-root-right 순서로 같은 트리를 읽는 규칙입니다.루트 37은 전위 순회의 첫 값이고 중위 순회의 가운데 분할점입니다.

먼저 문제의 정체를 줄글로 이해하기

Preorder는 root를 가장 먼저 알려 주고, Inorder는 root를 기준으로 왼쪽 subtree와 오른쪽 subtree의 원소 집합을 나눠 줍니다. 두 정보를 번갈아 사용하면 트리를 재귀적으로 복원할 수 있습니다.

이 문제의 key는 모두 서로 다릅니다. 따라서 Inorder에서 root 위치가 하나로 정해지고, 왼쪽·오른쪽 구간도 모호하지 않아 결과 트리가 유일합니다.

BST의 Inorder는 원래 오름차순이므로 주어진 Inorder가 BST 조건과 일치하는지도 먼저 확인할 수 있습니다.

필요한 개념을 깊게 배우기

개념 1

0단계 · 순회(Traversal)의 세 위치

전위 순회(Preorder)는 root-left-right, 중위 순회(Inorder)는 left-root-right입니다. 이름의 pre와 in은 루트(root)를 언제 읽는지를 나타냅니다.

복원에서는 전위 순회의 첫 원소로 루트를 찾고 중위 순회에서 그 루트 왼쪽과 오른쪽에 있는 값들을 부분 트리(subtree) 집합으로 나눕니다.

수식으로 정확히 쓰기

핵심 규칙\operatorname{Pre}(T)=N\to L\to R

\[\operatorname{In}(T)=L\to N\to R\]\operatorname{In}(T)=L\to N\to R
개념 2

1단계 · 첫 루트(root) 37

전위 순회의 첫 값 37이 전체 루트입니다. 중위 순회에서 37 왼쪽 [7,15,29]는 왼쪽 부분 트리, 오른쪽 [56,85]는 오른쪽 부분 트리입니다.

전위 순회에서도 왼쪽 부분 트리에는 원소 3개가 있으므로 다음 세 값 [15,7,29]가 왼쪽, 남은 [56,85]가 오른쪽입니다.

수식으로 정확히 쓰기

\[\operatorname{root}(T)=37\]\operatorname{root}(T)=37
\[L=\{7,15,29\}\]L=\{7,15,29\}
\[R=\{56,85\}\]R=\{56,85\}
개념 3

2단계 · 부분 트리(subtree)에 같은 규칙 반복

왼쪽 전위 순회의 첫 값 15가 왼쪽 부분 트리 루트입니다. 중위 순회 [7,15,29]에서 7은 왼쪽, 29는 오른쪽이므로 15의 두 자식이 됩니다.

오른쪽 전위 순회의 첫 값 56이 오른쪽 부분 트리 루트이고 중위 순회 [56,85]에서 56 왼쪽은 비어 있고 85가 오른쪽 자식입니다.

수식으로 정확히 쓰기

핵심 규칙15.\mathrm{left}=7,\qquad 15.\\(\text{mathrm}{\text{right}}=29\)mathrm{right}=29

핵심 규칙56.\mathrm{left}=\varnothing,\qquad 56.\\(\text{mathrm}{\text{right}}=85\)mathrm{right}=85

개념 4

3단계 · 두 순회로 결과 검산

완성한 트리를 전위 순회로 읽어 원문 [37,15,7,29,56,85]가 나오는지 확인합니다. 이어 중위 순회로 읽어 [7,15,29,37,56,85]인지 확인합니다.

두 순회가 모두 일치하면 단순히 이진 탐색 트리처럼 보이는 정도가 아니라 주어진 정보 전체를 만족한 것입니다.

수식으로 정확히 쓰기

핵심 규칙\operatorname{Pre}(T_{\mathrm{answer}})=\operatorname{Pre}_{\mathrm{input}}

핵심 규칙\operatorname{In}(T_{\mathrm{answer}})=\operatorname{In}_{\mathrm{input}}

초보자용 연결 강의

이 소문제를 왜 배우나

서로 다른 두 sequence가 어떻게 하나의 tree 그림을 결정하는지 이해하면 traversal을 단순 암기하지 않고, root와 subtree라는 재귀 구조를 실제로 읽을 수 있습니다. 이후 BST 복원·직렬화 문제의 기본 도구가 됩니다.

풀이 전에 꼭 알아야 할 말

트리(tree)의 부품

노드(node)는 키(key)를 담는 칸, 간선(edge)은 두 노드를 잇는 선, 루트(root)는 부모가 없는 시작 노드, 자식이 없는 노드는 잎(leaf)입니다. 어떤 노드 아래의 전체 묶음이 부분 트리(subtree)이고 빈 자식 자리는 nil입니다.

아주 작은 예: 루트 10의 왼쪽 자식이 5라면 5와 그 아래 모든 노드가 10의 왼쪽 부분 트리입니다.

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

이진 트리는 노드마다 왼쪽·오른쪽 자식을 최대 하나씩 갖습니다. 이진 탐색 트리는 여기에 모든 왼쪽 부분 트리 키가 작고 모든 오른쪽 부분 트리 키가 크다는 전역 약속을 더합니다.

아주 작은 예: 10의 오른쪽 부분 트리 어디에도 10보다 작은 7이 올 수 없습니다.

순회(Traversal)

트리를 바꾸는 연산이 아니라 같은 트리의 노드를 어느 순서로 읽을지 정한 규칙입니다. 전위 순회는 root-left-right, 중위 순회는 left-root-right입니다.

아주 작은 예: 루트 10, 자식 5와 20이면 \(\text{Pre}=[10,5,20], \text{In}=[5,10,20]\)Pre=[10,5,20], In=[5,10,20]입니다.

서로 다른 키(key) 전제

같은 숫자가 중복되지 않으므로 중위 순회에서 루트의 위치가 하나뿐입니다. 중복 키가 있으면 같은 값을 어느 쪽에 둘지 규칙이 추가로 필요합니다.

아주 작은 예: 이 문제에서 37은 중위 순회에 정확히 한 번만 나옵니다.

책 목차를 두 방식으로 읽기

전위 순회(Preorder)는 장 제목을 먼저 읽고 그 아래 절을 읽는 목차이며, 중위 순회(Inorder)는 왼쪽 절을 읽은 뒤 장 제목을 만나고 오른쪽 절을 읽는 목록이라고 생각합니다. 같은 장 제목을 두 목록에서 맞추면 양쪽 절 묶음이 드러납니다.

가장 먼저 적힌 장 제목
↔
전위 순회의 첫 키인 부분 트리 루트
장 제목 앞뒤에 놓인 두 절 묶음
↔
중위 순회에서 루트 왼쪽·오른쪽 구간
각 절 안에서 같은 목차 규칙을 반복
↔
재귀적으로 작은 subtree 복원

비유의 한계: 실제 목차는 제목이 중복될 수 있지만 이 문제의 key는 모두 다릅니다. 비유는 방문 순서와 분할만 설명하며 BST의 수치 대소 관계 자체를 대신하지 않습니다.

두 순회열(sequence)을 같은 루트에서 자르는 세 단계

전위 순회: [37 | 15,7,29 | 56,85]37이 전체 루트이고 뒤의 세 값과 두 값이 왼쪽·오른쪽 부분 트리의 전위 순회입니다.
중위 순회: [7,15,29 | 37 | 56,85]37의 위치가 왼쪽 원소 세 개와 오른쪽 원소 두 개를 정확히 분리합니다.
작은 문제 반복왼쪽은 root 15, 오른쪽은 root 56으로 같은 분할 규칙을 다시 적용합니다.

각 프레임은 Preorder 첫 값을 root로 표시하고 Inorder의 같은 값 양옆을 subtree로 나눕니다. 원소 수가 정해지면 Preorder의 다음 구간 길이도 자동으로 정해집니다.

먼저 작은 예제로 연습 · 세 노드(node) [10,5,20] 복원

Preorder [10,5,20], Inorder [5,10,20]인 서로 다른 key 세 개를 먼저 복원해 봅니다.

root 10 선택

Preorder는 root를 가장 먼저 출력하므로 첫 값 10이 전체 root입니다.

\(\text{루트}=10\)root=10
Inorder를 10에서 분할

10 왼쪽의 5는 left subtree, 오른쪽의 20은 right subtree 원소입니다.

\(L=[5], R=[20]\)L=[5], R=[20]
두 leaf 연결

각 구간에 원소가 하나뿐이므로 5와 20은 더 분할할 child가 없는 leaf입니다.

5 ← \(10 \to 20\)10 → 20

작은 예제의 결론: Preorder가 root를 알려 주고 Inorder가 양쪽 원소 집합을 알려 주면 각 작은 subtree에서도 같은 절차를 반복할 수 있습니다.

이제 실제 시험 문제에 연결

첫 root는 무엇이며 왜 37인가?

Preorder의 첫 값은 현재 subtree의 root이므로 37입니다. Inorder 첫 값 7을 root로 고르는 것이 아닙니다.

37의 왼쪽과 오른쪽 원소는 무엇인가?

Inorder에서 37 앞의 [7,15,29]가 left subtree, 뒤의 [56,85]가 right subtree입니다.

왼쪽 subtree의 root와 children은 어떻게 정하는가?

왼쪽 Preorder 구간 [15,7,29]의 첫 값 15가 root이고, Inorder [7,15,29]가 7과 29를 양쪽으로 나눕니다.

오른쪽 subtree는 왜 56의 right child 85인가?

오른쪽 Preorder 첫 값 56이 root이며 Inorder [56,85]에서 56 왼쪽은 비고 85가 오른쪽에 있기 때문입니다.

BST라는 추가 정보는 무엇을 바꾸는가?

unique-key BST에서는 Lecture 03처럼 Preorder의 root보다 작은 연속 구간과 큰 구간만으로도 복원 가능합니다. 주어진 Inorder는 일반 binary-tree 방식의 분할과 강력한 검산에 사용합니다.

답이 맞는지 스스로 검산

  • 완성 tree를 root-left-right로 다시 읽으면 [37,15,7,29,56,85]가 정확히 나와야 합니다.
  • left-root-right로 읽으면 [7,15,29,37,56,85]가 나오며, unique-key BST이므로 strictly increasing이어야 합니다.
  • 각 edge에서 왼쪽 child와 그 descendants는 ancestor보다 작고 오른쪽 descendants는 더 큰지 확인합니다.

30초 자가점검

일반 binary tree에서 Preorder 하나만 주어지면 항상 shape가 유일한가?

힌트: root 위치만 알고 left subtree의 크기를 아는지 생각합니다.

정답: 아닙니다. 일반 binary tree는 Preorder 하나만으로 left/right 구간 경계를 알 수 없어 여러 shape가 가능합니다.

unique-key BST에서는 왜 Preorder 하나만으로도 복원 가능한가?

힌트: root보다 작은 값과 큰 값은 갈 수 있는 방향이 정해집니다.

정답: BST 대소 관계가 Preorder 뒤 원소를 left와 right subtree로 나누므로 각 구간에서 재귀적으로 root를 정할 수 있습니다.

실제 문제의 상태 변화를 한 단계씩 재현하기

각 단계에서 무엇을 했는지, 왜 그렇게 했는지, 결과가 무엇인지 차례대로 확인합니다.

  1. 단계 1

    Preorder 첫 값 \(37 \to \)37 →전체 root

  2. 단계 2

    Inorder를 37에서 분할 → left [7,15,29], right [56,85]

  3. 단계 3

    왼쪽 Preorder [15,7,29]의 \(\text{루트} 15 \to \text{children} 7,29\)root 15 → children 7,29

  4. 단계 4

    오른쪽 Preorder [56,85]의 \(\text{루트} 56 \to \text{right} \text{child} 85\)root 56 → right child 85

마지막에 쓰는 시험 답안 틀

37을 root로 둔다. Inorder에서 37 왼쪽 [7,15,29], 오른쪽 [56,85]로 나눈다. 왼쪽 subtree root는 15이고 children은 7,29이다. 오른쪽 subtree root는 56이고 right child는 85이다.

자주 하는 실수

근거와 정확성 범위

복기 문언, 강의 정의, 공식 연습 풀이, 추가 유도를 구분해 표시합니다.

마지막 생성: 2026-08-02 08:51