5. Grundlegende Datenstrukturen (7 Punkte)

5(e) · 다른 삽입 순서가 존재하는 이유와 전체 조건

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

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

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

네, 많이 있습니다. 동일 subtree 안에서는 parent가 descendant보다 먼저라는 제약을 지켜야 하지만, 왼쪽 subtree와 오른쪽 subtree의 원소는 서로 interleave할 수 있습니다.

예를 들어 [37,56,15,85,29,7]도 같은 트리를 만듭니다. 37이 먼저이고, 15가 7·29보다 먼저이며, 56이 85보다 먼저라는 핵심 제약을 모두 만족합니다.

이 문제는 아무 permutation이나 된다는 뜻이 아닙니다. tree가 정의하는 ancestor partial order를 보존하는 순서만 가능합니다.

필요한 개념을 깊게 배우기

개념 1

0단계 · 강제되는 순서와 자유로운 순서

37이 먼저, 15가 7과 29보다 먼저, 56이 85보다 먼저라는 관계는 강제됩니다. 반면 15 부분 트리 작업과 56 부분 트리 작업의 상대 순서는 자유롭습니다.

7과 29도 둘 다 15의 자식이고 서로 조상 관계가 없어 15 뒤에서는 어느 쪽이 먼저 와도 됩니다.

수식으로 정확히 쓰기

핵심 규칙u\text{가 }v\text{의 조상}\;\Longrightarrow\;u\prec v

개념 2

1단계 · 올바른 대안 순서 검증

대안 [37,56,15,85,29,7]을 삽입하면 56은 37의 오른쪽, 15는 37의 왼쪽, 85는 56의 오른쪽, 29는 15의 오른쪽, 7은 15의 왼쪽이 됩니다.

순서가 원래 전위 순회와 크게 달라도 결과 간선(edge)이 모두 같으므로 올바릅니다.

수식으로 정확히 쓰기

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

개념 3

2단계 · 조상보다 자손이 먼저 오면 실패

[37,7,15,...]에서는 7이 먼저 37의 왼쪽을 차지하고 15가 7의 오른쪽에 붙어 원래 15 루트 부분 트리가 나오지 않습니다.

[37,85,56,...]에서도 85가 37의 오른쪽을 차지해 원래 구조와 달라집니다. 자손이 조상보다 먼저 들어간 것이 원인입니다.

수식으로 정확히 쓰기

핵심 규칙v\prec u\ \text{(자손이 조상보다 먼저)}\;\Longrightarrow\;\text{모양이 달라질 수 있음}

개념 4

3단계 · 가능한 순서 개수

루트 37 뒤 왼쪽 부분 트리의 가능한 내부 순서는 [15,7,29] 또는 [15,29,7] 두 개입니다. 오른쪽은 [56,85] 한 개입니다.

길이 3과 2인 두 순서를 내부 순서를 보존하며 섞는 방법은 \(C(5,3)=10\)C(5,3)=10개이고 왼쪽 내부 순서 2개를 곱해 총 20개의 삽입 순서가 있습니다.

수식으로 정확히 쓰기

\[2\cdot\binom{5}{3}=20\]2\cdot\binom{5}{3}=20
초보자용 연결 강의

이 소문제를 왜 배우나

BST insertion 순서는 하나의 고정된 history가 아니라 ancestor 제약을 만족하는 여러 가능한 history입니다. 강제되는 관계와 자유롭게 섞을 수 있는 관계를 구분하면 ‘다른 순서가 있는가’에 예시와 이유를 함께 답할 수 있습니다.

풀이 전에 꼭 알아야 할 말

부분 순서(partial order)

모든 두 원소의 순서를 강제하지 않고 일부 선행 관계만 정하는 규칙입니다. 이 트리에서는 37이 먼저, 15가 7과 29보다 먼저, 56이 85보다 먼저라는 관계만 강제됩니다.

아주 작은 예: 15와 56 사이에는 어느 쪽이 먼저라는 화살표가 없습니다.

순서 보존 끼워 넣기(interleaving)

두 순회열 각각의 내부 순서는 유지하면서 한 줄로 섞는 것입니다. 서로 다른 부분 트리는 루트에서 즉시 분리되므로 이렇게 섞어도 상대 구조가 변하지 않습니다.

아주 작은 예: [15,7]과 [56,85]를 [56,15,85,7]처럼 섞을 수 있습니다.

조합 \(\binom{n}{k}\)

n개의 위치 중 k개를 고르는 방법 수입니다. 이 문제에서는 루트 뒤 다섯 위치 중 왼쪽 부분 트리 세 위치를 선택할 때만 선택 심화로 사용합니다.

아주 작은 예: \(C(5,3)=10\)C(5,3)=10이며 원문 정답에는 이 계산이 필수가 아닙니다.

선수과목이 있는 시간표

어떤 과목은 선수과목 뒤에만 들을 수 있지만 서로 독립인 과목은 어느 학기에 먼저 배치해도 됩니다. BST의 ancestor가 선수과목이고 descendant가 후속 과목이며, left와 right subtree는 독립 트랙입니다.

선수과목을 먼저 수강
↔
ancestor-before-descendant
서로 독립인 전공 트랙 과목을 섞어 배치
↔
left/right subtree interleaving
선수과목 전에 후속 과목을 신청한 시간표
↔
invalid permutation

비유의 한계: 실제 수강에는 학기 수나 동시 수강 조건이 있지만 BST에는 오직 insertion 순서와 비교 path만 있습니다. 조합 개수는 설명용 심화이며 시험 문언의 필수 요구가 아닙니다.

dependency DAG와 대안 순서 재생

강제: 37 먼저root가 첫 key가 아니면 같은 tree가 될 수 없습니다.
강제: \(15\to 7,29 / 56\to 85\)15→7,29 / 56→85각 subtree의 parent가 descendants보다 먼저입니다.
자유: 왼쪽과 오른쪽 부분 트리 섞기15·7·29 작업과 56·85 작업의 상대 위치는 순서를 보존하며 끼워 넣을 수 있습니다.
대안: 37,56,15,85,29,7강제 화살표를 모두 지키면서 Preorder와 다른 한 줄 순서를 만듭니다.

DAG 화살표는 강제 관계이고 화살표가 없는 sibling·다른 subtree 사이는 자유입니다. 아래 대안 sequence를 한 칸씩 재생하면 원래 edge가 그대로 만들어집니다.

먼저 작은 예제로 연습 · 10-root tree의 두 대안 순서

root 10, left child 5, right child 20인 tree에서 [10,5,20] 외의 순서를 찾습니다.

10을 먼저 고정

root dependency는 자유가 아니므로 두 valid sequence 모두 10으로 시작합니다.

10
right 20을 먼저 삽입

5와 20은 서로 ancestor가 아니어서 20을 5보다 먼저 넣어도 됩니다.

10,20
left 5 삽입

\(5<10\)5<10이라 10.left로 가며 이미 있는 right subtree 20의 구조에 영향을 주지 않습니다.

10,20,5

작은 예제의 결론: [10,20,5]도 같은 tree를 만들므로 Preorder는 안전한 한 답이지 유일한 history가 아닙니다.

이제 실제 시험 문제에 연결

다른 삽입 순서가 존재하는가?

네. tree가 모든 key 쌍의 순서를 강제하지 않고 ancestor 관계만 강제하므로 독립인 작업의 순서를 바꿀 수 있습니다.

어떤 관계는 절대로 바꿀 수 없는가?

37이 먼저이고, 15가 7과 29보다 먼저이며, 56이 85보다 먼저여야 합니다. 자손이 먼저 오면 그 키가 조상 자리를 차지해 트리 모양이 달라집니다.

대안 [37,56,15,85,29,7]은 왜 valid인가?

56은 37.right, 15는 37.left, 85는 56.right, 29는 15.right, 7은 15.left가 되어 모든 원래 edge를 재현합니다.

왜 모든 6! permutation이 가능한 것은 아닌가?

root와 ancestor dependency를 어기는 permutation은 중간 node가 먼저 빈 child를 차지합니다. 예를 들어 7이 15보다 먼저면 7이 37.left가 됩니다.

20개 계산은 어떻게 분리해 설명하는가?

필수 답은 대안 하나와 ancestor/interleaving 이유입니다. 선택 심화에서는 왼쪽 내부 순서 2개와 위치 \(\text{interleaving} C(5,3)=10\)interleaving C(5,3)=10을 곱해 20개를 얻습니다.

답이 맞는지 스스로 검산

  • 대안 순서를 빈 tree에 재생해 최종 edge가 \(37\to 15/56, 15\to 7/29, 56\to 85\)37→15/56, 15→7/29, 56→85인지 확인합니다.
  • 대안 sequence 안에서 모든 dependency 화살표의 출발 key가 도착 key보다 앞에 있는지 검사합니다.
  • 선택 심화 개수는 root 37을 고정해 5!가 아니라는 점과 2×\(C(5,3)=20\)C(5,3)=20계산을 구분합니다.

30초 자가점검

[37,7,15,29,56,85]가 왜 실패하는가?

힌트: 7이 삽입될 때 37.left가 비어 있는지 봅니다.

정답: 7이 15보다 먼저 37.left를 차지하고 15는 7.right가 되므로 원래 15-rooted left subtree와 달라집니다.

15와 56의 상대 순서는 강제되는가?

힌트: 둘이 서로 ancestor인지 확인합니다.

정답: 강제되지 않습니다. 둘은 root 37의 서로 다른 subtree root이므로 37 뒤에서는 어느 쪽을 먼저 삽입해도 됩니다.

마지막에 쓰는 시험 답안 틀

Ja. 예: [37,56,15,85,29,7]. Root 37은 먼저, 각 parent는 descendant보다 먼저 와야 하지만 서로 독립인 left/right subtree 원소는 interleave할 수 있으므로 다른 순서가 존재한다.

자주 하는 실수

근거와 정확성 범위

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

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