5. Grundlegende Datenstrukturen (7 Punkte)
선행지식이 전혀 없어도 이 페이지 하나에서 용어를 배우고, 작은 예제를 거쳐 실제 시험 풀이와 검산까지 따라가도록 구성했습니다.
시험 문언과 숫자·배점은 비공식 복기 자료 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 삽입은 root부터 한 번의 search path를 따라 nil 자리를 찾는 과정입니다. 새 key가 현재 node보다 작으면 왼쪽, 크면 오른쪽으로 갑니다.
두 값을 'nacheinander(차례로)' 넣으므로 60은 23이 들어간 결과에서 시작합니다. 다만 두 search path가 서로 다른 가지라 23이 60의 위치에는 영향을 주지 않습니다.
각 삽입 뒤 트리를 따로 그려야 2점의 단계 점수를 지킬 수 있습니다.
모든 노드 z에서 왼쪽 부분 트리의 키≤\(z.\text{key}\le \)z.key≤오른쪽 부분 트리의 키입니다. 서로 다른 키만 있다면 엄격한 부등호 <와 >로 생각해도 됩니다.
삽입은 이 비교가 안내하는 한 경로만 내려가므로 다른 부분 트리를 탐색할 필요가 없습니다.
핵심 규칙\(k<x.\)k<x.\mathrm{key}\;\Longrightarrow\;x\leftarrow x.\mathrm{left}
핵심 규칙\(k>x.\)k>x.\mathrm{key}\;\Longrightarrow\;x\leftarrow x.\mathrm{right}
\(23<37\)23<37이므로 15로, \(23>15\)23>15이므로 29로, \(23<29\)23<29이므로 왼쪽 빈 자리(nil)로 갑니다. 따라서 23은 29의 왼쪽 자식입니다.
중간 비교값 [37,15,29]를 답안 옆에 쓰면 위치가 우연이 아니라 알고리즘 결과임을 보여 줍니다.
핵심 규칙37\xrightarrow{L}15\xrightarrow{R}29\xrightarrow{L}\varnothing
29.\mathrm{left}=23\(60>37\)60>37이므로 56으로, \(60>56\)60>56이므로 85로, \(60<85\)60<85이므로 왼쪽 빈 자리로 갑니다. 따라서 60은 85의 왼쪽 자식입니다.
60은 56보다 크면서 85보다 작으므로 이 위치가 정확히 이진 탐색 트리의 범위 조건을 만족합니다.
핵심 규칙37\xrightarrow{R}56\xrightarrow{R}85\xrightarrow{L}\varnothing
85.\mathrm{left}=60삽입은 루트에서 잎(leaf)까지 한 경로만 보므로 \(O(h)\)O(h)입니다. 이 트리에서는 비교 횟수가 작지만 일반 이진 탐색 트리는 한쪽 사슬이 되어 \(h=n-1\)h=n-1일 수 있습니다.
균형 트리라면 \(h=\Theta(\log n)\)h=Θ(log n)이지만 일반 이진 탐색 트리가 자동으로 균형을 맞추지는 않습니다.
T_{\text{삽입}}(h)=O(h)h=\Θ(\log n)\ \text{(균형)},\qquad h=\Θ(n)\ \text{(편향)}BST insertion은 새 값을 아무 빈 곳에 붙이는 그림 문제가 아니라, search가 실패한 정확한 nil 자리를 찾는 알고리즘입니다. 비교 한 번마다 반대쪽 subtree 전체를 버리는 이유를 이해하면 위치를 외우지 않고 재현할 수 있습니다.
어떤 노드 하나만이 아니라 그 노드의 왼쪽 부분 트리 전체가 더 작고 오른쪽 부분 트리 전체가 더 커야 한다는 약속입니다. 이 전역 약속 때문에 한 비교로 반대쪽을 버릴 수 있습니다.
23<29이면 29의 오른쪽 부분 트리는 모두 29보다 커서 23의 후보가 아닙니다.삽입은 루트에서 검색과 같은 비교를 반복하다가 자식이 없는 nil 방향을 처음 만난 곳에 새 잎을 연결합니다. 기존 노드나 간선을 덮어쓰지 않습니다.
29.left=nil에서 멈추면 새 노드 23이 바로 29.left가 됩니다.두 값을 차례로 넣으라는 말은 첫 번째 결과 tree가 두 번째 입력 상태가 된다는 뜻입니다. 각 삽입 뒤의 그림이 채점 대상입니다.
각 node를 번호가 적힌 갈림길로 생각합니다. 새 번호가 표지판보다 작으면 왼쪽 복도, 크면 오른쪽 복도로 가며, 처음 만난 빈 방 nil에 입주합니다. 이미 사람이 있는 방이나 복도 중간을 밀어내지는 않습니다.
비유의 한계: 실제 건물에서는 지름길이나 방 재배치가 가능하지만 plain BST insertion은 한 root-to-nil path만 따르고 자동 rotation이나 균형 조정을 하지 않습니다.
23<37 → L허용 상한이 37이 되고 15로 이동합니다.23>15 → R허용 구간이 (15,37)로 좁아지고 29로 이동합니다.23<29 → 왼쪽 빈 자리(nil)최종 구간 (15,29)에 23이 들어가 29.left가 됩니다.표의 한 행이 tree 위의 화살표 하나와 대응합니다. 녹색 끝 node는 새로 삽입된 key이며, 기존 node와 edge는 그대로 유지됩니다.
root 10의 left child가 5이고 다른 child가 모두 nil인 작은 tree에 key 7을 넣습니다.
\(7<10\)7<10이므로 BST invariant상 7이 있다면 left subtree에만 있을 수 있습니다.
10 --L→ 5\(7>5\)7>5이므로 5의 right subtree로 가야 하며 반대쪽 left는 후보가 아닙니다.
5 --R→ nil5.right가 첫 nil이므로 기존 edge를 바꾸지 않고 새 leaf 7을 붙입니다.
\(5.\text{right}=7\)5.right=7작은 예제의 결론: 삽입 위치는 숫자의 전체 정렬 위치를 눈대중으로 고르는 것이 아니라 root에서 시작한 실패 search path가 결정합니다.
\(23<37\)23<37이므로 37의 left child 15로 갑니다. 37의 right subtree는 모두 37보다 커서 버립니다.
\(23>15\)23>15라서 right 29, 이어 \(23<29\)23<29라서 left nil로 갑니다. 따라서 \(29.\text{left}=23\)29.left=23입니다.
23 삽입 후 tree에서 root 37부터 시작합니다. 두 path가 다른 가지라 결과 위치는 영향을 받지 않아도 중간 tree는 반드시 그립니다.
\(60>37, 60>56\)60>37, 60>56이지만 \(60<85\)60<85이므로 85의 left nil이 처음 만나는 빈 자리입니다. 기존 85를 덮어쓰지 않습니다.
새 node로 가는 edge 하나만 추가되고 기존 key, parent-child 관계, subtree 내부 순서는 모두 그대로입니다.
15<23<29이고 60의 범위는 \(56<60<85\)56<60<85이므로 두 새 node 위치가 BST invariant를 만족합니다.힌트: 그 자리에 이미 어떤 node가 있는지 확인합니다.
정답: 56.right에는 이미 85가 있으므로 search를 계속해야 합니다. \(60<85\)60<85라서 최종 위치는 85.left입니다.
힌트: AVL/RB와 plain BST를 구분합니다.
정답: 아닙니다. plain BST는 비교 path의 nil에 붙일 뿐이며 rotation은 AVL·Red-Black 같은 별도 균형 구조의 작업입니다.
23: 37에서 L, 15에서 R, 29에서 L이므로 \(29.\text{left}=23.\)29.left=23.그 트리를 먼저 그린다. 60: 37에서 R, 56에서 R, 85에서 L이므로 \(85.\text{left}=60.\)85.left=60.두 번째 트리를 그린다.
23>15인데 왼쪽으로 간다.복기 문언, 강의 정의, 공식 연습 풀이, 추가 유도를 구분해 표시합니다.
AuD Gedächtnisprotokoll SoSe 2025.md · lines 246-268 · 신뢰도/범위: 비공식 기억 복기5번의 sequence, 삽입·검색 key, 소문항 요구와 배점
정확한 시험 문언의 공식 공개본이 아니라 복기 자료이므로 강의 정의와 별도로 표시합니다.
Vorlesung\03BasicDataStructures.pdf · pp. 46-51 · 신뢰도/범위: 현재 강의 슬라이드binary tree·subtree·nil·height 용어와 Inorder/Preorder/Postorder 정의
Vorlesung\03BasicDataStructures.pdf · pp. 66-71 · 신뢰도/범위: 현재 강의 슬라이드BST invariant, unique-key BST의 Preorder 복원, Inorder 비유일성, search와 insertion
Vorlesung\03BasicDataStructures.pdf · pp. 80-81 · 신뢰도/범위: 현재 강의 슬라이드BST 연산 \(O(h)\)O(h), balanced와 degenerate height 차이
Übung\AuD26_Sheet05-GrpSol.pdf · pp. 7-10 · 신뢰도/범위: 공식 풀이BST insertion, traversal, reconstruction을 단계별로 그리는 현재 풀이 방식
Übung\AuD26_Sheet05-GrpSol.pdf · pp. 11-12 · 신뢰도/범위: 공식 풀이search path의 ancestor bound와 위반 경로 판정
마지막 생성: 2026-08-02 08:51