균형 탐색 트리, 회전, 이진 max-heap

II-6 · 기초 개념부터 실제 판정까지

과목을 처음 보는 학습자가 이 한 페이지만 읽고 용어, 수식, 판정 절차와 정답 근거를 설명할 수 있도록 구성했습니다.

비공식 시험 복기 문언

먼저 실제 문항을 읽기

Rotationen (d.h., Funktionen rotateLeft() und rotateRight()) in Bäumen:

한국어 번역: 트리에서 rotateLeft()와 rotateRight() 같은 rotation 함수에 대해 옳은 설명 두 개를 고르시오.

선택 규칙: 정확히 두 개를 고릅니다. 아래 개념 강의를 읽기 전에 머릿속으로 한 번 판단해 보세요.

선행지식 0 기준

II-6 회전(rotation)이 필요한 트리와 필요 없는 구조 — 완전 초보자 Masterclass

먼저 이 문제의 정체부터

Rotation은 모든 트리 삽입의 필수 동작이 아니라, BST 순서를 보존하면서 모양을 다시 잡는 도구입니다. 구조가 어떤 invariant를 복구해야 하는지부터 확인합니다.

책 순서는 유지한 채 기울어진 책장을 다시 세우는 작업입니다.

이 문항의 풀이 목표는 정답 label 암기가 아니라 다음 절차를 재현하는 것입니다. \(\text{Splay}=\)Splay=회전, \(\text{AVL}=\)AVL=회전, \(\text{plain} \text{BST}=\text{attach}, \text{heap}=\text{swap}\)plain BST=attach, heap=swap이라는 네 단어로 대응합니다.

복기 시험지는 공식 답안지가 아니므로 문언과 selection rule이 충돌하면 그 사실을 표시하고 현재 강의 자료로 각 보기를 독립 검증합니다.

0. 필요한 개념을 처음부터 배우기

개념 1
개념 1 · 문제의 정체를 생활 언어로

Rotation은 모든 트리 삽입의 필수 동작이 아니라, BST 순서를 보존하면서 모양을 다시 잡는 도구입니다. 구조가 어떤 invariant를 복구해야 하는지부터 확인합니다.

이 문항에서 가장 먼저 붙잡을 문장은 'Splay tree는 접근·삽입 후 rotation으로 노드를 위로 올린다.'입니다. 용어를 외우기 전에 이 문장이 어떤 상황을 말하는지 작은 예를 만들어 확인합니다.

이 절에서 꼭 기억할 것
  • Splay tree는 접근·삽입 후 rotation으로 노드를 위로 올린다.
  • \(\text{Splay}=\)Splay=회전, \(\text{AVL}=\)AVL=회전, \(\text{plain} \text{BST}=\text{attach}, \text{heap}=\text{swap}\)plain BST=attach, heap=swap이라는 네 단어로 대응합니다.
개념 2
개념 2 · 반드시 알아야 하는 네 개의 뼈대

첫째, Splay tree는 접근·삽입 후 rotation으로 노드를 위로 올린다. 둘째, AVL tree는 balance factor 위반을 rotation으로 복구한다.

셋째, plain BST는 leaf를 붙이기만 해도 삽입이 완료된다. 넷째, binary heap은 array의 마지막에 넣고 swap-up하며 tree rotation을 쓰지 않는다. 이 네 문장을 서로 섞지 않고 별도 체크박스로 기억해야 합니다.

이 절에서 꼭 기억할 것
  • Splay tree는 접근·삽입 후 rotation으로 노드를 위로 올린다.
  • AVL tree는 balance factor 위반을 rotation으로 복구한다.
  • plain BST는 leaf를 붙이기만 해도 삽입이 완료된다.
  • binary heap은 array의 마지막에 넣고 swap-up하며 tree rotation을 쓰지 않는다.
개념 3
개념 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
개념 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
개념 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
개념 6 · 정확히 두 개 선택(exactly two) 판정법

선택지를 서로 비교해 '가장 그럴듯한 두 개'를 고르지 않습니다. A부터 D까지 각각 독립적인 참·거짓 명제로 바꾸고 근거 또는 반례를 붙인 뒤 참의 개수를 셉니다.

현재 복기 데이터에서 판정된 정답 표시는 C, D입니다. 정답 수와 섹션 규칙이 충돌하는 문항은 억지로 두 개를 만들지 않고 복기 문언 누락 가능성을 명시합니다.

수식으로 정확히 쓰기

핵심 규칙선택 규칙: 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))

핵심 규칙검증된 선택지: C, D

이 절에서 꼭 기억할 것
  • 모든 tree update를 rotation으로 생각하거나, 반대로 self-balancing tree의 rotation을 잊는 함정.
  • 스플레이는 스플레이 회전, AVL은 균형 복구 회전, 일반 BST는 리프 연결, 힙은 위쪽 교환을 사용한다.

1. 시험장에서 따라 할 풀이 순서

풀이가 진행되며 무엇이 바뀌는지 먼저 한눈에 보기
1선택 규칙을 먼저 적는다

선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))

2문장을 쉬운 한국어로 다시 쓴다

회전(rotation)이 필요한 트리와 필요 없는 구조

3핵심 도구를 종이에 꺼낸다

Splay tree는 접근·삽입 후 rotation으로 노드를 위로 올린다. | AVL tree는 balance factor 위반을 rotation으로 복구한다. | plain BST는 leaf를 붙이기만 해도 삽입이 완료된다.

4선택지 A를 독립 판정한다

선택지 \(A =\)A =거짓

  1. 선택 규칙을 먼저 적는다

    이 문항의 규칙은 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))입니다. 마지막에 참 개수를 반드시 재검산합니다.

    핵심 규칙선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))

  2. 문장을 쉬운 한국어로 다시 쓴다

    트리에서 rotateLeft()와 rotateRight() 같은 rotation 함수에 대해 옳은 설명 두 개를 고르시오.

    핵심 규칙회전(rotation)이 필요한 트리와 필요 없는 구조

  3. 핵심 도구를 종이에 꺼낸다

    \(\text{Splay}=\)Splay=회전, \(\text{AVL}=\)AVL=회전, \(\text{plain} \text{BST}=\text{attach}, \text{heap}=\text{swap}\)plain BST=attach, heap=swap이라는 네 단어로 대응합니다.

    핵심 규칙Splay tree는 접근·삽입 후 rotation으로 노드를 위로 올린다. | AVL tree는 balance factor 위반을 rotation으로 복구한다. | plain BST는 leaf를 붙이기만 해도 삽입이 완료된다.

  4. 선택지 A를 독립 판정한다

    강의에서 스플레이 삽입(splay insertion)은 먼저 BST처럼 삽입 지점을 찾고, 새 노드 x를 스플레이 연산(splay operation)으로 루트까지 올린다. 이 연산은 zig, zig-zig, zig-zag 회전의 연속이다.

    \[선택지 A = 거짓\]선택지 A = 거짓
  5. 선택지 B를 독립 판정한다

    AVL 삽입은 균형 인수(balance factor)를 위반할 수 있다. 강의와 Sheet06 해설처럼 LL·RR 경우는 단일 회전, LR·RL 경우는 이중 회전으로 복구한다.

    \[선택지 B = 거짓\]선택지 B = 거짓
  6. 선택지 C를 독립 판정한다

    강의의 BST insert는 root에서 내려가 빈 위치를 찾고 새 node를 leaf로 붙인다. 균형을 보장하지 않기 때문에 rotation repair가 필수 단계가 아니다.

    \[선택지 C = 참\]선택지 C = 참
  7. 선택지 D를 독립 판정한다

    Heap insert는 complete-tree shape가 정한 마지막 위치에 값을 넣고, parent보다 크면 위로 swap한다. 이것은 BST rotation이 아니라 sift-up이다.

    \[선택지 D = 참\]선택지 D = 참
  8. 정답 수와 애매성을 재검산한다

    참으로 판정된 선택지는 C, D입니다. 복기 섹션 규칙과 수가 다르면 원문 누락 가능성을 기록하고 거짓을 참으로 조작하지 않습니다.

    \[검증된 정답 = C, D\]검증된 정답 = C, D

2. 이 문제를 실제로 끝까지 풀기

Rotation은 모든 트리 삽입의 필수 동작이 아니라, BST 순서를 보존하면서 모양을 다시 잡는 도구입니다. 구조가 어떤 invariant를 복구해야 하는지부터 확인합니다.

풀이를 시작할 때 다음 네 사실을 먼저 적습니다. (1) Splay tree는 접근·삽입 후 rotation으로 노드를 위로 올린다. (2) AVL tree는 balance factor 위반을 rotation으로 복구한다. (3) plain BST는 leaf를 붙이기만 해도 삽입이 완료된다. (4) binary heap은 array의 마지막에 넣고 swap-up하며 tree rotation을 쓰지 않는다.

선택지 A는 거짓입니다. 강의에서 스플레이 삽입(splay insertion)은 먼저 BST처럼 삽입 지점을 찾고, 새 노드 x를 스플레이 연산(splay operation)으로 루트까지 올린다. 이 연산은 zig, zig-zig, zig-zag 회전의 연속이다. 가장 작은 확인 예는 스플레이 트리에 키를 손자 노드로 삽입하면, 삽입된 노드를 zig-zig 또는 zig-zag 회전으로 위로 이동한다.

선택지 B는 거짓입니다. AVL 삽입은 균형 인수(balance factor)를 위반할 수 있다. 강의와 Sheet06 해설처럼 LL·RR 경우는 단일 회전, LR·RL 경우는 이중 회전으로 복구한다. 가장 작은 확인 예는 빈 AVL 트리에 10, 20, 30을 차례로 삽입하면 노드 10의 오른쪽 높이가 2만큼 커지므로 rotateLeft(10)이 필요하다.

선택지 C는 참입니다. 강의의 BST insert는 root에서 내려가 빈 위치를 찾고 새 node를 leaf로 붙인다. 균형을 보장하지 않기 때문에 rotation repair가 필수 단계가 아니다.

선택지 D는 참입니다. Heap insert는 complete-tree shape가 정한 마지막 위치에 값을 넣고, parent보다 크면 위로 swap한다. 이것은 BST rotation이 아니라 sift-up이다.

따라서 현재 문언에서 참으로 검증된 선택지는 C, D입니다. 선택지는 서로 상대평가하지 않고 각 문장을 정의·전제·반례로 독립 검증했습니다.

시험장에서 쓸 압축 절차는 다음과 같습니다. \(\text{Splay}=\)Splay=회전, \(\text{AVL}=\)AVL=회전, \(\text{plain} \text{BST}=\text{attach}, \text{heap}=\text{swap}\)plain BST=attach, heap=swap이라는 네 단어로 대응합니다. 시간이 부족해도 '항상(always)', '오직(only)', '모든(every)' 같은 강한 단어와 전제조건, O와 Θ를 먼저 확인하면 대표 함정을 피할 수 있습니다.

3. 선택지 A–D를 한 줄도 건너뛰지 않고 판정하기

  1. A거짓

    강의에서 스플레이 삽입(splay insertion)은 먼저 BST처럼 삽입 지점을 찾고, 새 노드 x를 스플레이 연산(splay operation)으로 루트까지 올린다. 이 연산은 zig, zig-zig, zig-zag 회전의 연속이다.

    빠른 확인법: 스플레이 트리에 키를 손자 노드로 삽입하면, 삽입된 노드를 zig-zig 또는 zig-zag 회전으로 위로 이동한다.

  2. B거짓

    AVL 삽입은 균형 인수(balance factor)를 위반할 수 있다. 강의와 Sheet06 해설처럼 LL·RR 경우는 단일 회전, LR·RL 경우는 이중 회전으로 복구한다.

    빠른 확인법: 빈 AVL 트리에 10, 20, 30을 차례로 삽입하면 노드 10의 오른쪽 높이가 2만큼 커지므로 rotateLeft(10)이 필요하다.

  3. C참 — 정답 후보

    강의의 BST insert는 root에서 내려가 빈 위치를 찾고 새 node를 leaf로 붙인다. 균형을 보장하지 않기 때문에 rotation repair가 필수 단계가 아니다.

    빠른 확인법: 일반 binary search tree는 삽입할 때 rotation 함수가 필요 없다.

  4. D참 — 정답 후보

    Heap insert는 complete-tree shape가 정한 마지막 위치에 값을 넣고, parent보다 크면 위로 swap한다. 이것은 BST rotation이 아니라 sift-up이다.

    빠른 확인법: 이진 max-heap은 삽입할 때 rotation 함수가 필요 없다.

4. 초보자가 가장 자주 틀리는 이유

  • 모든 tree update를 rotation으로 생각하거나, 반대로 self-balancing tree의 rotation을 잊는 함정.
  • exactly-two라는 이유만으로 근거 없이 두 선택지를 맞다고 만든다.
  • 선택지의 절반만 맞는데 결합 문장 전체를 참으로 판정한다.
  • always, only, every 같은 강한 단어를 놓친다.
  • 정의와 구현, 전제조건과 결론, upper bound와 tight bound를 섞는다.
  • 작은 예 하나로 거짓은 깰 수 있지만 참인 보편 명제를 증명했다고 착각한다.
  • 복기 시험지가 공식 원문·공식 답안이라는 전제로 애매성을 숨긴다.
  • 용어를 암기한 소리만 따라가고 실제 상태나 한 단계 실행을 그리지 않는다.

5. 시험 답안 템플릿

\(\text{Splay}=\)Splay=회전, \(\text{AVL}=\)AVL=회전, \(\text{plain} \text{BST}=\text{attach}, \text{heap}=\text{swap}\)plain BST=attach, heap=swap이라는 네 단어로 대응합니다. 각 선택지를 정의와 전제에 따라 독립 판정하면 참인 label은 C, D이다. 핵심 근거: Splay tree는 접근·삽입 후 rotation으로 노드를 위로 올린다. AVL tree는 balance factor 위반을 rotation으로 복구한다. plain BST는 leaf를 붙이기만 해도 삽입이 완료된다. binary heap은 array의 마지막에 넣고 swap-up하며 tree rotation을 쓰지 않는다.

6. 스스로 이해했는지 확인

II-6의 주제를 한 문장으로 설명하면?

정답: Rotation은 모든 트리 삽입의 필수 동작이 아니라, BST 순서를 보존하면서 모양을 다시 잡는 도구입니다. 구조가 어떤 invariant를 복구해야 하는지부터 확인합니다.

이 문제에서 가장 먼저 꺼낼 판정법은?

정답: \(\text{Splay}=\)Splay=회전, \(\text{AVL}=\)AVL=회전, \(\text{plain} \text{BST}=\text{attach}, \text{heap}=\text{swap}\)plain BST=attach, heap=swap이라는 네 단어로 대응합니다.

핵심 사실 네 가지 중 첫 번째는?

정답: Splay tree는 접근·삽입 후 rotation으로 노드를 위로 올린다.

핵심 사실 네 가지 중 두 번째는?

정답: AVL tree는 balance factor 위반을 rotation으로 복구한다.

가장 위험한 함정은?

정답: 모든 tree update를 rotation으로 생각하거나, 반대로 self-balancing tree의 rotation을 잊는 함정.

정답 label은?

정답: C, 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-6
    복기된 문언과 선택지; 공식 답안지가 아님
  • 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 회전 경우를 뒷받침한다.

개념을 덮고 같은 문항 다시 풀기

이 페이지 안에서 선택지를 고르고 채점하세요. 정답 해설은 제출한 뒤에 열립니다.

II-6 · 정확히 2개 선택

Rotationen (d.h., Funktionen rotateLeft() und rotateRight()) in Bäumen:

트리에서 rotateLeft()와 rotateRight() 같은 rotation 함수에 대해 옳은 설명 두 개를 고르시오.

정답과 선택지별 해설 보기

정답: C, D · 기대 2개 / 확인 2개

핵심 함정: 모든 tree update를 rotation으로 생각하거나, 반대로 self-balancing tree의 rotation을 잊는 함정.

10초 판별법: 스플레이는 스플레이 회전, AVL은 균형 복구 회전, 일반 BST는 리프 연결, 힙은 위쪽 교환을 사용한다.

마지막 생성: 2026-08-03 03:24