6. Fortgeschrittene Datenstrukturen (12 Punkte)

6.1(c) · 후보 트리 3 · 레드-블랙 트리 판정

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

  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입니다.

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

Tree 3은 네 후보 중 유효한 Red-Black Tree입니다. 참이라고 답할 때도 근거 없이 '모양이 균형'이라고 쓰면 부족합니다.

root 13은 black이고 key order가 맞습니다. red node 3,21,18은 모두 black child만 가지며, 강의 \(\text{SH}(\text{nil})=0\)SH(nil)=0기준 모든 terminal path의 black internal node 수가 3으로 같습니다.

positive answer에서는 만족한 속성을 명시하라는 문제 요구가 있으므로 체크리스트 전 항목을 짧게 확인합니다.

필요한 개념을 깊게 배우기

개념 1

0단계 · positive proof

유효하다는 주장은 위반을 못 찾았다는 말보다 강합니다. 모든 rule을 빠짐없이 확인해야 합니다.

BST, root, red-red, black-height 순으로 답안을 쓰면 누락을 막을 수 있습니다.

수식으로 정확히 쓰기

핵심 규칙\(\text{유효} \Longleftrightarrow \text{every} \text{RB} \text{rule} \text{holds}\)valid ⇔ every RB rule holds

개념 2

1단계 · red node 검사

사각형 3,21,18 각각의 바로 아래 child를 봅니다. 모두 black circle이며 빈 child도 black NIL입니다.

red node의 parent가 red여도 같은 red-red edge이므로 위쪽과 아래쪽 모두 실제로는 edge 기준 검사입니다.

수식으로 정확히 쓰기

\[R \text{parent} \Rightarrow \text{children} B\]R parent ⇒ children B
개념 3

2단계 · black-height 표본과 일반화

왼쪽 짧은/긴 경로와 오른쪽 짧은/긴 경로를 대표로 골라 black 수를 셉니다. 모두 root와 두 추가 black internal nodes로 3이며 NIL은 \(\text{SH}(\text{nil})=0\)SH(nil)=0입니다.

각 branching node의 두 child subtree Schwarzhöhe가 같은 것을 bottom-up label로 확인하면 모든 경로를 빠짐없이 증명할 수 있습니다.

수식으로 정확히 쓰기

\[\text{SH}(\text{nil})=0\]SH(nil)=0

핵심 규칙\(\text{루트}-\text{to}-\text{terminal} \text{black} \text{count}=3\)root-to-terminal black count=3

초보자용 연결 강의

이 소문제를 왜 배우나

invalid tree는 위반 하나로 끝낼 수 있지만 valid tree는 ‘못 찾았다’가 아니라 모든 필수 규칙이 성립함을 보여야 합니다. bottom-up Schwarzhöhe label은 많은 path를 빠짐없이 압축해 증명하는 방법입니다.

풀이 전에 꼭 알아야 할 말

성립 증명 (positive proof)

위반을 우연히 못 찾았다는 말이 아니라 definition의 모든 항목을 확인하는 증명입니다. 체크리스트 누락 하나가 있으면 Ja 답안의 근거가 불완전합니다.

아주 작은 예: BST와 root만 맞다고 Ja라고 결론 내리면 안 됩니다.

핵심 학습 항목 (bottom-up SH)

\(\text{SH}(\text{nil})=0\)SH(nil)=0에서 시작해 양쪽 child의 Schwarzhöhe가 같은지 확인하고 black node이면 1을 더해 parent label을 만듭니다. 한 node에서 다르면 즉시 invalid입니다.

아주 작은 예: black leaf 11은 child nil의 0에 자기 1을 더해 \(\text{SH}=1\)SH=1입니다.

red node 검사

red node와 바로 연결된 child가 red인지 edge 기준으로 확인합니다. 없는 child는 black NIL이므로 red leaf는 no-red-red 규칙을 만족할 수 있습니다.

아주 작은 예: red 18의 children 17과19는 모두 black입니다.

모든 필수 과목을 통과한 성적표

졸업하려면 한 과목에서 낙제하지 않은 정도가 아니라 모든 필수 과목의 합격 성적을 제시해야 합니다. BST, root color, red-red, black-height가 각각 필수 과목이고 SH label은 경로 과목의 채점표입니다.

모든 필수 과목 합격
↔
네 규칙 모두 PASS
누락 없이 확인할 수강 과목 목록
↔
red node 목록 3,21,18
각 분반 점수를 합쳐 전체 성적표 작성
↔
bottom-up SH label

비유의 한계: 실제 과목은 평균으로 보상될 수 있지만 RB 규칙은 하나라도 실패하면 invalid입니다. 비유는 체크리스트 완전성만 설명합니다.

모든 node에 SH를 붙인 positive certificate

BST + root 13(B)inorder가 정렬되고 root가 black입니다.
R nodes: 3,21,18세 red node의 child가 모두 black internal node 또는 NIL입니다.
\(\text{SH}(\text{루트})=3\)SH(root)=3왼쪽·오른쪽 모든 terminal path의 black internal node 수가 3입니다.

tree 그림의 각 node 옆에 SH label을 두고 red node에는 R badge를 표시합니다. root 13의 두 child subtree SH가 2로 같아 최종 root count 3이 됩니다.

먼저 작은 예제로 연습 · black root와 비대칭 깊이의 valid 색칠

black root 10, left red 5 아래 black leaves 3·7, right black 15인 tree를 bottom-up으로 검사합니다.

terminal SH 설정

black leaves 3,7,15는 nil child의 0에 자기 black 1을 더해 \(\text{SH}=1\)SH=1입니다.

\(\text{SH}(3)=\text{SH}(7)=\text{SH}(15)=1\)SH(3)=SH(7)=SH(15)=1
red 5 계산

두 child SH가 1로 같고 red 5는 black count를 더하지 않습니다.

\(\text{SH}(5)=1\)SH(5)=1
root 10 계산

left SH 1과 right SH 1이 같고 black root에서 1을 더합니다.

\(\text{SH}(10)=2 \to \text{유효}\)SH(10)=2 → valid

작은 예제의 결론: edge depth가 달라도 red node는 black count를 늘리지 않으므로 equal Schwarzhöhe를 만족할 수 있습니다.

이제 실제 시험 문제에 연결

Tree 3은 BST인가?

네. 모든 subtree가 ancestor가 만든 key interval을 지키며 inorder가 오름차순입니다.

root와 red-red 규칙은 어떤가?

root 13은 black이고 red 3의 children 1·4, red21의 16·24, red18의 17·19가 모두 black입니다.

왼쪽 path의 black count는 얼마인가?

13-9-11은 13,9,11 세 개이고 13-9-3-1은 red3을 빼고 13,9,1 세 개입니다.

오른쪽 path도 왜 모두 3인가?

21과18은 red라 세지 않고 각 path가 black root13과 black internal 두 개를 지나므로 모두 3입니다.

positive answer를 어떻게 마무리하는가?

네 규칙을 모두 한 문장씩 확인하고 \(\text{SH}(\text{nil})=0 \text{convention}\)SH(nil)=0 convention아래 common Schwarzhöhe 3이라고 씁니다.

답이 맞는지 스스로 검산

  • \(\text{witness}_{\text{paths}}\)witness(paths)네 행의 \(\text{black}_{\text{nodes}}\)black(nodes)길이가 모두 \(\text{course}_{\text{count}} 3\)course(count) 3인지 자동 확인합니다.
  • \(\text{sh}_{\text{labels}}\)sh(labels)를 bottom-up으로 계산할 때 모든 internal node의 left/right child SH가 같고 root label이 3인지 확인합니다.
  • red node 목록이 정확히 {3,21,18}이며 그 사이 또는 child 방향에 red-red edge가 하나도 없는지 검사합니다.

30초 자가점검

대표 path 네 개만 같으면 무조건 모든 path가 같다고 말할 수 있는가?

힌트: 각 branching node의 두 child를 모두 검사하는 방법을 생각합니다.

정답: 표본만으로는 부족할 수 있습니다. 각 node에서 left/right SH equality를 bottom-up으로 확인하면 모든 path를 빠짐없이 증명합니다.

Tree 3의 강의 기준 common black count는 얼마인가?

힌트: NIL을 +1하지 않습니다.

정답: 3입니다. 예를 들어 13-9-11에서 black internal nodes 13,9,11을 셉니다.

마지막에 쓰는 시험 답안 틀

Ja. Der Baum ist ein BST, die Wurzel 13 ist schwarz, jeder rote Knoten (3,21,18) hat schwarze Kinder, und alle Pfade zu Blättern/Halbblättern haben dieselbe Schwarzhöhe 3; SH(nil)=0.

자주 하는 실수

근거와 정확성 범위

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

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