6. Fortgeschrittene Datenstrukturen (12 Punkte)

6.1(d) · 후보 트리 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)=0`	NIL sentinel은 black으로 모델링하지만 강의 Schwarzhöhe 수치에서는 nil 자체에 1을 더하지 않습니다.	Tree 3의 root-to-terminal black 수는 3이지 4가 아닙니다.
\(t=2\)`t=2`	B-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 4는 root가 black이고 red-red edge도 없어 처음에는 그럴듯합니다. 하지만 key placement와 NIL 경로를 확인하면 두 가지 위반이 드러납니다.

node 7은 11의 right child인데 \(7<11\)7<11이라 BST order 위반입니다. 또한 red 86의 left에는 black 74가 있지만 right는 바로 NIL이라 두 경로 black 수가 다릅니다.

negative answer에는 최소 한 위반만 요구되지만 두 위반을 정확히 쓰면 판정이 더 견고합니다.

필요한 개념을 깊게 배우기

개념 1

0단계 · 두 축을 분리

key order와 color balance는 서로 독립입니다. 하나가 맞아도 다른 하나가 자동으로 맞지 않습니다.

먼저 inorder 또는 범위로 BST를 검사하고 다음에 색 경로를 셉니다.

수식으로 정확히 쓰기

핵심 규칙BST check + color check

개념 2

1단계 · 7의 범위

11의 right subtree 전체는 (11,68) 범위에 있어야 합니다. 7은 이 범위를 벗어나므로 direct child 관계만으로 invalid입니다.

6과9가 7의 children으로 local order를 지켜도 7 자체가 ancestor 11의 범위를 위반합니다.

수식으로 정확히 쓰기

핵심 규칙right of 11 ⇒ key>11; \(\text{but} 7<11\)but 7<11

개념 3

2단계 · 86 아래 NIL 경로

86은 red이므로 86 자체는 black count에 넣지 않습니다. right NIL 방향은 68,89 두 black이고 left 74 방향은 68,89,74 세 black입니다.

NIL sentinel은 black이지만 강의 Schwarzhöhe는 \(\text{SH}(\text{nil})=0\)SH(nil)=0이므로 terminal에 1을 더하지 않습니다.

수식으로 정확히 쓰기

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

\[\text{black}(\text{left} \text{via} 74)=3\]black(left via 74)=3

\[\text{black}(\text{right} \text{missing})=2\]black(right missing)=2

초보자용 연결 강의

이 소문제를 왜 배우나

한 tree 안에서 key-order 위반과 color-balance 위반이 동시에 존재할 수 있습니다. 두 검사 축을 분리해 최소 witness를 찾으면 root가 black이고 겉모양이 균형이어도 왜 invalid인지 정확히 설명할 수 있습니다.

ancestor interval을 이용해 7의 BST 위치 위반을 찾고 local children 6·9의 정렬과 혼동하지 않습니다.
half-leaf 86의 존재하는 child와 missing child 방향을 모두 path로 포함해 black count 3 대2를 계산합니다.
두 독립 위반 중 하나를 최소 답으로, 둘 다를 견고한 답으로 작성할 수 있습니다.

풀이 전에 꼭 알아야 할 말

조상으로부터 받은 허용 구간 (ancestor range)

node가 parent와 locally 정렬되어도 더 위 ancestor가 만든 lower·upper bound를 위반할 수 있습니다. root부터 방향을 따라 range를 갱신해야 합니다.

아주 작은 예: \(68\to \text{left}11\to \text{right}\)68→left11→right위치는 11보다 크고 68보다 작아야 합니다.

missing child도 path

half-leaf의 없는 child 방향은 NIL로 끝나는 실제 비교 path입니다. 존재하는 child 쪽만 세면 black-height 위반을 놓칩니다.

아주 작은 예: red86의 right child가 없으므로 68-89-86에서 terminal path 하나가 끝납니다.

독립된 violation

BST order와 equal Schwarzhöhe는 서로 다른 필수 조건입니다. 하나의 수정이 다른 위반을 자동으로 해결한다고 가정하면 안 됩니다.

아주 작은 예: 7의 위치를 고쳐도 86 아래 2 대3 mismatch는 남습니다.

주소 검사와 출구 검사 두 장

건물 방 번호가 올바른 구역에 있는지 보는 주소 검사와 각 출구까지 검문소 수를 세는 안전 검사는 별도입니다. 7번 방은 잘못된 구역이고, 86번 갈림길의 한 출구에는 검문소 74가 하나 더 있습니다.

11보다 큰 번호 구역에 더 작은 7번 방

↔

7∉(11,68)

두 출구 중 한쪽에만 추가 검문소

↔

86 missing/right vs 74/left

주소 심사와 안전 심사 모두 불합격

↔

두 규칙 모두 FAIL

비유의 한계: 실제 건물은 방 번호를 바꾸거나 검문소를 옮길 수 있지만 이 문제는 repair가 아니라 판정만 요구합니다. witness를 찾은 뒤 tree를 수정할 필요는 없습니다.

BST risk edge와 SH mismatch path를 동시에 표시

7 ∉ (11,68)11의 right subtree인데 \(7<11\)7<11이므로 BST FAIL입니다.

via 74: black 368,89,74를 세고 red86과 NIL은 더하지 않습니다.

missing right: black 268,89만 세므로 한 개 부족합니다.

\(11\to 7 \text{edge}\)11→7 edge는 빨간 \(\text{BST} \text{violation}, 68\to 89\to 86\)BST violation, 68→89→86의 두 terminal 방향은 서로 다른 semantic color로 표시합니다. connector를 먼저 그리고 node와 count label을 위에 둡니다.

먼저 작은 예제로 연습 · red half-leaf 아래 한쪽 black child

black root 10의 right black 20 아래 red30이 있고, red30의 left에 black25만 있는 작은 tree를 black-height만 검사합니다.

missing right path 세기

10과20은 black, 30은 red이며 right NIL은 SH 0입니다.

10-20-30-right: count 2

left child path 세기

같은 prefix에 black25가 추가되어 black internal node가 하나 더 있습니다.

10-20-30-25: count 3

mismatch 판정

같은 branching node 30 아래 terminal path의 count가 2와3으로 달라 equal SH를 위반합니다.

2≠\(3 \to \text{invalid}\)3 → invalid

작은 예제의 결론: 없는 child 방향을 제외하지 않아야 half-leaf가 만드는 Schwarzhöhe mismatch를 발견할 수 있습니다.

이제 실제 시험 문제에 연결

root와 red-red 규칙은 통과하는가?

네. root68은 black이고 red7,86,92,97의 children은 black internal node 또는 NIL입니다.

7의 허용 범위는 어떻게 얻는가?

68에서 left라 upper bound68, 11에서 right라 lower bound11이므로 range는 (11,68)입니다.

왜 7의 children 6과9가 정렬된 것은 충분하지 않은가?

\(6<7<9\)6<7<9라는 local order와 별개로 node7 자체가 ancestor11의 right subtree 조건 \(7>11\)7>11을 위반합니다.

86 아래 두 path의 count는 얼마인가?

missing right는 black68,89 두 개이고 left74 방향은 68,89,74 세 개입니다. red86과 NIL은 더하지 않습니다.

시험 답안은 어떻게 구성하는가?

Nein 뒤에 7의 BST witness 하나만 써도 충분하며, 추가로 86 아래 Schwarzhöhe 2 대3을 쓰면 더 견고합니다.

답이 맞는지 스스로 검산

BST inorder가 11의 right 위치에서 7 때문에 감소하는지 확인하고 \(\text{allowed}_{\text{interval}} (11,68)\)allowed(interval) (11,68)과 actual7을 대조합니다.
두 SH witness의 \(\text{black}_{\text{nodes}}\)black(nodes)길이가 각각 \(\text{course}_{\text{count}2}\)course(count)2와3인지 확인합니다.
red86을 두 count에서 모두 제외하고 동일한 prefix 68,89만 공통으로 센 뒤 74 하나의 차이를 확인합니다.

30초 자가점검

86의 right child가 없으면 그 방향은 검사하지 않아도 되는가?

힌트: missing child가 무엇으로 모델링되는지 생각합니다.

정답: 아닙니다. right NIL도 terminal path이며 left74 방향과 black-height를 비교해야 합니다.

Tree 4를 invalid로 만드는 최소 한 문장은 무엇인가?

힌트: 가장 짧은 local key witness를 고릅니다.

정답: Knoten 7 liegt rechts von 11, obwohl 7<11; daher ist der Baum kein BST라고 쓰면 충분합니다.

마지막에 쓰는 시험 답안 틀

Nein. Erstens liegt 7 im rechten Teilbaum von 11, obwohl 7<11. Zweitens sind die Schwarzhöhen verschieden: über 74 liegen 3 schwarze interne Knoten, über die fehlende rechte Seite von 86 nur 2; SH(nil)=0.

자주 하는 실수

root black만 보고 합격시킨다.
7의 local children 6,9만 보고 ancestor 11 범위를 놓친다.
86의 없는 right child를 path 후보에서 제외한다.
black-height에서 red 86이나 terminal NIL을 +1로 센다.

근거와 정확성 범위

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

복기 문언·그림AuD Gedächtnisprotokoll SoSe 2025.md · lines 270-295 and six linked images · 신뢰도/범위: 비공식 기억 복기
문제 문언, rectangle/circle 범례, 네 RB 후보, 초기 B-Tree, AVL code 요구
후보 tree와 초기 B-Tree는 로컬 원본 crop과 구조를 대조했으며 정의는 현재 강의 자료로 교차 확인합니다.
강의 정의Vorlesung\04AdvancedDataStructures.pdf · pp. 3-5 · 신뢰도/범위: 현재 강의 슬라이드
RB 필수 규칙, leaf·half-leaf path, Schwarzhöhe와 \(\text{SH}(\text{nil})=0\)SH(nil)=0
강의 정의·문제Vorlesung\04AdvancedDataStructures.pdf · pp. 45-46 and p. 57 · 신뢰도/범위: 현재 강의 슬라이드
AVL height bound 맥락, \(H(\text{empty})=-1, B=\text{hR}-\text{hL}, \text{BST}\)H(empty)=-1, B=hR-hL, BST가 AVL인지 검사하는 문제
강의 정의·알고리즘Vorlesung\04AdvancedDataStructures.pdf · p. 114 and pp. 122-126 · 신뢰도/범위: 현재 강의 슬라이드
Grad t B-Tree invariant, insertion, root split, Suchen und Splitten
공식 연습 풀이Übung\AuD26_Sheet06-Sol.pdf · pp. 3-6 · 신뢰도/범위: 공식 풀이
RB 규칙별 판정과 위반 node를 명시하는 답안 방식
공식 연습 풀이Übung\AuD26_Sheet06-Sol.pdf · pp. 8-10 · 신뢰도/범위: 공식 풀이
AVL balance convention과 node별 검사 방식
공식 연습 풀이Übung\AuD26_Sheet08-Sol.pdf · pp. 1-3 · 신뢰도/범위: 공식 풀이
\(t=2 B-\text{Tree}\)t=2 B-Tree삽입, split·promotion 및 각 삽입 후 중간 tree
선수 강의Vorlesung\03BasicDataStructures.pdf · pp. 66-81 · 신뢰도/범위: 현재 강의 슬라이드
BST subtree-wide order, height와 recursive tree operation

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