6. Fortgeschrittene Datenstrukturen (12 Punkte)

6.1(a) · 후보 트리 1 · 레드-블랙 트리 판정

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

  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 판정은 모양이 균형처럼 보이는지 눈대중으로 정하는 문제가 아닙니다. BST order, root color, red-red, black-height를 체크리스트 순서대로 검사합니다.

Tree 1의 root 27은 사각형이므로 red입니다. 문제 범례에서 사각형=red, 원=\(\text{circle}=\text{black}\)circle=black이며 기호를 바꾸면 안 됩니다.

root가 black이어야 한다는 규칙 하나만으로 이미 invalid입니다. 여기에 경로별 black-height까지 비교하면 추가 위반도 확인됩니다.

필요한 개념을 깊게 배우기

개념 1

0단계 · 범례부터

Rectangle은 red, circle은 black입니다. 색을 반대로 읽으면 모든 판정이 무너집니다.

NIL child는 그림에 없지만 black leaf로 존재한다고 간주합니다.

수식으로 정확히 쓰기

\[\text{rectangle}=R\]rectangle=R
\[\text{circle}=B\]circle=B
\[\text{NIL}=B\]NIL=B
개념 2

1단계 · root 규칙

Red-Black Tree의 root는 반드시 black입니다. Tree 1은 root 27이 red라서 다른 규칙을 보기 전에도 탈락합니다.

답안에는 단순히 '아니다'가 아니라 정확히 어느 node가 어느 규칙을 위반했는지 써야 합니다.

수식으로 정확히 쓰기

\[\text{루트}.\text{color}=\text{BLACK}\]root.color=BLACK
개념 3

2단계 · black-height 반례

한 node에서 leaf·half-leaf 방향으로 내려가는 경로의 black internal node 수가 같아야 합니다. NIL sentinel은 black이지만 강의 수치는 \(\text{SH}(\text{nil})=0\)SH(nil)=0이므로 NIL 자체를 더하지 않습니다.

왼쪽의 21 경로와 12 경로만 비교해도 1 대 3으로 다르므로 위반입니다.

수식으로 정확히 쓰기

\[\text{SH}(\text{nil})=0\]SH(nil)=0
\[\text{black}(27-18-21)=1\]black(27-18-21)=1
\[\text{black}(27-18-9-12)=3\]black(27-18-9-12)=3
초보자용 연결 강의

이 소문제를 왜 배우나

Red-Black Tree 판정은 ‘대충 균형으로 보인다’가 아니라 독립된 규칙들을 증거와 함께 검사하는 작업입니다. 한 규칙의 정확한 witness만 찾아도 invalid를 증명할 수 있고, black-height 숫자는 강의 convention에 맞춰야 합니다.

풀이 전에 꼭 알아야 할 말

핵심 학습 항목 (Red-Black Tree)

BST에 node color와 black-height 규칙을 추가해 height를 제한하는 binary search tree입니다. BST order, root black, no red-red, equal black-height를 모두 만족해야 합니다.

아주 작은 예: root가 red인 tree는 다른 규칙과 무관하게 Red-Black Tree가 아닙니다.

핵심 학습 항목 (leaf·half-leaf·NIL)

leaf는 child가 없고 half-leaf는 child가 하나인 internal node입니다. 없는 child는 NIL sentinel로 생각하며 색은 black이지만 강의 Schwarzhöhe에서 \(\text{SH}(\text{nil})=0\)SH(nil)=0입니다.

아주 작은 예: red leaf 21 뒤의 NIL을 black node 한 개로 더하지 않습니다.

증거 경로 (witness path)

같아야 하는 수치가 다르거나 금지된 edge가 존재함을 보여 주는 최소 반례 경로입니다. invalid 답은 모든 path를 나열하지 않아도 정확한 witness 하나면 충분합니다.

아주 작은 예: 27-18-21과 27-18-9-12의 1 대 3 비교가 witness입니다.

안전 인증 체크리스트

건물 인증에서 입구 규정, 배선 규정, 출구 검문소 규정을 따로 검사한다고 생각합니다. 입구가 규정을 어기면 즉시 불합격이고, 두 출구까지 검은 검문소 수가 다르면 또 다른 불합격 근거가 됩니다.

건물 입구의 필수 인증 표지
↔
root must be black
위험 구역 두 개가 직접 이어지면 안 되는 배선 규정
↔
no red-red edge
모든 출구까지 같은 수의 검은 검문소
↔
equal black-height

비유의 한계: 건물은 한 규정 실패 뒤 검사를 끝낼 수 있지만 학습 페이지에서는 추가 위반도 찾아 규칙 간 차이를 연습합니다. NIL의 색과 SH 수치는 실제 검문소 비유와 완전히 같지 않습니다.

위반 node와 두 witness path overlay

\(27 = R \text{루트}\)27 = R rootroot black 규칙을 즉시 위반하는 최소 witness입니다.
27-18-21: black 1red 27과21은 세지 않고 black 18만 셉니다.
27-18-9-12: black 3black 18,9,12를 세며 terminal NIL은 +1하지 않습니다.

root 27은 risk 색으로, black-height 비교 path는 서로 다른 강조선으로 표시합니다. 각 node 옆 label은 강의 \(\text{SH}(\text{nil})=0\)SH(nil)=0수치를 사용합니다.

먼저 작은 예제로 연습 · black root 10과 red children

black root 10 아래 red leaf 5와 red leaf 15가 있는 가장 작은 valid color 예시를 검사합니다.

BST와 root 확인

\(5<10<15\)5<10<15이고 root 10은 black이므로 첫 두 규칙을 만족합니다.

BST PASS, root B
red-red 확인

red 5와15의 children은 모두 black NIL이며 red child가 없습니다.

no R-R PASS
black-height 확인

두 terminal 방향 모두 black internal node 10 하나를 지나고 \(\text{SH}(\text{nil})=0\)SH(nil)=0입니다.

\(\text{left}=1, \text{right}=1\)left=1, right=1

작은 예제의 결론: NIL의 색은 black이지만 black-height 숫자에 NIL을 1로 더하지 않아도 equality 판정은 정확히 수행할 수 있습니다.

이제 실제 시험 문제에 연결

범례에서 root 27은 무슨 색인가?

사각형이므로 red입니다. 복기 문언은 rectangle을 red로 고정하고 기호 재정의를 금지합니다.

첫 번째로 확정되는 verdict는 무엇인가?

root는 black이어야 하는데 27이 red이므로 Tree 1은 즉시 Nein, invalid입니다.

짧은 witness path의 black 수는 얼마인가?

27(R)-18(B)-21(R)에서 black internal node는 18 하나이므로 강의 기준 1입니다.

긴 witness path의 black 수는 얼마인가?

27(R)-18(B)-9(B)-12(B)에서 18,9,12 세 개를 세므로 3입니다.

시험 답안에는 어떻게 쓰는가?

Nein 뒤에 ‘Wurzel 27 ist rot’를 먼저 쓰고, 추가 근거로 두 path의 Schwarzhöhe 1과3이 다르다고 위치를 명시합니다.

답이 맞는지 스스로 검산

  • JSON witness의 \(\text{black}_{\text{nodes}}\)black(nodes)길이가 각각 \(\text{course}_{\text{count}} 1\)course(count) 1과3과 같은지 확인하고 NIL을 목록에 넣지 않습니다.
  • root 27의 children 18과36은 black이므로 root red 자체는 red-red 위반이 아니라 별도의 root-color 위반임을 구분합니다.
  • BST inorder가 정렬되어도 color 규칙 두 개가 실패하므로 전체 verdict는 false입니다.

30초 자가점검

NIL sentinel이 black이면 왜 \(\text{SH}(\text{nil})=1\)SH(nil)=1이 아닌가?

힌트: 색 속성과 black-height base-case 정의를 분리합니다.

정답: 강의가 NIL을 black sentinel로 모델링하면서도 Schwarzhöhe 재귀의 base case를 \(\text{SH}(\text{nil})=0\)SH(nil)=0으로 정의했기 때문입니다.

root 위반 하나만 쓰면 충분한가?

힌트: negative 답의 최소 요구를 봅니다.

정답: 네. 정확한 규칙과 위치를 쓴 root 27 witness 하나로 invalid가 증명됩니다. black-height 위반은 추가로 견고한 근거입니다.

마지막에 쓰는 시험 답안 틀

Nein. Die Wurzel 27 ist rot, obwohl die Wurzel schwarz sein muss. Zusätzlich sind die Schwarzhöhen verschieden: 27-18-21 enthält 1 schwarzen internen Knoten, 27-18-9-12 enthält 3; SH(nil)=0.

자주 하는 실수

근거와 정확성 범위

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

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