II-7 Binary Max-Heap의 세 가지 invariant — 완전 초보자 Masterclass
먼저 이 문제의 정체부터
Max-heap은 전체 정렬 트리가 아닙니다. 완전 이진 트리 모양과 \(\text{parent}\ge \text{children}\)parent≥children이라는 국소 규칙만 지키며, 그 결과 최댓값 하나만 root에 보장됩니다.
토너먼트 우승자는 맨 위에 있지만 아래 참가자 전체 순위는 정해지지 않은 대진표입니다.
이 문항의 풀이 목표는 정답 label 암기가 아니라 다음 절차를 재현하는 것입니다. \(\text{루트} \text{maximum}, \text{complete} \text{shape}, \text{parent}\ge \text{child}\)root maximum, complete shape, parent≥child를 적고 delete-max 절차를 시뮬레이션합니다.
복기 시험지는 공식 답안지가 아니므로 문언과 selection rule이 충돌하면 그 사실을 표시하고 현재 강의 자료로 각 보기를 독립 검증합니다.
0. 필요한 개념을 처음부터 배우기
개념 1 · 문제의 정체를 생활 언어로
Max-heap은 전체 정렬 트리가 아닙니다. 완전 이진 트리 모양과 \(\text{parent}\ge \text{children}\)parent≥children이라는 국소 규칙만 지키며, 그 결과 최댓값 하나만 root에 보장됩니다.
이 문항에서 가장 먼저 붙잡을 문장은 'root는 최대 원소다.'입니다. 용어를 외우기 전에 이 문장이 어떤 상황을 말하는지 작은 예를 만들어 확인합니다.
이 절에서 꼭 기억할 것
- root는 최대 원소다.
- \(\text{루트} \text{maximum}, \text{complete} \text{shape}, \text{parent}\ge \text{child}\)
root maximum, complete shape, parent≥child를 적고 delete-max 절차를 시뮬레이션합니다.
개념 2 · 반드시 알아야 하는 네 개의 뼈대
첫째, root는 최대 원소다. 둘째, heap order는 BST order가 아니다.
셋째, delete-max 후 마지막 node를 root로 옮겨 complete shape를 보존한다. 넷째, heapify-down은 parent-child 위반을 아래로 내려가며 고친다. 이 네 문장을 서로 섞지 않고 별도 체크박스로 기억해야 합니다.
이 절에서 꼭 기억할 것
- root는 최대 원소다.
- heap order는 BST order가 아니다.
- delete-max 후 마지막 node를 root로 옮겨 complete shape를 보존한다.
- heapify-down은 parent-child 위반을 아래로 내려가며 고친다.
개념 3 · 강의 정의를 초보자 언어로 해체
이 세 문항의 핵심은 '비슷하게 생긴 이진트리'를 같은 것으로 착각하지 않는 것이다. BST는 좌우 키 순서를 지키는 검색 구조이고, AVL과 레드-블랙 트리(red-black tree)는 BST의 높이를 \(O(\log n)\)O(log n)으로 제한하는 균형 규칙을 추가한다. 힙(heap)은 최댓값을 빨리 꺼내기 위한 우선순위 큐(priority queue) 구현이므로 좌우 전체 정렬을 요구하지 않는다.
이진 탐색 트리(Binary Search Tree, binärer Suchbaum)는 모든 노드 z에서 왼쪽 부분 트리의 키가 z.key 이하이고 오른쪽 부분 트리의 키가 z.key 이상인 구조다. 레드-블랙 트리(red-black tree, Rot-Schwarz-Baum)는 BST에 노드 색, 검은 루트, 적색 노드 연속 금지, 동일한 흑색 높이 규칙을 추가한다. AVL 트리(AVL tree, AVL-Baum)는 BST이며 모든 노드 x에서 '오른쪽 높이 - 왼쪽 높이'인 균형 인수(balance factor) B(x)가 -1, 0, +1 중 하나다. 이진 최대 힙(binary max-heap)은 거의 완전한 이진트리이며 루트가 아닌 모든 x에서 \(\text{parent}.\text{key} \ge x.\text{key}\)parent.key ≥ x.key를 만족한다.
수식으로 정확히 쓰기
핵심 규칙BST 연산은 \(O(h)\)O(h)이다. AVL·RB 트리는 \(h = O(\log n)\)h = O(log n)을 유지한다. AVL은 \(B(x) \in \{-1, 0, +1\}, \text{RB}\)B(x) ∈ {-1, 0, +1}, RB트리는 적색 노드 연속 금지(no red-red)와 동일한 흑색 높이(equal black-height)를 지킨다. 최대 힙의 루트는 최댓값이며 삽입·최댓값 추출은 \(O(\log n)\)O(log n)이다.
이 절에서 꼭 기억할 것
- BST 키 순서를 먼저 검사한다. AVL·RB는 모두 BST 계열이므로 BST 순서가 깨지면 바로 탈락한다.
- 회전(rotation)은 키 순서를 바꾸지 않는다. 바뀌는 것은 부모·자식 모양(parent-child shape)이다.
- 힙(heap)의 왼쪽 자식과 오른쪽 자식 사이에는 정렬 관계가 없다.
개념 4 · 성립 조건·불변식·경계 사례
회전(rotation)은 중위 순회 키 순서를 보존한다. 즉 \(A < x < B < y < C\)A < x < B < y < C와 같은 순서가 회전 전후에 유지된다. 레드-블랙 트리의 높이는 \(O(\log n)\)O(log n)이고 강의의 상한은 \(h \le 2 \log_{2}(n+1)\)h ≤ 2 log₂(n+1)이다. AVL 트리의 높이도 \(O(\log n)\)O(log n)이며 강의 상한은 \(h \le 1.441 \log_{2} n\)h ≤ 1.441 log₂ n이다. 힙은 맨 아래 층을 제외하면 완전 이진트리이므로 높이가 \(O(\log n)\)O(log n)이다.
루트 9와 자식 8, 7로 이루어진 올바른 최대 힙은 오른쪽 자식 7이 루트보다 작으므로 BST가 아니다. 레드-블랙 트리는 AVL 균형을 만족하지 않아도 유효할 수 있으며 강의도 \(\text{AVL} \ne \text{Rot}-\text{Schwarz}\)AVL != Rot-Schwarz를 명시한다. Sheet06의 관계에서는 모든 AVL 트리를 레드-블랙으로 색칠할 수 있지만, 이는 BST 모양의 색칠 가능성에 관한 명제이지 힙에 관한 명제가 아니다. 일반 BST 삽입은 탐색 후 리프를 붙이므로 자기 균형 변형을 쓰지 않는다면 rotateLeft나 rotateRight가 필요하지 않다.
이 절에서 꼭 기억할 것
- 전제조건을 생략하지 않는다.
- 존재 명제와 모든 경우 명제를 구분한다.
- 강한 단어는 작은 반례로 우선 검사한다.
개념 5 · 실행시간과 비용을 읽는 법
일반 BST의 탐색·삽입·삭제 비용은 \(O(h)\)O(h)이며 최악의 경우 h는 n이 될 수 있다. 강의 요약에서 AVL·레드-블랙 트리의 탐색·삽입·삭제는 \(\Theta(\log n)\)Θ(log n)이다. 스플레이 연산(splay operation)은 회전을 사용하며 한 번의 연산은 \(O(h)\)O(h), 연속 연산의 분할 상환 비용(amortized cost)은 \(O(\log n)\)O(log n)이다. 최대 힙의 삽입·최댓값 추출은 교환·힙 정리(swap/heapify)를 사용해 \(O(\log n)\)O(log n)에 실행되고 최댓값 읽기는 \(O(1)\)O(1)이다.
O는 upper bound이고 Θ는 tight bound입니다. 자료구조 연산 비용은 ADT 이름만이 아니라 구현과 유지하는 보조 정보에 따라 달라질 수 있습니다.
이 절에서 꼭 기억할 것
- O와 Θ를 같은 뜻으로 읽지 않는다.
- 구현 의존성을 확인한다.
- 필요 없는 runtime 주장도 억지로 만들지 않는다.
개념 6 · 정확히 두 개 선택(exactly two) 판정법
선택지를 서로 비교해 '가장 그럴듯한 두 개'를 고르지 않습니다. A부터 D까지 각각 독립적인 참·거짓 명제로 바꾸고 근거 또는 반례를 붙인 뒤 참의 개수를 셉니다.
현재 복기 데이터에서 판정된 정답 표시는 A, C입니다. 정답 수와 섹션 규칙이 충돌하는 문항은 억지로 두 개를 만들지 않고 복기 문언 누락 가능성을 명시합니다.
수식으로 정확히 쓰기
핵심 규칙선택 규칙: 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
핵심 규칙검증된 선택지: A, C
이 절에서 꼭 기억할 것
- Heap을 sorted tree로 착각하거나 max-heap과 min-heap의 방향을 바꾸는 함정.
- 최대 힙은 루트가 최댓값이고 거의 완전한 모양과 \(\text{parent} \ge \text{child}\)
parent ≥ child를 지킨다. 최댓값 삭제는 마지막 노드를 루트로 옮긴 뒤 아래로 힙 정리(heapify down)한다.
1. 시험장에서 따라 할 풀이 순서
선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
Binary Max-Heap의 세 가지 invariant
root는 최대 원소다. | heap order는 BST order가 아니다. | delete-max 후 마지막 node를 root로 옮겨 complete shape를 보존한다.
선택지 \(A =\)A =참
선택 규칙을 먼저 적는다
이 문항의 규칙은 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))입니다. 마지막에 참 개수를 반드시 재검산합니다.핵심 규칙선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))문장을 쉬운 한국어로 다시 쓴다
이진 max-heap에 대해 옳은 설명 두 개를 고르시오.
핵심 규칙Binary Max-Heap의 세 가지 invariant
핵심 도구를 종이에 꺼낸다
\(\text{루트} \text{maximum}, \text{complete} \text{shape}, \text{parent}\ge \text{child}\)
root maximum, complete shape, parent≥child를 적고 delete-max 절차를 시뮬레이션합니다.핵심 규칙root는 최대 원소다. | heap order는 BST order가 아니다. | delete-max 후 마지막 node를 root로 옮겨 complete shape를 보존한다.
선택지 A를 독립 판정한다
모든 parent가 child 이상이라는 heap order 때문에 어떤 path를 따라가도 root보다 큰 값이 아래에 있을 수 없다. 강의도 maximum is at the root라고 명시한다.
\[선택지 A = 참\]선택지 A = 참선택지 B를 독립 판정한다
Heap은 parent-child priority만 보장한다. 강의는 heaps are not BSTs라고 직접 경고한다. 오른쪽 child가 root보다 작아도 max-heap에서는 정상일 수 있지만 BST에서는 root의 오른쪽 subtree 값은 root 이상이어야 한다.
\[선택지 B = 거짓\]선택지 B = 거짓선택지 C를 독립 판정한다
마지막 leaf를 root로 옮기면 complete-tree shape가 유지된다. 그 다음 heapify가 parent-child max property를 아래로 내려가며 복구하므로 다시 max-heap이 된다.
\[선택지 C = 참\]선택지 C = 참선택지 D를 독립 판정한다
Max-heap에서는 큰 값이 위로 올라간다. 가장 큰 값은 root에 있어야 하며, leaves에는 작은 값들이 있을 수 있다.
\[선택지 D = 거짓\]선택지 D = 거짓정답 수와 애매성을 재검산한다
참으로 판정된 선택지는 A, C입니다. 복기 섹션 규칙과 수가 다르면 원문 누락 가능성을 기록하고 거짓을 참으로 조작하지 않습니다.
\[검증된 정답 = A, C\]검증된 정답 = A, C
2. 이 문제를 실제로 끝까지 풀기
Max-heap은 전체 정렬 트리가 아닙니다. 완전 이진 트리 모양과 \(\text{parent}\ge \text{children}\)parent≥children이라는 국소 규칙만 지키며, 그 결과 최댓값 하나만 root에 보장됩니다.
풀이를 시작할 때 다음 네 사실을 먼저 적습니다. (1) root는 최대 원소다. (2) heap order는 BST order가 아니다. (3) delete-max 후 마지막 node를 root로 옮겨 complete shape를 보존한다. (4) heapify-down은 parent-child 위반을 아래로 내려가며 고친다.
선택지 A는 참입니다. 모든 parent가 child 이상이라는 heap order 때문에 어떤 path를 따라가도 root보다 큰 값이 아래에 있을 수 없다. 강의도 maximum is at the root라고 명시한다.
선택지 B는 거짓입니다. Heap은 parent-child priority만 보장한다. 강의는 heaps are not BSTs라고 직접 경고한다. 오른쪽 child가 root보다 작아도 max-heap에서는 정상일 수 있지만 BST에서는 root의 오른쪽 subtree 값은 root 이상이어야 한다. 가장 작은 확인 예는 루트가 9이고 자식이 8과 7인 트리는 올바른 최대 힙이지만, 오른쪽 자식 7이 BST 조건을 위반한다.
선택지 C는 참입니다. 마지막 leaf를 root로 옮기면 complete-tree shape가 유지된다. 그 다음 heapify가 parent-child max property를 아래로 내려가며 복구하므로 다시 max-heap이 된다.
선택지 D는 거짓입니다. Max-heap에서는 큰 값이 위로 올라간다. 가장 큰 값은 root에 있어야 하며, leaves에는 작은 값들이 있을 수 있다. 가장 작은 확인 예는 힙 [9, 8, 7]의 잎은 8과 7이지만 최댓값 9는 루트에 있다.
따라서 현재 문언에서 참으로 검증된 선택지는 A, C입니다. 선택지는 서로 상대평가하지 않고 각 문장을 정의·전제·반례로 독립 검증했습니다.
시험장에서 쓸 압축 절차는 다음과 같습니다. \(\text{루트} \text{maximum}, \text{complete} \text{shape}, \text{parent}\ge \text{child}\)root maximum, complete shape, parent≥child를 적고 delete-max 절차를 시뮬레이션합니다. 시간이 부족해도 '항상(always)', '오직(only)', '모든(every)' 같은 강한 단어와 전제조건, O와 Θ를 먼저 확인하면 대표 함정을 피할 수 있습니다.
3. 선택지 A–D를 한 줄도 건너뛰지 않고 판정하기
-
A참 — 정답 후보
모든 parent가 child 이상이라는 heap order 때문에 어떤 path를 따라가도 root보다 큰 값이 아래에 있을 수 없다. 강의도 maximum is at the root라고 명시한다.
빠른 확인법: 가장 큰 원소는 root에 있다.
-
B거짓
Heap은 parent-child priority만 보장한다. 강의는 heaps are not BSTs라고 직접 경고한다. 오른쪽 child가 root보다 작아도 max-heap에서는 정상일 수 있지만 BST에서는 root의 오른쪽 subtree 값은 root 이상이어야 한다.
빠른 확인법: 루트가 9이고 자식이 8과 7인 트리는 올바른 최대 힙이지만, 오른쪽 자식 7이 BST 조건을 위반한다.
-
C참 — 정답 후보
마지막 leaf를 root로 옮기면 complete-tree shape가 유지된다. 그 다음 heapify가 parent-child max property를 아래로 내려가며 복구하므로 다시 max-heap이 된다.
빠른 확인법: 이진 max-heap에서 최대 원소를 지운 뒤 마지막 node를 root로 옮기고 heapify를 수행하면 다시 이진 max-heap이 된다.
-
D거짓
Max-heap에서는 큰 값이 위로 올라간다. 가장 큰 값은 root에 있어야 하며, leaves에는 작은 값들이 있을 수 있다.
빠른 확인법: 힙 [9, 8, 7]의 잎은 8과 7이지만 최댓값 9는 루트에 있다.
4. 초보자가 가장 자주 틀리는 이유
- Heap을 sorted tree로 착각하거나 max-heap과 min-heap의 방향을 바꾸는 함정.
- exactly-two라는 이유만으로 근거 없이 두 선택지를 맞다고 만든다.
- 선택지의 절반만 맞는데 결합 문장 전체를 참으로 판정한다.
- always, only, every 같은 강한 단어를 놓친다.
- 정의와 구현, 전제조건과 결론, upper bound와 tight bound를 섞는다.
- 작은 예 하나로 거짓은 깰 수 있지만 참인 보편 명제를 증명했다고 착각한다.
- 복기 시험지가 공식 원문·공식 답안이라는 전제로 애매성을 숨긴다.
- 용어를 암기한 소리만 따라가고 실제 상태나 한 단계 실행을 그리지 않는다.
5. 시험 답안 템플릿
\(\text{루트} \text{maximum}, \text{complete} \text{shape}, \text{parent}\ge \text{child}\)root maximum, complete shape, parent≥child를 적고 delete-max 절차를 시뮬레이션합니다. 각 선택지를 정의와 전제에 따라 독립 판정하면 참인 label은 A, C이다. 핵심 근거: root는 최대 원소다. heap order는 BST order가 아니다. delete-max 후 마지막 node를 root로 옮겨 complete shape를 보존한다. heapify-down은 parent-child 위반을 아래로 내려가며 고친다.
6. 스스로 이해했는지 확인
II-7의 주제를 한 문장으로 설명하면?
정답: Max-heap은 전체 정렬 트리가 아닙니다. 완전 이진 트리 모양과 \(\text{parent}\ge \text{children}\)parent≥children이라는 국소 규칙만 지키며, 그 결과 최댓값 하나만 root에 보장됩니다.
이 문제에서 가장 먼저 꺼낼 판정법은?
정답: \(\text{루트} \text{maximum}, \text{complete} \text{shape}, \text{parent}\ge \text{child}\)root maximum, complete shape, parent≥child를 적고 delete-max 절차를 시뮬레이션합니다.
핵심 사실 네 가지 중 첫 번째는?
정답: root는 최대 원소다.
핵심 사실 네 가지 중 두 번째는?
정답: heap order는 BST order가 아니다.
가장 위험한 함정은?
정답: Heap을 sorted tree로 착각하거나 max-heap과 min-heap의 방향을 바꾸는 함정.
정답 label은?
정답: A, C
레드-블랙 트리(red-black tree)가 단순히 색칠된 트리가 아니라 무엇 위에 색 규칙을 얹은 구조인지 말하라.
정답: 레드-블랙 트리는 이진 탐색 트리(binary search tree) 위에 적색·흑색 색상, 검은 루트, 적색 노드 연속 금지(no red-red), 동일한 흑색 높이(equal black-height) 규칙을 추가한 구조다.
왜 최대 힙(max-heap) [9, 8, 7]은 BST가 아닌가?
정답: 오른쪽 자식 7이 루트 9보다 작으므로 BST의 '오른쪽 부분 트리 키 >= 루트' 조건을 위반한다. 하지만 부모 >= 자식이므로 최대 힙은 맞다.
근거 자료
AuD Gedächtnisprotokoll SoSe 2025.md· Multiple Choice II-7
복기된 문언과 선택지; 공식 답안지가 아님AuD Gedächtnisprotokoll SoSe 2025.md· MC section II, questions 5-7
SoSe 2025 복기 자료의 세 객관식 문항 문구, 배점, 정확히 2개 선택 규칙을 뒷받침한다.Vorlesung\03BasicDataStructures.pdf· pp. 66, 69, 71
BST 순서 정의, BST 탐색 경계 \(O(h)\)O(h), 회전 없이 탐색 경로를 따라가는 일반 BST 삽입을 뒷받침한다.Vorlesung\04AdvancedDataStructures.pdf· pp. 2-6, 12-18, 24-29
레드-블랙 트리는 색, 루트, 연속된 빨강 금지, 검은 높이 규칙을 갖는 BST이며, 회전은 레드-블랙 복구에 쓰는 상수 시간 포인터 변경이라는 내용을 뒷받침한다.Vorlesung\04AdvancedDataStructures.pdf· pp. 45-55, 59-69
AVL 정의, 균형 인수 관례, AVL 높이 경계, AVL 트리의 레드-블랙 색칠 가능성, 레드-블랙 트리가 반드시 AVL은 아니라는 사실, AVL 회전 경우를 뒷받침한다.