5. Grundlegende Datenstrukturen (7 Punkte)

5(d) · 원래 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은 전위 순회의 첫 값이고 중위 순회의 가운데 분할점입니다.

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

빈 BST의 첫 삽입 key는 root가 되므로 37이 반드시 첫 번째입니다. 이후 어떤 node가 자신의 자손보다 먼저 삽입되어야 그 자손이 올바른 parent 아래에 도달합니다.

가장 안전한 정답은 원래 트리의 Preorder입니다. parent를 자식보다 먼저 방문하기 때문에 같은 BST를 재구성합니다.

따라서 [37,15,7,29,56,85]는 즉시 사용할 수 있는 정답입니다. 이 문제의 23과 60은 5(b)에서 추가된 값이므로 원래 순서에 넣으면 안 됩니다.

필요한 개념을 깊게 배우기

개념 1

0단계 · 첫 키(key)가 루트(root)

빈 트리에는 비교할 노드가 없으므로 첫 키가 루트가 됩니다. 회전 없는 일반 이진 탐색 트리 삽입에서는 루트가 나중에 자동 교체되지 않습니다.

원래 루트가 37이므로 가능한 모든 순서는 37로 시작해야 합니다.

수식으로 정확히 쓰기

\[k_{1}=\operatorname{root}(T)\]k₁=\operatorname{root}(T)
개념 2

1단계 · 조상이 자손보다 먼저(ancestor-before-descendant)

15는 7과 29의 부모(parent)이므로 둘보다 먼저 들어가야 합니다. 56은 85의 부모이므로 85보다 먼저 들어가야 합니다.

왼쪽 부분 트리 원소와 오른쪽 부분 트리 원소는 루트 37에서 즉시 서로 다른 방향으로 가므로 서로 섞여 삽입되어도 상대 구조에 영향을 주지 않습니다.

수식으로 정확히 쓰기

핵심 규칙15\prec7,\qquad15\prec29

핵심 규칙56\prec85

개념 3

2단계 · 전위 순회(Preorder)가 안전한 이유

전위 순회는 루트를 먼저, 그다음 각 부분 트리의 루트를 자손보다 먼저 출력합니다. 그래서 그 순서대로 빈 이진 탐색 트리에 삽입하면 조상이 먼저 준비됩니다.

주어진 전위 순회가 바로 [37,15,7,29,56,85]이므로 추가 계산 없이 정답 하나를 얻습니다.

수식으로 정확히 쓰기

핵심 규칙\text{유효한 한 순서}=\operatorname{Pre}(T)

개념 4

3단계 · 직접 삽입해 검산

37은 루트, 15는 37의 왼쪽, 7은 15의 왼쪽, 29는 15의 오른쪽, 56은 37의 오른쪽, 85는 56의 오른쪽에 붙는지 확인합니다.

최종 중위 순회가 정렬되고 트리 모양이 5(a)와 같으면 검산이 끝납니다.

수식으로 정확히 쓰기

핵심 규칙\langle37,15,7,29,56,85\rangle

초보자용 연결 강의

이 소문제를 왜 배우나

같은 key 집합도 삽입 순서에 따라 BST shape가 크게 달라집니다. 완성 tree를 보고 가능한 과거 순서를 구성하는 문제는 parent가 먼저 존재해야 descendant가 올바른 자리에 도달한다는 인과 관계를 이해하는 훈련입니다.

풀이 전에 꼭 알아야 할 말

조상(ancestor)과 자손(descendant)

어떤 노드에서 자식 간선을 한 번 이상 따라 내려가 만나는 노드가 자손이고, 위쪽 노드는 조상입니다. 부모-자식보다 넓은 관계입니다.

아주 작은 예: 37은 15의 부모이면서 7과 29의 조상입니다.

빈 이진 탐색 트리(BST)의 첫 삽입

비교할 노드가 전혀 없으므로 첫 키가 루트가 됩니다. 일반 이진 탐색 트리에는 나중에 루트를 자동 교체하는 회전(rotation)이 없습니다.

아주 작은 예: 원래 루트가 37이면 가능한 순서는 반드시 37로 시작합니다.

전위 순회(Preorder)의 부모 우선 성질

전위 순회는 각 부분 트리 루트를 먼저 출력한 뒤 그 자손을 출력합니다. 그래서 키가 중복되지 않는 이진 탐색 트리의 전위 순회는 같은 모양을 만드는 안전한 삽입 순서입니다.

아주 작은 예: [37,15,7]에서는 37과 15가 7보다 먼저 준비됩니다.

조직도 등록 순서

빈 인사 시스템에서 대표가 먼저 등록되어야 부서장이 그 아래에 들어가고, 부서장이 먼저 있어야 팀원이 올바른 부서에 연결됩니다. 서로 다른 부서의 등록은 섞어도 되지만 자기 부서의 상사는 먼저 있어야 합니다.

대표를 가장 먼저 등록
↔
루트 37이 먼저
부서장 계정을 팀원보다 먼저 생성
↔
ancestor before descendant
서로 다른 부서 등록 작업은 사이에 섞을 수 있음
↔
left/right subtree 독립

비유의 한계: 실제 조직 시스템은 나중에 상사를 바꿀 수 있지만 plain BST insertion은 기존 node를 재배치하지 않습니다. 여기서는 insertion만 허용됩니다.

먼저 와야 하는 관계를 화살표로 보기

\(37 \to 15, 56\)37 → 15, 56root가 두 subtree root보다 먼저 존재해야 합니다.
\(15 \to 7, 29\)15 → 7, 2915가 먼저 있어야 7과 29가 37의 직접 child가 되지 않습니다.
\(56 \to 85\)56 → 8556이 먼저 있어야 85가 37.right를 차지하지 않습니다.

화살표 \(A\to B\)A→B는 A가 B보다 먼저 삽입되어야 한다는 뜻입니다. 이 DAG의 화살표 방향을 거스르지 않는 한 줄 순서 하나가 답입니다.

먼저 작은 예제로 연습 · 10의 children 5,20을 만드는 순서

원하는 tree가 root 10, left child 5, right child 20인 경우 가능한 삽입 순서를 구성합니다.

10을 첫 번째로 둔다

빈 tree의 첫 key가 root이므로 다른 key로 시작하면 root shape가 달라집니다.

[10]
5를 삽입한다

\(5<10\)5<10이므로 10.left에 연결됩니다. 아직 다른 node가 경로를 가로막지 않습니다.

[10,5]
20을 삽입한다

\(20>10\)20>10이므로 10.right에 연결되어 목표 tree가 완성됩니다.

[10,5,20]

작은 예제의 결론: Preorder [10,5,20]은 root와 parent를 children보다 먼저 보장하므로 원래 shape를 재현합니다.

이제 실제 시험 문제에 연결

순서의 첫 key는 무엇인가?

원래 tree의 root 37입니다. 15나 56이 먼저 들어가면 그 key가 root가 되어 원래 tree를 만들 수 없습니다.

왼쪽 subtree에서 강제되는 순서는 무엇인가?

15가 7과 29보다 먼저여야 합니다. 7과 29 사이에는 ancestor 관계가 없어 둘의 상대 순서는 자유롭습니다.

오른쪽 subtree에서 강제되는 순서는 무엇인가?

56이 85보다 먼저여야 85가 37의 직접 right child를 차지하지 않고 56.right에 도달합니다.

안전한 순서 하나는 어떻게 즉시 얻는가?

원래 tree의 Preorder [37,15,7,29,56,85]를 사용합니다. 모든 subtree에서 root가 descendants보다 먼저 나옵니다.

제안 순서를 어떻게 검산하는가?

빈 tree에서 여섯 insertion을 실제로 재생해 \(\text{dependency} \text{edge} 37\to 15/56, 15\to 7/29, 56\to 85\)dependency edge 37→15/56, 15→7/29, 56→85가 모두 생기는지 확인합니다.

답이 맞는지 스스로 검산

  • 재생 후 root가 37이고 edge 집합이 {(37,15),(37,56),(15,7),(15,29),(56,85)}인지 비교합니다.
  • 최종 inorder가 [7,15,29,37,56,85]로 정렬되고 node 수가 여섯인지 확인합니다.
  • 5(b)에서 나중에 추가한 23과 60이 원래 tree 순서에 섞이지 않았는지 확인합니다.

30초 자가점검

정렬된 Inorder [7,15,29,37,56,85]를 삽입하면 같은 tree인가?

힌트: 첫 key가 무엇이 되는지부터 봅니다.

정답: 아닙니다. 첫 key 7이 root가 되고 계속 큰 값이 right로 붙어 오른쪽 사슬에 가까운 다른 shape가 됩니다.

7과 29 중 어느 것이 먼저여야 하는가?

힌트: 둘 사이에 ancestor 관계가 있는지 확인합니다.

정답: 15가 먼저라는 조건만 지키면 7과 29의 상대 순서는 어느 쪽도 가능합니다. 둘은 서로 독립인 sibling입니다.

마지막에 쓰는 시험 답안 틀

한 가능한 순서는 Preorder 그대로 [37,15,7,29,56,85]이다. parent가 자손보다 먼저 삽입되므로 동일한 tree shape가 재현된다.

자주 하는 실수

근거와 정확성 범위

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

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