6. Fortgeschrittene Datenstrukturen (12 Punkte)

6.1(b) · 후보 트리 2 · 레드-블랙 트리 판정

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

  1. 용어: 기호와 전제
  2. 직관: 비유와 작은 예
  3. 풀이: 실제 상태 변화
  4. 확인: 검산과 자가점검

자료의 성격과 정확성 경계

문제 문언·배점·후보 그림은 비공식 SoSe 2025 복기 lines 270-295와 연결 이미지에서 가져왔습니다. 정의와 수치 convention은 Lecture 04 pp.3-5, 45-46, p.57, p.114, pp.122-126으로 교차 확인했습니다. Sheet06-Sol은 RB/AVL, Sheet08-Sol은 B-Tree 삽입을 뒷받침하며, 일반 교재의 NIL-inclusive black count를 강의 SH 수치와 섞지 않습니다.

문제를 읽기 전에 알아둘 기호와 용어

기호를 모른 채 풀이를 외우지 않도록, 이 문제에서 실제로 쓰는 뜻과 작은 예를 먼저 확인합니다.

기호·용어뜻작은 예
항목 (R / rectangle)복기 그림에서 red node를 뜻하는 사각형입니다. 기호를 다른 색 의미로 재정의하지 않습니다.Tree 1의 root 27은 rectangle이므로 red입니다.
항목 (B / circle)복기 그림에서 black node를 뜻하는 원입니다. CSS 색만이 아니라 shape와 R/B label을 함께 읽습니다.Tree 3의 root 13은 black circle입니다.
\(\text{SH}(\text{nil})=0\)SH(nil)=0NIL sentinel은 black으로 모델링하지만 강의 Schwarzhöhe 수치에서는 nil 자체에 1을 더하지 않습니다.Tree 3의 root-to-terminal black 수는 3이지 4가 아닙니다.
\(t=2\)t=2B-Tree의 Grad 또는 minimum degree이며 non-root node의 key 수는 t-1부터 2t-1입니다.\(t=2\)t=2이면 한 node는 1~3 keys를 가집니다.
\(B(v)=\text{hR}-\text{hL}\)B(v)=hR-hL강의의 AVL balance factor로 오른쪽 subtree 높이에서 왼쪽 높이를 뺍니다.\(B(v)=-2\)B(v)=-2이면 이 convention에서는 left-heavy입니다.
실패AVL 검사 중 이미 균형 위반을 찾았다는 별도 반환값이며 유효한 높이 -1과 혼동하지 않습니다.empty tree는 height -1, invalid subtree는 FAIL입니다.

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

Red-Black Tree는 먼저 Binary Search Tree여야 합니다. 색과 black-height만 맞는 colored binary tree는 충분하지 않습니다.

Tree 2에서 node 3은 node 4의 오른쪽 child입니다. 오른쪽 subtree의 모든 key는 4 이상이어야 하는데 \(3<4\)3<4이므로 BST order가 깨집니다.

흥미롭게도 root 7은 black이고 red-red도 없으며 black-height도 맞습니다. 이 때문에 색만 검사하면 오답이 됩니다.

필요한 개념을 깊게 배우기

개념 1

0단계 · RB는 BST의 특수형

Red-Black Tree는 BST에 색·black-height 규칙을 추가한 구조입니다. 따라서 BST condition은 선택 사항이 아닙니다.

색 규칙을 검사하기 전에 각 edge가 key 범위를 지키는지 확인하면 이 문제를 빠르게 잡습니다.

수식으로 정확히 쓰기

핵심 규칙RB tree ⊂ BST

개념 2

1단계 · local edge 반례

4의 right subtree에는 4보다 큰 값만 있어야 합니다. 그런데 바로 right child가 3이므로 한 edge만으로 반례가 완성됩니다.

전체 inorder를 계산해도 [2,4,3,7,9,10,11,12]가 정렬되지 않아 같은 위반을 확인할 수 있습니다.

수식으로 정확히 쓰기

핵심 규칙\(3 \text{is} \text{right} \text{of} 4 \text{but} 3<4\)3 is right of 4 but 3<4

개념 3

2단계 · 나머지 규칙 검산

root 7은 black이고 red 11의 children 9,12는 black입니다. 2,3,10은 red leaf라 자식 NIL이 black입니다.

모든 경로 black 수가 같더라도 BST 실패 하나로 최종 verdict는 false입니다.

수식으로 정확히 쓰기

핵심 규칙all rules must hold

초보자용 연결 강의

이 소문제를 왜 배우나

Red-Black Tree는 색칠된 임의 binary tree가 아니라 먼저 BST여야 합니다. 색 규칙이 전부 맞는 후보에서도 key 하나가 ancestor가 만든 허용 범위를 벗어나면 전체가 invalid라는 우선순위를 훈련합니다.

풀이 전에 꼭 알아야 할 말

핵심 학습 항목 (subtree-wide BST order)

right child 하나만 큰 것으로 충분하지 않고 right subtree의 모든 descendant가 현재 node보다 커야 합니다. root부터 내려오며 lower·upper bound를 함께 유지합니다.

아주 작은 예: 7의 left subtree 안에서는 모든 key가 7보다 작아야 합니다.

허용 interval

오른쪽으로 가면 lower bound가 현재 key로 올라가고 왼쪽으로 가면 upper bound가 내려갑니다. 두 bound를 동시에 만족해야 ancestor 전체와 일관됩니다.

아주 작은 예: \(7\to \text{left}4\to \text{right}\)7→left4→right위치의 허용 범위는 (4,7)입니다.

필수 규칙의 AND 관계

RB validity는 BST, root black, no red-red, equal black-height가 모두 true일 때만 true입니다. 한 항목의 false를 다른 항목의 true가 보상하지 못합니다.

아주 작은 예: color 세 항목 \(\text{PASS} + \text{BST} \text{FAIL} =\)PASS + BST FAIL =전체 FAIL입니다.

안전 규정을 지킨 역주행 차량

차량의 브레이크, 안전벨트, 조명이 모두 정상이어도 반대 차선으로 달리면 도로 검사를 통과하지 못합니다. RB color 규칙은 안전 장비이고 BST order는 올바른 차선 방향입니다.

브레이크·벨트·조명 정상
↔
root/no-red-red/black-height 통과
안전한 차량이 반대 차선으로 역주행
↔
BST order 위반 \(3<4 \text{on} \text{right}\)3<4 on right
필수 검사 하나 실패로 운행 불가
↔
전체 invalid

비유의 한계: 실제 차량 규정에는 중요도 차이가 있지만 RB definition의 각 항목은 모두 논리적으로 필수입니다. 한 규칙이 더 ‘중요’해서가 아니라 AND 조건이기 때문에 실패합니다.

ancestor bound overlay로 3의 위치 확인

\(7 \to \text{left}\)7 → left이후 모든 key의 upper bound는 7입니다.
\(4 \to \text{right}\)4 → right이후 모든 key의 lower bound는 4입니다.
3 ∉ (4,7)\(3<4\)3<4이므로 BST witness가 완성됩니다.

7에서 left로 내려와 upper bound 7, 4에서 right로 내려와 lower bound 4를 얻습니다. node 3은 강조된 허용 interval (4,7) 밖입니다.

먼저 작은 예제로 연습 · 10의 right subtree에 8이 있는 경우

root 10의 right child가 15이고 그 left child가 8인 colored tree를 key order만 검사합니다.

10에서 right 이동

15와 그 descendants는 모두 10보다 커야 하므로 lower bound가 10이 됩니다.

\(\text{range}=(10,+\infty)\)range=(10,+∞)
15에서 left 이동

15보다 작아야 하므로 upper bound가 15로 내려가 최종 range는 (10,15)입니다.

\(\text{range}=(10,15)\)range=(10,15)
8 검사

8은 parent 15보다 작지만 ancestor lower bound 10을 위반합니다.

8∉\((10,15) \to \text{invalid}\)(10,15) → invalid

작은 예제의 결론: local parent-child 방향만 맞아도 충분하지 않으며 모든 ancestor가 만든 interval을 유지해야 BST입니다.

이제 실제 시험 문제에 연결

Tree 2의 root와 color 규칙은 어떻게 보이는가?

root 7은 black이고 red 2,3,11,10 사이에 red-red edge가 없습니다.

black-height는 강의 기준 얼마인가?

각 terminal path에서 root 7과 추가 black internal node 4·9·12 중 하나를 지나므로 모두 2입니다.

BST 검사는 어디서 실패하는가?

3은 4의 right child이므로 \(3>4\)3>4여야 하지만 실제 \(3<4\)3<4입니다. 전체 ancestor range로도 3∉(4,7)입니다.

색 규칙 통과가 왜 verdict를 구하지 못하는가?

RB tree는 BST이면서 모든 color rule을 만족해야 하는 AND 정의이므로 BST false 하나로 전체 false입니다.

시험 답안의 가장 짧은 정확한 형태는 무엇인가?

Nein. Knoten 3 liegt rechts von 4, obwohl 3<4; daher ist der Baum kein BST라고 위치와 비교를 씁니다.

답이 맞는지 스스로 검산

  • Tree 2의 inorder [2,4,3,7,9,10,11,12]가 4 다음 3에서 감소하므로 같은 BST 위반을 독립적으로 확인합니다.
  • 두 sample path의 \(\text{course}_{\text{count}}\)course(count)가 모두 2이고 NIL을 추가하지 않았는지 확인합니다.
  • 오직 violation overlay의 \(4\to 3 \text{edge}\)4→3 edge가 risk로 표시되고 color 규칙은 PASS로 남는지 확인합니다.

30초 자가점검

3은 parent 4보다 작으므로 left에 있어야 하는가?

힌트: 현재 그림에서 3이 연결된 방향을 봅니다.

정답: 네. \(3<4\)3<4인데 right child로 연결되어 있어 바로 그 edge가 BST order를 위반합니다.

black-height가 모두 같으면 자동으로 RB tree인가?

힌트: RB definition의 첫 조건을 떠올립니다.

정답: 아닙니다. 먼저 BST여야 하고 root black·no red-red 등 다른 모든 규칙도 함께 만족해야 합니다.

마지막에 쓰는 시험 답안 틀

Nein. Der Baum erfüllt zwar Wurzel-, Rot-Rot- und Schwarzhöhenregel mit Schwarzhöhe 2, ist aber kein BST: Knoten 3 liegt im rechten Teilbaum von 4, obwohl 3<4.

자주 하는 실수

근거와 정확성 범위

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

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