II-5 AVL·Red-Black·Heap의 포함 관계 — 완전 초보자 Masterclass
먼저 이 문제의 정체부터
세 구조에 모두 'tree'가 들어가도 지키는 규칙은 다릅니다. BST order, AVL height balance, red-black color rules, max-heap parent order를 각각 별도 체크박스로 봐야 합니다.
모두 제복을 입었어도 학교·소방서·병원의 규칙이 다른 것과 같습니다.
이 문항의 풀이 목표는 정답 label 암기가 아니라 다음 절차를 재현하는 것입니다. 구조마다 order rule과 balance rule을 두 칸으로 나누어 포함 방향을 검사합니다.
복기 시험지는 공식 답안지가 아니므로 문언과 selection rule이 충돌하면 그 사실을 표시하고 현재 강의 자료로 각 보기를 독립 검증합니다.
0. 필요한 개념을 처음부터 배우기
개념 1 · 문제의 정체를 생활 언어로
세 구조에 모두 'tree'가 들어가도 지키는 규칙은 다릅니다. BST order, AVL height balance, red-black color rules, max-heap parent order를 각각 별도 체크박스로 봐야 합니다.
이 문항에서 가장 먼저 붙잡을 문장은 '모든 red-black tree는 BST이다.'입니다. 용어를 외우기 전에 이 문장이 어떤 상황을 말하는지 작은 예를 만들어 확인합니다.
이 절에서 꼭 기억할 것
- 모든 red-black tree는 BST이다.
- 구조마다 order rule과 balance rule을 두 칸으로 나누어 포함 방향을 검사합니다.
개념 2 · 반드시 알아야 하는 네 개의 뼈대
첫째, 모든 red-black tree는 BST이다. 둘째, max-heap의 \(\text{parent}\ge \text{child}\)parent≥child는 BST의 \(\text{left}<\text{루트}<\text{right}\)left<root<right와 다르다.
셋째, red-black balance는 AVL보다 느슨해 모든 RB가 AVL인 것은 아니다. 넷째, AVL tree는 적절히 색칠해 red-black 조건을 만족시킬 수 있다는 강의 정리를 사용한다. 이 네 문장을 서로 섞지 않고 별도 체크박스로 기억해야 합니다.
이 절에서 꼭 기억할 것
- 모든 red-black tree는 BST이다.
- max-heap의 \(\text{parent}\ge \text{child}\)
parent≥child는 BST의 \(\text{left}<\text{루트}<\text{right}\)left<root<right와 다르다. - red-black balance는 AVL보다 느슨해 모든 RB가 AVL인 것은 아니다.
- AVL tree는 적절히 색칠해 red-black 조건을 만족시킬 수 있다는 강의 정리를 사용한다.
개념 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까지 각각 독립적인 참·거짓 명제로 바꾸고 근거 또는 반례를 붙인 뒤 참의 개수를 셉니다.
현재 복기 데이터에서 판정된 정답 표시는 B, D입니다. 정답 수와 섹션 규칙이 충돌하는 문항은 억지로 두 개를 만들지 않고 복기 문언 누락 가능성을 명시합니다.
수식으로 정확히 쓰기
핵심 규칙선택 규칙: 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
핵심 규칙검증된 선택지: B, D
이 절에서 꼭 기억할 것
- 색칠 가능성, BST order, AVL balance를 한 단어 'balanced tree'로 뭉개는 함정.
- RB는 BST다. Heap은 BST가 아니다. AVL은 RB로 색칠 가능하지만 RB가 항상 AVL은 아니다.
1. 시험장에서 따라 할 풀이 순서
선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
AVL·Red-Black·Heap의 포함 관계
모든 red-black tree는 BST이다. | max-heap의 \(\text{parent}\ge \text{child}\)parent≥child는 BST의 \(\text{left}<\text{루트}<\text{right}\)left<root<right와 다르다. | red-black balance는 AVL보다 느슨해 모든 RB가 AVL인 것은 아니다.
선택지 \(A =\)A =거짓
선택 규칙을 먼저 적는다
이 문항의 규칙은 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))입니다. 마지막에 참 개수를 반드시 재검산합니다.핵심 규칙선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))문장을 쉬운 한국어로 다시 쓴다
고급 자료구조 사이의 동치 또는 포함 관계에 대해 옳은 설명 두 개를 고르시오.
핵심 규칙AVL·Red-Black·Heap의 포함 관계
핵심 도구를 종이에 꺼낸다
구조마다 order rule과 balance rule을 두 칸으로 나누어 포함 방향을 검사합니다.
핵심 규칙모든 red-black tree는 BST이다. | max-heap의 \(\text{parent}\ge \text{child}\)
parent≥child는 BST의 \(\text{left}<\text{루트}<\text{right}\)left<root<right와 다르다. | red-black balance는 AVL보다 느슨해 모든 RB가 AVL인 것은 아니다.선택지 A를 독립 판정한다
Red-black tree는 정의상 BST여야 한다. Max-heap은 \(\text{parent} \ge \text{child}\)
parent ≥ child만 요구하고 왼쪽/오른쪽 subtree의 BST order를 요구하지 않는다. 색칠은 key order를 고치지 못하므로 일반적으로 false다.\[선택지 A = 거짓\]선택지 A = 거짓선택지 B를 독립 판정한다
강의 정의가 바로 'Ein Rot-Schwarz-Baum ist ein binärer Suchbaum, so dass gilt ...'로 시작한다. 색 규칙은 BST 위에 추가되는 조건이다.
\[선택지 B = 참\]선택지 B = 참선택지 C를 독립 판정한다
거짓이다. 레드-블랙 균형(red-black balance)은 AVL 균형보다 약하다. 강의는 AVL과 레드-블랙 트리가 같지 않으며, 높이 차이가 2인 유효한 레드-블랙 트리가 AVL 조건을 어길 수 있음을 보여 준다.
\[선택지 C = 거짓\]선택지 C = 거짓선택지 D를 독립 판정한다
강의와 Sheet06 공식 풀이가 AVL subset RB를 다룬다. 즉 AVL shape는 적절한 red/black coloring으로 RB 조건을 만족시킬 수 있다.
\[선택지 D = 참\]선택지 D = 참정답 수와 애매성을 재검산한다
참으로 판정된 선택지는 B, D입니다. 복기 섹션 규칙과 수가 다르면 원문 누락 가능성을 기록하고 거짓을 참으로 조작하지 않습니다.
\[검증된 정답 = B, D\]검증된 정답 = B, D
2. 이 문제를 실제로 끝까지 풀기
세 구조에 모두 'tree'가 들어가도 지키는 규칙은 다릅니다. BST order, AVL height balance, red-black color rules, max-heap parent order를 각각 별도 체크박스로 봐야 합니다.
풀이를 시작할 때 다음 네 사실을 먼저 적습니다. (1) 모든 red-black tree는 BST이다. (2) max-heap의 \(\text{parent}\ge \text{child}\)parent≥child는 BST의 \(\text{left}<\text{루트}<\text{right}\)left<root<right와 다르다. (3) red-black balance는 AVL보다 느슨해 모든 RB가 AVL인 것은 아니다. (4) AVL tree는 적절히 색칠해 red-black 조건을 만족시킬 수 있다는 강의 정리를 사용한다.
선택지 A는 거짓입니다. Red-black tree는 정의상 BST여야 한다. Max-heap은 \(\text{parent} \ge \text{child}\)parent ≥ child만 요구하고 왼쪽/오른쪽 subtree의 BST order를 요구하지 않는다. 색칠은 key order를 고치지 못하므로 일반적으로 false다. 가장 작은 확인 예는 루트가 9, 왼쪽 자식이 8, 오른쪽 자식이 7인 트리는 올바른 최대 힙이지만, 오른쪽 자식 7이 9보다 작으므로 BST 순서를 위반한다.
선택지 B는 참입니다. 강의 정의가 바로 'Ein Rot-Schwarz-Baum ist ein binärer Suchbaum, so dass gilt ...'로 시작한다. 색 규칙은 BST 위에 추가되는 조건이다.
선택지 C는 거짓입니다. 거짓이다. 레드-블랙 균형(red-black balance)은 AVL 균형보다 약하다. 강의는 AVL과 레드-블랙 트리가 같지 않으며, 높이 차이가 2인 유효한 레드-블랙 트리가 AVL 조건을 어길 수 있음을 보여 준다. 가장 작은 확인 예는 어떤 국소 부분트리의 높이 차가 2인 올바른 레드-블랙 트리는 레드-블랙 규칙상 허용되지만 AVL 조건은 위반한다.
선택지 D는 참입니다. 강의와 Sheet06 공식 풀이가 AVL subset RB를 다룬다. 즉 AVL shape는 적절한 red/black coloring으로 RB 조건을 만족시킬 수 있다.
따라서 현재 문언에서 참으로 검증된 선택지는 B, D입니다. 선택지는 서로 상대평가하지 않고 각 문장을 정의·전제·반례로 독립 검증했습니다.
시험장에서 쓸 압축 절차는 다음과 같습니다. 구조마다 order rule과 balance rule을 두 칸으로 나누어 포함 방향을 검사합니다. 시간이 부족해도 '항상(always)', '오직(only)', '모든(every)' 같은 강한 단어와 전제조건, O와 Θ를 먼저 확인하면 대표 함정을 피할 수 있습니다.
3. 선택지 A–D를 한 줄도 건너뛰지 않고 판정하기
-
A거짓
Red-black tree는 정의상 BST여야 한다. Max-heap은 \(\text{parent} \ge \text{child}\)
parent ≥ child만 요구하고 왼쪽/오른쪽 subtree의 BST order를 요구하지 않는다. 색칠은 key order를 고치지 못하므로 일반적으로 false다.빠른 확인법: 루트가 9, 왼쪽 자식이 8, 오른쪽 자식이 7인 트리는 올바른 최대 힙이지만, 오른쪽 자식 7이 9보다 작으므로 BST 순서를 위반한다.
-
B참 — 정답 후보
강의 정의가 바로 'Ein Rot-Schwarz-Baum ist ein binärer Suchbaum, so dass gilt ...'로 시작한다. 색 규칙은 BST 위에 추가되는 조건이다.
빠른 확인법: 모든 red-black tree는 binary search tree이다.
-
C거짓
거짓이다. 레드-블랙 균형(red-black balance)은 AVL 균형보다 약하다. 강의는 AVL과 레드-블랙 트리가 같지 않으며, 높이 차이가 2인 유효한 레드-블랙 트리가 AVL 조건을 어길 수 있음을 보여 준다.
빠른 확인법: 어떤 국소 부분트리의 높이 차가 2인 올바른 레드-블랙 트리는 레드-블랙 규칙상 허용되지만 AVL 조건은 위반한다.
-
D참 — 정답 후보
강의와 Sheet06 공식 풀이가 AVL subset RB를 다룬다. 즉 AVL shape는 적절한 red/black coloring으로 RB 조건을 만족시킬 수 있다.
빠른 확인법: 모든 AVL tree는 red-black tree가 되도록 색칠할 수 있다.
4. 초보자가 가장 자주 틀리는 이유
- 색칠 가능성, BST order, AVL balance를 한 단어 'balanced tree'로 뭉개는 함정.
- exactly-two라는 이유만으로 근거 없이 두 선택지를 맞다고 만든다.
- 선택지의 절반만 맞는데 결합 문장 전체를 참으로 판정한다.
- always, only, every 같은 강한 단어를 놓친다.
- 정의와 구현, 전제조건과 결론, upper bound와 tight bound를 섞는다.
- 작은 예 하나로 거짓은 깰 수 있지만 참인 보편 명제를 증명했다고 착각한다.
- 복기 시험지가 공식 원문·공식 답안이라는 전제로 애매성을 숨긴다.
- 용어를 암기한 소리만 따라가고 실제 상태나 한 단계 실행을 그리지 않는다.
5. 시험 답안 템플릿
구조마다 order rule과 balance rule을 두 칸으로 나누어 포함 방향을 검사합니다. 각 선택지를 정의와 전제에 따라 독립 판정하면 참인 label은 B, D이다. 핵심 근거: 모든 red-black tree는 BST이다. max-heap의 \(\text{parent}\ge \text{child}\)parent≥child는 BST의 \(\text{left}<\text{루트}<\text{right}\)left<root<right와 다르다. red-black balance는 AVL보다 느슨해 모든 RB가 AVL인 것은 아니다. AVL tree는 적절히 색칠해 red-black 조건을 만족시킬 수 있다는 강의 정리를 사용한다.
6. 스스로 이해했는지 확인
II-5의 주제를 한 문장으로 설명하면?
정답: 세 구조에 모두 'tree'가 들어가도 지키는 규칙은 다릅니다. BST order, AVL height balance, red-black color rules, max-heap parent order를 각각 별도 체크박스로 봐야 합니다.
이 문제에서 가장 먼저 꺼낼 판정법은?
정답: 구조마다 order rule과 balance rule을 두 칸으로 나누어 포함 방향을 검사합니다.
핵심 사실 네 가지 중 첫 번째는?
정답: 모든 red-black tree는 BST이다.
핵심 사실 네 가지 중 두 번째는?
정답: max-heap의 \(\text{parent}\ge \text{child}\)parent≥child는 BST의 \(\text{left}<\text{루트}<\text{right}\)left<root<right와 다르다.
가장 위험한 함정은?
정답: 색칠 가능성, BST order, AVL balance를 한 단어 'balanced tree'로 뭉개는 함정.
정답 label은?
정답: B, D
레드-블랙 트리(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-5
복기된 문언과 선택지; 공식 답안지가 아님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 회전 경우를 뒷받침한다.