6번 · 고급 트리 구조: 레드-블랙 트리, B-트리, AVL 트리

레드-블랙 트리 판정부터 B-트리의 분할 삽입, AVL 트리의 후위 순회 검증까지 한 편의 한국어 문서로 이어서 설명합니다.

독일어 시험 주제명 확인

6. Fortgeschrittene Datenstrukturen (12 Punkte)

선행지식 없이 시작

이 페이지를 읽는 순서

BST, Red-Black Tree, B-Tree, AVL Tree를 처음 보는 학습자를 위한 페이지입니다. 세 구조의 관계를 먼저 분리하고, 각 규칙의 뜻을 작은 그림에서 확인한 뒤, 시험 tree의 위반 witness·split microstate·postorder trace를 한 단계씩 따라갑니다.

  1. 구조의 관계 먼저 보기

    Red-Black과 AVL은 BST의 binary balance 방식이고 B-Tree는 여러 key와 child를 갖는 multiway search tree라는 차이를 먼저 고정합니다.

  2. 강의 convention 고정

    RB는 NIL이 black이지만 \(\text{SH}(\text{nil})=0\)SH(nil)=0이며, AVL은 \(\text{height}(\text{empty})=-1\)height(empty)=-1과 \(B=\text{hR}-\text{hL}\)B=hR-hL을 사용합니다. 다른 convention과 숫자를 섞지 않습니다.

  3. 작은 witness로 판정

    무효 tree는 한 개의 정확한 위반 node/path만으로 반증하고, 유효 tree는 모든 규칙을 bottom-up label로 빠짐없이 확인합니다.

  4. 상태를 그린 뒤 검산

    B-Tree는 split과 promotion을 별도 frame으로 그리고, AVL은 child 결과가 parent로 올라오는 postorder 표를 채운 뒤 invariant와 runtime을 검산합니다.

먼저 익힐 기호와 용어

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

입문 설명을 읽은 뒤 사용하는 도구

레드-블랙 트리 판정 체크리스트

강의 수치 규약: 강의 Schwarzhöhe에서는 terminal NIL 자체를 +1로 세지 않습니다. 실제 black internal node만 세며 \(\text{SH}(\text{nil})=0\)SH(nil)=0입니다.

1P

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

독립 학습 안내: 앞 소문항을 읽지 않았어도 이 절의 문제 입력과 개념 설명부터 따라갈 수 있습니다.

먼저 문제를 정확히 읽기

복기 문언의 소문항별 재구성

공식 원문 인용이 아니라 비공식 시험 복기의 요구를 소문항별로 재구성한 문장입니다.

한국어 문제 뜻

Tree 1이 Red-Black Tree인지 판정하시오. 아니면 위반한 속성과 정확한 node 또는 path 위치를 최소 하나 제시하시오.

답안에 반드시 포함할 요소

  • Ja/Nein 판정
  • 위반 규칙 이름
  • 위반 node 또는 두 비교 path
재구성된 독일어 문장 보기 (Deutsch)

Entscheiden Sie, ob Baum 1 ein Rot-Schwarz-Baum ist. Begründen Sie die Antwort und nennen Sie bei einer negativen Antwort mindestens eine verletzte Eigenschaft und die Stelle.

6.1(a) 후보 트리 · 해설 표식 없는 입력
3R · 빨강 사각형9B · 검정 원12B · 검정 원18B · 검정 원21R · 빨강 사각형27R · 빨강 사각형29B · 검정 원36B · 검정 원42B · 검정 원59R · 빨강 사각형68B · 검정 원

문제의 정체를 한 문장으로

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까지 비교하면 추가 위반도 확인됩니다.

이 소문항만 읽어도 되는 연결 강의

왜 이 개념이 필요한가

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

이 절을 읽고 나면 다음을 할 수 있어야 합니다.

  • \(\text{rectangle}=\text{red}, \text{circle}=\text{black}\)rectangle=red, circle=black범례를 바꾸지 않고 root color 위반을 즉시 찾을 수 있습니다.
  • NIL은 black이지만 \(\text{SH}(\text{nil})=0\)SH(nil)=0이라는 차이를 설명하고 두 path의 black internal node 수를 셀 수 있습니다.
  • Nein 답안에 위반 규칙과 node/path 위치를 독일어 시험 문장으로 제시할 수 있습니다.

풀이 전에 꼭 알아야 할 말

레드-블랙 트리(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가 아닙니다.

잎·반쪽 잎·NIL(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입니다.

위반 노드와 두 목격 경로(witness path) 겹침 표시
  1. 루트 \(27 = R(\)27 = R(빨강)

    root black 규칙을 즉시 위반하는 최소 witness입니다.

  2. 경로 27-18-21: 검은 노드 1개

    red 27과21은 세지 않고 black 18만 셉니다.

  3. 경로 27-18-9-12: 검은 노드 3개

    black 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 예시를 검사합니다.

  1. 이진 탐색 순서(BST)와 루트 확인

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

    이 단계의 상태: BST PASS, root B

  2. 빨강-빨강 연결(red-red) 확인

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

    이 단계의 상태: no R-R PASS

  3. 검은 높이(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 판정은 정확히 수행할 수 있습니다.

정확한 개념 설명 · 0부터 차근차근

0단계 · 범례부터

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

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

\[\text{사각형}=R\;(\text{빨강})\]rectangle=R
복기 그림에서 사각형은 빨간 노드를 뜻합니다.
\[\text{원}=B\;(\text{검정})\]circle=B
복기 그림에서 원은 검은 노드를 뜻합니다.
\[\text{NIL 잎}=B\;(\text{검정})\]NIL=B
보이지 않는 NIL 잎은 모두 검은색으로 취급합니다.

1단계 · root 규칙

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

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

\[\operatorname{color}(\operatorname{root})=B\]root.color=BLACK
레드-블랙 트리의 루트는 검은색이어야 합니다.

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으로 다르므로 위반입니다.

\[\operatorname{SH}(\mathrm{nil})=0\]SH(nil)=0
이 강의에서는 NIL 자체를 검은 높이 수치에 더하지 않습니다.
\[\#B(27\to18\to21\to\mathrm{nil})=1\]black(27-18-21)=1
해당 경로에서 검은 내부 노드는 18 하나뿐입니다.
\[\#B(27\to18\to9\to12\to\mathrm{nil})=3\]black(27-18-9-12)=3
해당 경로에는 검은 내부 노드가 세 개 있습니다.

실제 문제의 단계별 풀이와 정답

실제 시험 문제를 한 단계씩 풀기

각 단계의 질문에 먼저 답한 뒤 바로 아래 설명과 대조하세요.

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

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

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

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

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

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

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

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

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

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

레드-블랙 트리(Red-Black Tree)가 아님

이 페이지의 강의 convention: NIL은 black이지만 \(\text{SH}(\text{nil})=0\)SH(nil)=0이며, path 수치에는 실제 black 내부 node만 센다.

6.1(a) · 위반 경로와 검은 높이(SH) 표시
3R9B\(\text{SH}=\text{mismatch}\)SH=mismatch아래12B\(\text{SH}=1\)SH=118B\(\text{SH}=\text{mismatch}\)SH=mismatch21R\(\text{SH}=0\)SH=027R29B36B42B59R68B

최소 반례 또는 유효성을 보이는 증명 경로

증명 또는 반례 경로방문 노드판정 근거
짧은 path\(27 \to 18 \to 21\)27 → 18 → 21검은 내부 노드=[18] · 강의 규약의 개수=1
긴 path\(27 \to 18 \to 9 \to 12\)27 → 18 → 9 → 12검은 내부 노드=[18, 9, 12] · 강의 규약의 개수=3

규칙별 판정표

검사 규칙결과판정 이유
이진 탐색 트리 순서통과모든 왼쪽 key는 작고 오른쪽 key는 큽니다.
루트는 검정색실패root 27이 red rectangle입니다.
빨강 노드가 연속되지 않음통과red 27의 children 18,36은 black이고 다른 red node도 black children을 가집니다.
모든 경로의 검정 높이는 동일실패강의 \(\text{SH}(\text{nil})=0\)SH(nil)=0기준으로 \(27\to 18\to 21\)27→18→21은 black 1개\((18), 27\to 18\to 9\to 12\)(18), 27→18→9→12는 black 3개(18,9,12)입니다.
실제 풀이를 마친 뒤

답이 맞는지 스스로 검산

  1. JSON witness의 \(\text{black}_{\text{nodes}}\)black(nodes)길이가 각각 \(\text{course}_{\text{count}} 1\)course(count) 1과3과 같은지 확인하고 NIL을 목록에 넣지 않습니다.
  2. root 27의 children 18과36은 black이므로 root red 자체는 red-red 위반이 아니라 별도의 root-color 위반임을 구분합니다.
  3. 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.

초보자가 자주 틀리는 지점

  • 사각형과 원의 색을 반대로 읽는다.
  • root 규칙 위반 뒤 위치를 쓰지 않는다.
  • black-height에서 red node도 센다.
  • NIL은 black이라는 색 속성과 \(\text{SH}(\text{nil})=0\)SH(nil)=0이라는 수치 convention을 혼동한다.
1P

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

독립 학습 안내: 앞 소문항을 읽지 않았어도 이 절의 문제 입력과 개념 설명부터 따라갈 수 있습니다.

먼저 문제를 정확히 읽기

복기 문언의 소문항별 재구성

공식 원문 인용이 아니라 비공식 시험 복기의 요구를 소문항별로 재구성한 문장입니다.

한국어 문제 뜻

Tree 2가 Red-Black Tree인지 판정하고, 아니면 위반한 속성과 위치를 최소 하나 정확히 쓰시오.

답안에 반드시 포함할 요소

  • Ja/Nein 판정
  • BST·색 규칙을 분리한 검사
  • 위반 node의 ancestor 허용 범위
재구성된 독일어 문장 보기 (Deutsch)

Entscheiden Sie, ob Baum 2 ein Rot-Schwarz-Baum ist. Begründen Sie die Antwort und lokalisieren Sie mindestens eine verletzte Eigenschaft.

6.1(b) 후보 트리 · 해설 표식 없는 입력
2R · 빨강 사각형4B · 검정 원3R · 빨강 사각형7B · 검정 원9B · 검정 원10R · 빨강 사각형11R · 빨강 사각형12B · 검정 원

문제의 정체를 한 문장으로

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도 맞습니다. 이 때문에 색만 검사하면 오답이 됩니다.

이 소문항만 읽어도 되는 연결 강의

왜 이 개념이 필요한가

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

이 절을 읽고 나면 다음을 할 수 있어야 합니다.

  • RB tree가 BST의 특수형임을 말하고 key order와 color balance를 별도 축으로 검사할 수 있습니다.
  • node 3의 단순 parent 비교와 ancestor 범위 (4,7)를 이용해 최소 BST witness를 제시할 수 있습니다.
  • 나머지 color 규칙이 통과해도 하나의 필수 규칙 실패가 전체 verdict를 false로 만든다고 설명할 수 있습니다.

풀이 전에 꼭 알아야 할 말

부분 트리 전체의 이진 탐색 순서(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입니다.

조상의 허용 범위(ancestor bound)로 3의 위치 확인
  1. 7에서 왼쪽으로 이동

    이후 모든 key의 upper bound는 7입니다.

  2. 4에서 오른쪽으로 이동

    이후 모든 key의 lower bound는 4입니다.

  3. 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만 검사합니다.

  1. 10에서 오른쪽으로 이동

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

    이 단계의 상태: \(\text{range}=(10,+\infty)\)range=(10,+∞)

  2. 15에서 왼쪽으로 이동

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

    이 단계의 상태: \(\text{range}=(10,15)\)range=(10,15)

  3. 8 검사

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

    이 단계의 상태: 8∉\((10,15) \to \text{invalid}\)(10,15) → invalid

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

정확한 개념 설명 · 0부터 차근차근

0단계 · RB는 BST의 특수형

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

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

\[\{\text{레드-블랙 트리}\}\subset\{\text{이진 탐색 트리}\}\]RB tree ⊂ BST
모든 레드-블랙 트리는 먼저 이진 탐색 트리여야 합니다.

1단계 · local edge 반례

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

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

\[3\in T_{\mathrm{right}}(4)\quad\text{이지만}\quad3<4\]3 is right of 4 but 3<4
4의 오른쪽 부분 트리에 더 작은 키 3이 있어 BST 순서를 위반합니다.

2단계 · 나머지 규칙 검산

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

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

\[\text{유효}\iff\bigwedge_i R_i\]all rules must hold
모든 필수 규칙을 동시에 만족해야 유효합니다.

실제 문제의 단계별 풀이와 정답

실제 시험 문제를 한 단계씩 풀기

각 단계의 질문에 먼저 답한 뒤 바로 아래 설명과 대조하세요.

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

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

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

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

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

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

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

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

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

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

레드-블랙 트리(Red-Black Tree)가 아님

이 페이지의 강의 convention: NIL은 black이지만 \(\text{SH}(\text{nil})=0\)SH(nil)=0이며, path 수치에는 실제 black 내부 node만 센다.

6.1(b) · 위반 경로와 검은 높이(SH) 표시
2R\(\text{SH}=0\)SH=04B\(\text{SH}=1\)SH=13R\(\text{SH}=0\)SH=07B\(\text{SH}=2\)SH=29B\(\text{SH}=1\)SH=110R11R\(\text{SH}=1\)SH=112B\(\text{SH}=1\)SH=1

최소 반례 또는 유효성을 보이는 증명 경로

증명 또는 반례 경로방문 노드판정 근거
항목 (BST local witness)\(7 \to 4 \to 3\)7 → 4 → 3허용 범위=(4,7) · 실제 키=3
항목 (color-height sample)\(7 \to 4 \to 2\)7 → 4 → 2검은 내부 노드=[7, 4] · 강의 규약의 개수=2
항목 (right sample)\(7 \to 11 \to 9 \to 10\)7 → 11 → 9 → 10검은 내부 노드=[7, 9] · 강의 규약의 개수=2

규칙별 판정표

검사 규칙결과판정 이유
이진 탐색 트리 순서실패3은 4의 right child인데 \(3<4\)3<4입니다.
루트는 검정색통과root 7은 black circle입니다.
빨강 노드가 연속되지 않음통과red 2,3,11,10은 red child를 갖지 않습니다.
모든 경로의 검정 높이는 동일통과강의 \(\text{SH}(\text{nil})=0\)SH(nil)=0기준으로 모든 terminal path는 black internal node 두 개를 지납니다.
실제 풀이를 마친 뒤

답이 맞는지 스스로 검산

  1. Tree 2의 inorder [2,4,3,7,9,10,11,12]가 4 다음 3에서 감소하므로 같은 BST 위반을 독립적으로 확인합니다.
  2. 두 sample path의 \(\text{course}_{\text{count}}\)course(count)가 모두 2이고 NIL을 추가하지 않았는지 확인합니다.
  3. 오직 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.

초보자가 자주 틀리는 지점

  • 색과 black-height만 검사한다.
  • parent-child 한 edge의 key 위반을 놓친다.
  • 한 규칙이 맞으면 전체가 맞다고 결론 낸다.
  • BST 검사에서 node의 전체 허용 범위 대신 색을 본다.
1P

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

독립 학습 안내: 앞 소문항을 읽지 않았어도 이 절의 문제 입력과 개념 설명부터 따라갈 수 있습니다.

먼저 문제를 정확히 읽기

복기 문언의 소문항별 재구성

공식 원문 인용이 아니라 비공식 시험 복기의 요구를 소문항별로 재구성한 문장입니다.

한국어 문제 뜻

Tree 3이 Red-Black Tree인지 판정하시오. 맞다면 BST와 모든 Red-Black 속성이 성립함을 근거와 함께 쓰시오.

답안에 반드시 포함할 요소

  • Ja/Nein 판정
  • BST·root·red-red·Schwarzhöhe 전 항목
  • positive proof의 bottom-up SH 근거
재구성된 독일어 문장 보기 (Deutsch)

Entscheiden Sie, ob Baum 3 ein Rot-Schwarz-Baum ist. Bei einer positiven Antwort geben Sie an, welche Eigenschaften gelten.

6.1(c) 후보 트리 · 해설 표식 없는 입력
1B · 검정 원3R · 빨강 사각형4B · 검정 원9B · 검정 원11B · 검정 원13B · 검정 원15B · 검정 원16B · 검정 원17B · 검정 원18R · 빨강 사각형19B · 검정 원21R · 빨강 사각형23B · 검정 원24B · 검정 원27B · 검정 원

문제의 정체를 한 문장으로

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에서는 만족한 속성을 명시하라는 문제 요구가 있으므로 체크리스트 전 항목을 짧게 확인합니다.

이 소문항만 읽어도 되는 연결 강의

왜 이 개념이 필요한가

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

이 절을 읽고 나면 다음을 할 수 있어야 합니다.

  • positive RB 판정에서 BST·root·red-red·equal black-height를 모두 명시할 수 있습니다.
  • red node 3,21,18의 children을 빠짐없이 확인하고 R-R edge가 없음을 설명할 수 있습니다.
  • 각 node의 두 child SH를 bottom-up으로 맞춰 전체 terminal path의 course count 3을 증명할 수 있습니다.

풀이 전에 꼭 알아야 할 말

모든 규칙을 확인하는 유효성 증명(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 check)

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

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

모든 노드에 SH를 붙인 유효성 인증서(positive certificate)
  1. 이진 탐색 순서와 검정 루트 13(B)

    inorder가 정렬되고 root가 black입니다.

  2. 빨간 노드(R): 3, 21, 18

    세 red node의 child가 모두 black internal node 또는 NIL입니다.

  3. 루트의 검은 높이 \(\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으로 검사합니다.

  1. 종료 지점(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

  2. 빨간 노드 5의 값 계산

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

    이 단계의 상태: \(\text{SH}(5)=1\)SH(5)=1

  3. 루트 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를 만족할 수 있습니다.

정확한 개념 설명 · 0부터 차근차근

0단계 · positive proof

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

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

\[\text{유효}\iff\text{모든 레드-블랙 규칙이 참}\]valid ⇔ every RB rule holds
규칙 하나라도 거짓이면 레드-블랙 트리가 아닙니다.

1단계 · red node 검사

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

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

\[\begin{aligned}\operatorname{color}(v)=R&\Longrightarrow\operatorname{color}(v.left)=B\\&\phantom{\Longrightarrow}\land\operatorname{color}(v.right)=B\end{aligned}\]R parent ⇒ children B
빨간 노드의 두 자식은 검어야 합니다.

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로 확인하면 모든 경로를 빠짐없이 증명할 수 있습니다.

\[\operatorname{SH}(\mathrm{nil})=0\]SH(nil)=0
이 강의에서는 NIL 자체를 검은 높이 수치에 더하지 않습니다.
\[\#B(\operatorname{root}\leadsto\mathrm{nil})=3\]root-to-terminal black count=3
모든 루트-종료 경로의 검은 내부 노드 수가 3으로 같습니다.

실제 문제의 단계별 풀이와 정답

실제 시험 문제를 한 단계씩 풀기

각 단계의 질문에 먼저 답한 뒤 바로 아래 설명과 대조하세요.

  1. Tree 3은 BST인가?

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

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

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

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

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

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

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

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

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

유효한 레드-블랙 트리(Red-Black Tree)

이 페이지의 강의 convention: NIL은 black이지만 \(\text{SH}(\text{nil})=0\)SH(nil)=0이며, path 수치에는 실제 black 내부 node만 센다.

6.1(c) · 위반 경로와 검은 높이(SH) 표시
1B\(\text{SH}=1\)SH=13R\(\text{SH}=1\)SH=14B\(\text{SH}=1\)SH=19B\(\text{SH}=2\)SH=211B\(\text{SH}=1\)SH=113B\(\text{SH}=3\)SH=315B\(\text{SH}=1\)SH=116B\(\text{SH}=2\)SH=217B\(\text{SH}=1\)SH=118R\(\text{SH}=1\)SH=119B\(\text{SH}=1\)SH=121R\(\text{SH}=2\)SH=223B\(\text{SH}=1\)SH=124B\(\text{SH}=2\)SH=227B\(\text{SH}=1\)SH=1

최소 반례 또는 유효성을 보이는 증명 경로

증명 또는 반례 경로방문 노드판정 근거
항목 (left short)\(13 \to 9 \to 11\)13 → 9 → 11검은 내부 노드=[13, 9, 11] · 강의 규약의 개수=3
항목 (left long)\(13 \to 9 \to 3 \to 1\)13 → 9 → 3 → 1검은 내부 노드=[13, 9, 1] · 강의 규약의 개수=3
항목 (right via 16)\(13 \to 21 \to 16 \to 15\)13 → 21 → 16 → 15검은 내부 노드=[13, 16, 15] · 강의 규약의 개수=3
항목 (right via 24)\(13 \to 21 \to 24 \to 23\)13 → 21 → 24 → 23검은 내부 노드=[13, 24, 23] · 강의 규약의 개수=3

규칙별 판정표

검사 규칙결과판정 이유
이진 탐색 트리 순서통과모든 subtree key가 올바른 범위에 있습니다.
루트는 검정색통과root 13은 black입니다.
빨강 노드가 연속되지 않음통과red 3의 children 1,4; red 21의 children 16,24; red 18의 children 17,19가 모두 black입니다.
모든 경로의 검정 높이는 동일통과예: 13-9-11, 13-9-3-1, 13-21-16-15, 13-21-24-23 모두 black internal node 수가 3입니다.
실제 풀이를 마친 뒤

답이 맞는지 스스로 검산

  1. \(\text{witness}_{\text{paths}}\)witness(paths)네 행의 \(\text{black}_{\text{nodes}}\)black(nodes)길이가 모두 \(\text{course}_{\text{count}} 3\)course(count) 3인지 자동 확인합니다.
  2. \(\text{sh}_{\text{labels}}\)sh(labels)를 bottom-up으로 계산할 때 모든 internal node의 left/right child SH가 같고 root label이 3인지 확인합니다.
  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.

초보자가 자주 틀리는 지점

  • 참이라고만 쓰고 속성을 열거하지 않는다.
  • 일부 경로만 보고 black-height를 단정한다.
  • red 18을 놓친다.
  • NIL의 black 색과 \(\text{SH}(\text{nil})=0\)SH(nil)=0수치를 혼동한다.
1P

6.1(d) · 후보 트리 4 · 레드-블랙 트리 판정

독립 학습 안내: 앞 소문항을 읽지 않았어도 이 절의 문제 입력과 개념 설명부터 따라갈 수 있습니다.

먼저 문제를 정확히 읽기

복기 문언의 소문항별 재구성

공식 원문 인용이 아니라 비공식 시험 복기의 요구를 소문항별로 재구성한 문장입니다.

한국어 문제 뜻

Tree 4가 Red-Black Tree인지 판정하시오. 아니라면 위반 규칙과 정확한 node 또는 path 위치를 최소 하나 쓰시오.

답안에 반드시 포함할 요소

  • Ja/Nein 판정
  • 최소 한 개의 정확한 violation witness
  • BST bound와 Schwarzhöhe를 분리한 설명
재구성된 독일어 문장 보기 (Deutsch)

Entscheiden Sie, ob Baum 4 ein Rot-Schwarz-Baum ist. Begründen Sie die Antwort und nennen Sie mindestens eine verletzte Eigenschaft samt Position.

6.1(d) 후보 트리 · 해설 표식 없는 입력
4B · 검정 원11B · 검정 원6B · 검정 원7R · 빨강 사각형9B · 검정 원68B · 검정 원74B · 검정 원86R · 빨강 사각형89B · 검정 원92R · 빨강 사각형96B · 검정 원97R · 빨강 사각형

문제의 정체를 한 문장으로

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에는 최소 한 위반만 요구되지만 두 위반을 정확히 쓰면 판정이 더 견고합니다.

이 소문항만 읽어도 되는 연결 강의

왜 이 개념이 필요한가

한 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 하나가 끝납니다.

서로 독립된 위반 규칙(independent violation)

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

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

BST 위험 간선과 SH 불일치 경로를 동시에 표시
  1. 7 ∉ (11,68)

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

  2. 74를 지나는 경로: 검은 노드 3개

    68,89,74를 세고 red86과 NIL은 더하지 않습니다.

  3. 비어 있는 오른쪽 경로: 검은 노드 2개

    68,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만 검사합니다.

  1. 비어 있는 오른쪽 경로의 검은 노드 세기

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

    이 단계의 상태: 10-20-30-right: count 2

  2. 왼쪽 자식 경로의 검은 노드 세기

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

    이 단계의 상태: 10-20-30-25: count 3

  3. 경로 개수 불일치 판정

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

    이 단계의 상태: 2≠\(3 \to \text{invalid}\)3 → invalid

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

정확한 개념 설명 · 0부터 차근차근

0단계 · 두 축을 분리

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

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

\[\text{유효}=\text{BST 키 순서}\land\text{색 규칙}\]BST check + color check
키 순서와 색 규칙을 모두 검사해야 합니다.

1단계 · 7의 범위

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

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

\[x\in T_{\mathrm{right}}(11)\Rightarrow x>11,\qquad7<11\]right of 11 ⇒ key>11; but 7<11
오른쪽 부분 트리의 7이 조상 11의 범위를 위반합니다.

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을 더하지 않습니다.

\[\operatorname{SH}(\mathrm{nil})=0\]SH(nil)=0
이 강의에서는 NIL 자체를 검은 높이 수치에 더하지 않습니다.
\[\#B(51\to74\to\cdots\to\mathrm{nil})=3\]black(left via 74)=3
74를 지나는 쪽 경로의 검은 내부 노드 수입니다.
\[\#B(51\to\text{오른쪽 NIL})=2\]black(right missing)=2
대응하는 짧은 경로는 검은 내부 노드가 두 개뿐입니다.

실제 문제의 단계별 풀이와 정답

실제 시험 문제를 한 단계씩 풀기

각 단계의 질문에 먼저 답한 뒤 바로 아래 설명과 대조하세요.

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

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

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

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

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

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

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

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

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

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

레드-블랙 트리(Red-Black Tree)가 아님

이 페이지의 강의 convention: NIL은 black이지만 \(\text{SH}(\text{nil})=0\)SH(nil)=0이며, path 수치에는 실제 black 내부 node만 센다.

6.1(d) · 위반 경로와 검은 높이(SH) 표시
4B\(\text{SH}=1\)SH=111B\(\text{SH}=2\)SH=26B\(\text{SH}=1\)SH=17R\(\text{SH}=1\)SH=19B\(\text{SH}=1\)SH=168B\(\text{SH}=\text{mismatch}\)SH=mismatch74B\(\text{SH}=1\)SH=186R\(\text{SH}=\text{mismatch}\)SH=mismatch89B\(\text{SH}=\text{mismatch}\)SH=mismatch92R\(\text{SH}=0\)SH=096B\(\text{SH}=1\)SH=197R\(\text{SH}=0\)SH=0

최소 반례 또는 유효성을 보이는 증명 경로

증명 또는 반례 경로방문 노드판정 근거
항목 (BST witness)\(68 \to 11 \to 7\)68 → 11 → 7허용 범위=(11,68) · 실제 키=7
항목 (86 missing side)\(68 \to 89 \to 86\)68 → 89 → 86검은 내부 노드=[68, 89] · 강의 규약의 개수=2
항목 (86 via 74)\(68 \to 89 \to 86 \to 74\)68 → 89 → 86 → 74검은 내부 노드=[68, 89, 74] · 강의 규약의 개수=3

규칙별 판정표

검사 규칙결과판정 이유
이진 탐색 트리 순서실패7은 11의 right subtree인데 \(7<11\)7<11입니다.
루트는 검정색통과root 68은 black입니다.
빨강 노드가 연속되지 않음통과red 7,86,92,97의 children은 black 또는 NIL입니다.
모든 경로의 검정 높이는 동일실패강의 \(\text{SH}(\text{nil})=0\)SH(nil)=0기준 68-89-86의 빈 right 방향은 black 2개(68,89), 74 방향은 3개(68,89,74)입니다.
실제 풀이를 마친 뒤

답이 맞는지 스스로 검산

  1. BST inorder가 11의 right 위치에서 7 때문에 감소하는지 확인하고 \(\text{allowed}_{\text{interval}} (11,68)\)allowed(interval) (11,68)과 actual7을 대조합니다.
  2. 두 SH witness의 \(\text{black}_{\text{nodes}}\)black(nodes)길이가 각각 \(\text{course}_{\text{count}2}\)course(count)2와3인지 확인합니다.
  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로 센다.
4P

6.2 · \(t=2 B-\)t=2 B-트리 · 16, 30, 40 순차 삽입

독립 학습 안내: 앞 소문항을 읽지 않았어도 이 절의 문제 입력과 개념 설명부터 따라갈 수 있습니다.

먼저 문제를 정확히 읽기

복기 문언의 소문항별 재구성

공식 원문 인용이 아니라 비공식 시험 복기의 요구를 소문항별로 재구성한 문장입니다.

한국어 문제 뜻

주어진 \(\text{Grad} t=2 B-\text{Tree}\)Grad t=2 B-Tree에 16, 30, 40을 순서대로 삽입하시오. 강의의 ‘검색하며 미리 split’ 알고리즘을 사용하고 각 삽입 뒤 중간 결과를 그리시오.

답안에 반드시 포함할 요소

  • \(t=2\)t=2용량과 root special case
  • 16·30·40 각각 삽입 뒤 tree
  • split·median promotion·child interval 선택 근거
재구성된 독일어 문장 보기 (Deutsch)

Betrachten Sie den gegebenen B-Baum mit Grad t=2. Fügen Sie der Reihe nach 16, 30 und 40 mit dem informellen Algorithmus Suchen und Splitten ein und skizzieren Sie das Zwischenergebnis nach jeder Einfügeoperation.

문제 입력 · 초기 \(t=2 B-\text{Tree} (\)t=2 B-Tree (해설 표식 없음)
13415172223265052025

문제의 정체를 한 문장으로

B-Tree node는 여러 sorted key와 여러 child interval을 가집니다. 최소차수 \(t=2\)t=2이면 non-root node는 1~3개의 key를 가질 수 있고 full node는 \(2t-1=3\)2t-1=3개입니다.

강의의 top-down insertion은 full node 안으로 내려가지 않습니다. child가 full이면 먼저 median을 parent로 올려 split한 뒤 올바른 half로 내려갑니다.

초기 root [5,20,25]가 이미 full이므로 16을 넣기 전에 root부터 split해야 합니다.

이 소문항만 읽어도 되는 연결 강의

왜 이 개념이 필요한가

B-Tree는 한 node에 key가 여러 개 있고 child도 여러 개라 binary tree와 읽는 법이 다릅니다. capacity, interval, preemptive split을 함께 이해해야 key를 4개로 overflow시키지 않고 각 삽입 뒤 올바른 multiway structure를 그릴 수 있습니다.

이 절을 읽고 나면 다음을 할 수 있어야 합니다.

  • \(t=2\)t=2에서 root·non-root key 수와 \(k \text{keys}\to k+1 \text{children}\)k keys→k+1 children규칙을 말할 수 있습니다.
  • full root 또는 full child를 내려가기 전에 split하고 median을 parent로 promotion할 수 있습니다.
  • promotion 뒤 target key를 다시 비교해 올바른 child interval을 선택하고 네 invariant로 검산할 수 있습니다.

풀이 전에 꼭 알아야 할 말

B-트리 노드와 키 구간(key interval)

한 node의 sorted keys가 수직 경계처럼 child 구간을 나눕니다. k keys를 가진 internal node는 k+1 children을 가지며 각 child의 모든 key가 해당 interval 안에 있어야 합니다.

아주 작은 예: [25,30]은 \(\text{children} (<25), (25,30), (>30)\)children (<25), (25,30), (>30)세 개를 가집니다.

차수 \(t=2\)t=2와 가득 찬 노드(full node)

non-root node는 최소 \(t-1=1,\)t-1=1,최대 \(2t-1=3 \text{keys}\)2t-1=3 keys입니다. 3 keys인 node는 valid하지만 full이라 그 안으로 더 내려가기 전 split해야 합니다.

아주 작은 예: [26,30,50]은 overflow가 아니라 full이고 다음 40 전에 split합니다.

노드 분할과 키 승격(split and promotion)

full [a,b,c]의 median b를 parent로 이동시키고 [a]와 [c] 두 node를 만듭니다. median을 child에 복사해 남기지 않으며 child pointers도 두 묶음으로 나눕니다.

아주 작은 예: [26,30,50] → [26] ↑30 [50]입니다.

모든 잎(leaves)의 깊이가 같음

B-Tree는 balanced multiway search tree라 어느 leaf까지 내려가도 depth가 같습니다. root split은 새 root를 만들어 모든 기존 leaf depth를 동시에 한 단계 늘립니다.

아주 작은 예: 한쪽 branch만 더 깊어지도록 leaf child를 임의로 추가하면 invalid입니다.

연결선으로 읽는 6단계 분할 과정(split sequence)
  1. 1–2단계: 가득 찬 루트 분할(root split)

    20이 promotion되고 [5], [25]가 새 root의 children이 됩니다.

  2. 3–4단계: 16과 30 삽입

    interval을 따라 두 leaf가 각각 [15,16,17], [26,30,50]이 됩니다.

  3. 5–6단계: 자식 분할 후 40 삽입

    30 promotion 뒤 새 \((>30) \text{child} [50]\)(>30) child [50]에 40을 넣어 [40,50]을 만듭니다.

각 SVG는 connector를 먼저 그린 뒤 node box를 올립니다. promotion key는 amber, target insertion은 green, 위험한 full node는 red border로 표시합니다.

작은 예제로 먼저 연습 · root [10,20,30]에 25 삽입

\(t=2\)t=2이고 leaf root [10,20,30]이 full인 가장 작은 B-Tree에 key25를 삽입합니다.

  1. 가득 찬 루트(full root) 확인

    \(3=2t-1 \text{keys}\)3=2t-1 keys이므로 25를 직접 넣으면 4 keys overflow가 됩니다.

    이 단계의 상태: [10,20,30] FULL

  2. 루트 분할(root split)

    median20을 새 root로 올리고 children [10]과 [30]을 만듭니다.

    이 단계의 상태: [10] ← \([20] \to [30]\)[20] → [30]

  3. 25가 정한 자식 구간(interval) 선택

    \(25>20\)25>20이므로 right child [30]으로 내려가 sorted 위치에 삽입합니다.

    이 단계의 상태: root[20], right[25,30]

작은 예제의 결론: top-down insertion은 full node 안으로 들어가지 않으므로 한 번 내려가는 동안 어떤 node도 4 keys가 되지 않습니다.

정확한 개념 설명 · 0부터 차근차근

0단계 · \(t=2\)t=2용량

각 node는 최대 3 keys, root가 아닌 node는 최소 1 key입니다. 내부 node에 k keys가 있으면 k+1 children이 key interval을 담당합니다.

모든 leaves는 같은 depth에 있어야 합니다.

\[k_{\min}=t-1=1\]min keys=t-1=1
\(t=2\)t=2인 비루트 노드는 최소 한 개의 키를 가집니다.
\[k_{\max}=2t-1=3\]max keys=2t-1=3
\(t=2\)t=2인 노드는 최대 세 개의 키를 가집니다.
\[\#\mathrm{children}=k+1\]children=k+1
키가 k개인 내부 노드는 자식을 k+1개 가져야 합니다.

1단계 · split

full [a,b,c]를 split하면 median b가 parent로 올라가고 left [a], right [c]가 됩니다. leaf가 아니라면 child pointers도 앞 t개와 뒤 t개로 나눕니다.

split은 key를 복사해 남기는 것이 아니라 median을 parent로 이동시킵니다.

\[[a,b,c]\;\Longrightarrow\;[a]\quad\overset{\uparrow}{b}\quad[c]\][a,b,c] ⇒ [a] ↑b [c]
가운데 키 b를 부모로 승격하고 양쪽 키를 두 자식으로 나눕니다.

2단계 · 루트 분할(root split)

초기 root [5,20,25]를 split해 새 root [20], left internal [5], right internal [25]를 만듭니다.

기존 네 leaf children은 [5] 아래 두 개와 [25] 아래 두 개로 정확히 분배합니다.

\[\operatorname{root}_{\mathrm{new}}=[20]\]new root=[20]
가득 찬 초기 루트를 분할하면 20이 새 루트가 됩니다.

3단계 · 삽입 실행 시간(runtime)

각 level에서 node 안 key 위치를 찾고 필요하면 constant-number pointer split을 수행하며 height만큼 내려갑니다. 강의 RAM 모델에서는 \(O(t\cdot h)\)O(t·h), 고정 t이면 \(O(\log n)\)O(log n)입니다.

B-Tree는 node를 disk block에 맞춰 큰 t로 사용해 I/O 횟수를 줄이는 목적도 있습니다.

\[h=\Theta(\log_t n)\]h=Θ(log_t n)
B-트리 높이는 키 수에 대해 로그 규모입니다.
\[T_{\mathrm{insert}}=O(t\cdot h)\]insert=O(t·h)
각 높이에서 최대 t 규모의 노드 안을 살피는 표기입니다.

실제 문제의 단계별 풀이와 정답

실제 시험 문제를 한 단계씩 풀기

각 단계의 질문에 먼저 답한 뒤 바로 아래 설명과 대조하세요.

  1. 16 전에 가장 먼저 해야 할 일은 무엇인가?

    초기 root [5,20,25]가 full이므로 median20을 새 root로 promotion하고 [5]와 [25]로 split합니다.

  2. 16은 어느 child interval로 가는가?

    \(16<20\)16<20이고 \(16>5\)16>5이므로 [5] internal node의 right child [15,17]에 들어가 [15,16,17]이 됩니다.

  3. 30 삽입 뒤 무엇이 full이 되는가?

    \(30>20,30>25\)30>20,30>25라 leaf [26,50]에 들어가 [26,30,50]이 되고 이 leaf가 full이 됩니다.

  4. 40을 넣기 전에 왜 split하는가?

    내려갈 child [26,30,50]이 이미 3 keys full이므로 직접 40을 넣지 않고 median30을 parent로 먼저 올립니다.

  5. promotion 뒤 40의 최종 위치는 어디인가?

    parent [25,30]에서 \(40>30\)40>30이라 new right child [50]을 선택하고 sorted insert해 [40,50]을 만듭니다.

  6. 최종 tree를 어떻게 검산하는가?

    모든 node key 정렬, 1~3 keys, k+1 children, 동일 leaf depth, child interval order 다섯 항목을 검사합니다.

여섯 세부 상태 · 분할과 삽입을 따로 보기

호박색 \(\text{key} = \text{parent}\)key = parent로 승격초록색 \(\text{key} =\)key =이번 단계에 삽입빨간 테두리 = 현재 full node

1 · 초기 root full 확인

동작: [5,20,25]는 3 keys라 full

왜: \(t=2\)t=2의 최대 key 수 \(2t-1=3\)2t-1=3이므로 내려가기 전에 root special case를 적용합니다.

검산: 현재 node key 정렬·leaf depth는 유효하지만 새 key를 직접 넣으면 4 keys가 됩니다.

1 · 초기 root full 확인
13415172223265052025

2 · 루트 분할과 20 승격(root split, promotion)

동작: 가운데 키(median) 20을 새 루트로 올림

왜: [5,20,25]를 [5]와 [25]로 나누고 기존 child pointer 두 개씩을 각 half에 붙입니다.

검산: 새 root [20], 모든 non-root node 1~3 keys, leaf depth 2로 동일합니다.

2 · 루트 분할과 20 승격(root split, promotion)
13415175222326502520

3 · 구간(interval) (5,20)에 16 삽입

동작: \([15,17] \to [15,16,17]\)[15,17] → [15,16,17]

왜: \(16<20\)16<20에서 \(\text{left} \text{internal} [5], 16>5\)left internal [5], 16>5에서 right child interval (5,20)을 선택합니다.

검산: leaf는 sorted 3 keys로 full이지만 overflow가 아니며 모든 leaf depth가 같습니다.

3 · 구간(interval) (5,20)에 16 삽입
1341516175222326502520

4 · 구간(interval) (25,+∞)에 30 삽입

동작: \([26,50] \to [26,30,50]\)[26,50] → [26,30,50]

왜: \(30>20, 30>25\)30>20, 30>25이므로 오른쪽 끝 leaf를 선택하고 sorted 위치에 30을 넣습니다.

검산: node가 정확히 3 keys로 full이지만 아직 2t-1 한계를 넘지 않습니다.

4 · 구간(interval) (25,+∞)에 30 삽입
134151617522232630502520

5 · 40 삽입 전 가득 찬 자식 분할(full child split)

동작: [26,30,50]을 [26] ↑30 [50]로 분할

왜: 40이 내려갈 child가 full이므로 먼저 median30을 parent [25]로 promotion해 [25,30]을 만듭니다.

검산: parent는 2 keys·3 children이고 child interval은 \((<25),(25,30),(>30)\)(<25),(25,30),(>30)으로 정확합니다.

5 · 40 삽입 전 가득 찬 자식 분할(full child split)
134151617522232650253020

6 · 새 오른쪽 구간에 40 삽입(new right interval)

동작: \([50] \to [40,50]\)[50] → [40,50]

왜: promotion 뒤 \(40>30\)40>30이므로 새 right child를 다시 선택해 sorted 위치에 넣습니다.

검산: 모든 node 1~3 keys, k keys에 k+1 children, 모든 leaves 동일 depth, 모든 interval order가 성립합니다.

6 · 새 오른쪽 구간에 40 삽입(new right interval)
13415161752223264050253020

시험 답안에 남길 세 checkpoint

루트 분할(root split) 후 16 삽입

[5,20,25]를 split해 root [20]을 만든다. \(16<20\)16<20이므로 left [5]의 right leaf [15,17]에 넣어 [15,16,17].

루트 분할(root split) 후 16 삽입
1341516175222326502520

30 삽입

\(30>20, 30>25\)30>20, 30>25이므로 leaf [26,50]에 넣어 [26,30,50].

30 삽입
134151617522232630502520

40 삽입

내려갈 child [26,30,50]이 full이므로 먼저 split하고 median 30을 parent로 올려 [25,30]을 만든다. 40은 new right leaf [50]에 들어가 [40,50].

40 삽입
13415161752223264050253020
실제 풀이를 마친 뒤

답이 맞는지 스스로 검산

  1. 여섯 microstate 각각에서 node key가 sorted이고 key 수가 1~3인지 검사합니다.
  2. internal node마다 children 수가 keys 수+1이고 모든 child key가 parent가 정의한 interval 안에 있는지 재귀 검증합니다.
  3. 모든 leaf depth가 동일하며 promotion20과30이 원래 child에 중복으로 남지 않았는지 확인합니다.

30초 자가점검

[26,30,50]에 40을 먼저 넣어 네 key 뒤 split해도 되는가?

힌트: 강의의 Suchen und Splitten 순서를 떠올립니다.

정답: 아닙니다. 내려갈 child가 full이면 먼저 split하고 promotion 뒤 target을 다시 비교해 한 half로 내려갑니다.

[26,30,50] split에서 parent로 올라가는 key는 무엇인가?

힌트: sorted 세 key의 가운데를 고릅니다.

정답: median 30입니다. children은 [26]과 [50]이 되고 30은 parent [25]에 들어가 [25,30]이 됩니다.

시험 답안 템플릿

\(t=2\)t=2이므로 max 3 keys. 먼저 full root [5,20,25]를 split해 root [20], children [5],[25]를 만든다. \(16\to [15,16,17], 30\to [26,30,50]. 40\)16→[15,16,17], 30→[26,30,50]. 40삽입 전 이 full leaf를 split해 30을 parent로 올리고 [40,50]에 삽입한다.

초보자가 자주 틀리는 지점

  • full root에 16을 직접 넣어 4 keys를 만든다.
  • median 20을 child에도 남긴다.
  • internal split 때 child pointer를 잘못 배분한다.
  • 40을 먼저 넣어 4 keys를 만든 뒤 split한다.
  • 40 삽입 split에서 30 대신 26이나50을 올린다.
4P

6.3 · 이진 탐색 트리(BST)가 AVL인지 판정하는 재귀 알고리즘

독립 학습 안내: 앞 소문항을 읽지 않았어도 이 절의 문제 입력과 개념 설명부터 따라갈 수 있습니다.

먼저 문제를 정확히 읽기

복기 문언의 소문항별 재구성

공식 원문 인용이 아니라 비공식 시험 복기의 요구를 소문항별로 재구성한 문장입니다.

한국어 문제 뜻

root T가 주어진 BST가 AVL Tree인지 true/false로 판정하는 재귀 pseudocode 또는 Java code를 쓰고, T로 실제 호출하는 줄까지 제시하시오.

답안에 반드시 포함할 요소

  • 재귀 helper와 empty base case
  • 모든 node balance 검사
  • T를 사용한 실제 호출
재구성된 독일어 문장 보기 (Deutsch)

Schreiben Sie Pseudocode oder Java-Code eines rekursiven Algorithmus, der prüft, ob ein binärer Suchbaum mit Wurzel T auch ein AVL-Baum ist. Zeigen Sie den Aufruf mit T; mehrere Funktionen sind erlaubt.

AVL 알고리즘 입력 · 이미 이진 탐색 트리인 루트 T (해설 표식 없음)
T왼쪽 부분 트리높이 = ?오른쪽 부분 트리높이 = ?

문제의 정체를 한 문장으로

AVL Tree는 모든 node에서 왼쪽과 오른쪽 subtree 높이 차이가 최대 1인 BST입니다. 문제는 입력이 이미 BST라고 했으므로 핵심은 모든 node의 balance condition 검사입니다.

초보자 구현은 node마다 height를 새로 계산해 \(O(n^{2})\)O(n²)이 되기 쉽습니다. 더 좋은 방식은 postorder로 한 번만 순회하면서 각 subtree의 높이와 실패 여부를 parent에게 동시에 돌려주는 것입니다.

강의 \(\text{convention} \text{height}(\text{empty})=-1, \text{leaf}=0, B=\text{hR}-\text{hL}\)convention height(empty)=-1, leaf=0, B=hR-hL을 사용합니다. 유효한 높이 -1과 충돌하지 않도록 invalid는 숫자가 아닌 FAIL sentinel로 반환합니다.

이 소문항만 읽어도 되는 연결 강의

왜 이 개념이 필요한가

AVL 조건은 root 하나가 아니라 모든 node의 두 subtree height에 걸린 전역 조건입니다. 높이를 계산하는 재귀와 균형 판정을 한 번의 postorder에 합치면 같은 node를 반복 방문하지 않고 정확한 \(O(n)\)O(n) 검사를 만들 수 있습니다.

이 절을 읽고 나면 다음을 할 수 있어야 합니다.

  • 강의 \(\text{convention} H(\text{nil})=-1, \text{leaf}=0, B=\text{hR}-\text{hL}\)convention H(nil)=-1, leaf=0, B=hR-hL을 작은 tree에서 계산할 수 있습니다.
  • height 또는 FAIL을 반환하는 postorder helper를 읽고 child failure를 parent로 전파할 수 있습니다.
  • 구체 trace와 induction으로 correctness를 설명하고 \(\text{naive} O(n^{2})\)naive O(n²)와 one-pass \(O(n)\)O(n)을 구분할 수 있습니다.

풀이 전에 꼭 알아야 할 말

높이와 균형 인자(height and balance factor)

height는 현재 node에서 가장 깊은 leaf까지 edge 수이며 empty tree는 -1, leaf는0입니다. 강의 balance factor는 right height-left height입니다.

아주 작은 예: left height1, right height-1이면 \(B=-2\)B=-2라 left-heavy invalid입니다.

후위 순회 재귀(postorder recursion)

parent 값을 계산하려면 두 child 결과가 먼저 필요하므로 left, right, node 순서로 호출이 돌아옵니다. 각 호출은 자기 subtree 요약 하나를 parent에게 반환합니다.

아주 작은 예: leaf2가 height0을 반환한 뒤 parent5가 height1을 계산합니다.

실패를 나타내는 특별값(FAIL sentinel)

유효한 course height에는 -1도 포함되므로 invalid를 -1로 표현하면 empty tree와 충돌합니다. 숫자가 아닌 FAIL을 별도 결과로 사용합니다.

아주 작은 예: nil returns -1, unbalanced node10 returns FAIL입니다.

높이 h에 비례하는 재귀 스택(recursion stack)

동시에 활성화된 호출 수는 root에서 현재 node까지 path 길이에 비례합니다. 입력이 invalid한 skewed BST면 h가 n에 가까울 수도 있습니다.

아주 작은 예: 한쪽 사슬 tree에서는 stack이 \(O(n)\)O(n)까지 커질 수 있습니다.

\(2\to 5\to 10\)2→5→10으로 올라오는 후위 순회 반환값(postorder return)
  1. 노드 2: 높이 0 반환

    nil children -1,-1에서 \(B=0\)B=0이고 leaf height0입니다.

  2. 노드 5: 높이 1 반환

    \(\text{hL}=0,\text{hR}=-1,B=-1\)hL=0,hR=-1,B=-1이 허용되어 height1입니다.

  3. 노드 10: 실패(FAIL) 반환

    \(\text{hL}=1,\text{hR}=-1,B=-2\)hL=1,hR=-1,B=-2라 AVL condition을 위반합니다.

connector는 child에서 parent 방향의 반환을 나타내며 먼저 그립니다. node box에는 hL, hR, B, return을 짧게 표시하고 10의 FAIL을 risk color로 강조합니다.

작은 예제로 먼저 연습 · root10과 leaves5·15인 valid AVL

root10의 left leaf5와 right leaf15가 있는 BST를 course height convention으로 검사합니다.

  1. 두 잎(leaf)의 높이 계산

    각 leaf의 children은 nil height-1이라 \(B=0,\)B=0,반환 height는0입니다.

    이 단계의 상태: \(\text{return}(5)=0, \text{return}(15)=0\)return(5)=0, return(15)=0

  2. 루트의 균형 인자(balance) 계산

    \(\text{hR}0-\text{hL}0=0\)hR0-hL0=0은 허용 집합 {-1,0,1}에 있습니다.

    이 단계의 상태: \(B(10)=0\)B(10)=0

  3. 루트 높이와 최종 판정(verdict)

    \(1+\max(0,0)=1\)1+max(0,0)=1을 반환하며 FAIL이 아니므로 전체 tree는 AVL입니다.

    이 단계의 상태: \(\text{height}=1, \text{isAVL}=\text{true}\)height=1, isAVL=true

작은 예제의 결론: child height와 validity를 한 결과로 올리면 parent에서 균형과 실제 height를 동시에 정확히 결정할 수 있습니다.

정확한 개념 설명 · 0부터 차근차근

0단계 · AVL 정의와 강의 convention

모든 node v에서 \(B(v)=\text{height}(v.\text{right})-\text{height}(v.\text{left})\)B(v)=height(v.right)-height(v.left)이고 \(B(v)\in \{-1,0,+1\}\)B(v)∈{-1,0,+1}이어야 합니다. root만 검사해서는 안 되고 모든 subtree가 자체적으로 AVL이어야 합니다.

강의는 \(\text{empty} \text{tree} \text{height}=-1, \text{leaf} \text{height}=0\)empty tree height=-1, leaf height=0을 사용합니다. invalid는 유효 height -1과 다른 FAIL 값으로 둡니다.

\[H(\mathrm{nil})=-1\]H(nil)=-1
강의 높이 규약에서 빈 트리의 높이는 -1입니다.
\[B(v)=h_R-h_L\]B(v)=hR-hL
AVL 균형 인자는 오른쪽 높이에서 왼쪽 높이를 뺍니다.
\[\lvert B(v)\rvert\le1\]|B(v)|≤1
모든 노드에서 균형 인자의 절댓값이 1 이하여야 합니다.

1단계 · postorder

현재 node의 높이를 알려면 두 child 높이가 먼저 필요하므로 left, right, node 순서의 postorder가 자연스럽습니다.

child가 invalid라고 보고하면 parent는 추가 계산 없이 invalid를 위로 전달합니다.

\[H(v)=1+\max(h_L,h_R)\]height(v)=1+max(hL,hR)
두 자식 높이 중 큰 값에 1을 더해 현재 높이를 구합니다.

2단계 · FAIL sentinel

\(\text{heightOrFail}(\text{nil})=-1\)heightOrFail(nil)=-1입니다. left 또는 right 결과가 FAIL이면 즉시 FAIL을 위로 전달합니다. 둘 다 정상이어도 \(\text{abs}(\text{right}-\text{left})>1\)abs(right-left)>1이면 FAIL입니다.

그 외에는 실제 course height를 반환합니다. 최종 root 결과가 FAIL이 아니면 AVL입니다.

\[\mathrm{FAIL}\ne-1\]FAIL≠-1
실패 표식은 정상적인 빈 트리 높이 -1과 달라야 합니다.
\[\operatorname{heightOrFail}(T)\ne\mathrm{FAIL}\;\Longrightarrow\;T\text{는 AVL}\]result!=FAIL ⇒ AVL
루트 호출이 실패가 아니면 모든 하위 트리가 균형 조건을 통과했습니다.

3단계 · complexity와 흔한 \(O(n^{2})\)O(n²)

각 node를 최대 한 번 방문하고 constant work만 하므로 \(O(n)\)O(n), valid tree 등 worst case에는 모두 방문해 \(\Theta(n)\)Θ(n)입니다. recursion stack은 \(O(h)\)O(h)입니다.

isBalanced(v) 안에서 별도 height(v.left), height(v.right)를 매 node마다 다시 호출하면 사슬 tree에서 같은 node를 반복 방문해 \(\Theta(n^{2})\)Θ(n²)이 될 수 있습니다.

\[T(n)=\Theta(n)\quad\text{(최악의 경우)}\]worst-case Θ(n)
모든 노드를 한 번씩 확인하는 최악의 실행 시간입니다.
\[S(h)=O(h)\]stack O(h)
동시에 열린 재귀 호출 수는 트리 높이에 비례합니다.
\[\begin{aligned}T_{\mathrm{naive}}(n)&=\Theta(n^2)\\T_{\mathrm{one\ pass}}(n)&=\Theta(n)\end{aligned}\]naive Θ(n²), one-pass Θ(n)
높이를 매번 다시 계산하는 방식은 제곱 시간, 높이와 판정을 합친 방식은 선형 시간입니다.

실제 문제의 단계별 풀이와 정답

실제 시험 문제를 한 단계씩 풀기

각 단계의 질문에 먼저 답한 뒤 바로 아래 설명과 대조하세요.

  1. 왜 입력 BST order를 다시 검사하지 않는가?

    문언이 이미 binärer Suchbaum 인스턴스라고 보장하므로 이 알고리즘의 과제는 모든 node의 AVL balance 검사입니다.

  2. base case는 무엇을 반환하는가?

    empty subtree nil은 강의 convention의 실제 height -1을 반환하며 이것은 정상 결과입니다.

  3. node2와 node5는 무엇을 반환하는가?

    node2는 \(\text{hL}=\text{hR}=-1\)hL=hR=-1이라0, node5는 \(\text{hL}0,\text{hR}-1,B=-1\)hL0,hR-1,B=-1이라 height1을 반환합니다.

  4. node10에서 왜 FAIL인가?

    hL1,hR-1이므로 \(B(10)=-2\)B(10)=-2이고 절댓값2가 1을 넘습니다. 따라서 숫자 height 대신 FAIL을 반환합니다.

  5. 최종 호출과 runtime은 어떻게 쓰는가?

    \(\text{answer}=\text{isAVL}(T)\)answer=isAVL(T)를 명시합니다. 각 node를 최대 한 번 방문해 \(O(n)\)O(n), valid tree 등 worst-case \(\Theta(n)\)Θ(n), stack \(O(h)\)O(h)입니다.

이 풀이에서 사용하는 AVL 규약

빈 트리 높이와 실패 표식을 먼저 분리해야 재귀 결과를 모호하지 않게 읽을 수 있습니다.

\[H(\mathrm{nil})=-1\]H(nil)=-1
강의 높이 규약에서 빈 트리의 높이는 -1입니다.
\[B(v)=h_R-h_L\]B(v)=hR-hL
AVL 균형 인자는 오른쪽 높이에서 왼쪽 높이를 뺍니다.
\[\lvert B(v)\rvert\le1\]|B(v)|≤1
모든 노드에서 균형 인자의 절댓값이 1 이하여야 합니다.
\[\mathrm{FAIL}\ne-1\]FAIL≠-1
실패 표식은 정상적인 빈 트리 높이 -1과 달라야 합니다.

선형 시간 \(O(n)\)O(n) 재귀 알고리즘

heightOrFail(v):
  if v == nil: return -1
  left = heightOrFail(v.left)
  if left == FAIL: return FAIL
  right = heightOrFail(v.right)
  if right == FAIL: return FAIL
  if abs(right - left) > 1: return FAIL
  return 1 + max(left, right)
isAVL(T): return heightOrFail(T) != FAIL
call: answer = isAVL(T)

구체적인 후위 순회 추적 · 강의 높이와 FAIL

자식 결과가 부모로 올라가는 방향
2\(B=0 \cdot 0\)B=0 · 05B=-1 · 110B=-2 · FAIL
계산 순서노드왼쪽 높이오른쪽 높이균형 인자 \(B=\text{hR}-\text{hL}\)B=hR-hL반환값이유
1nil children of 2----1empty tree base case
22-1-100leaf height 0
350-1-11허용 balance라 height 1
4101-1-2FAIL|\(B(10)|=2\)B(10)|=2로 AVL 위반

학습용 추가 분석 · Correctness와 complexity

다음 증명과 비용 분석은 복기 문언의 직접 제출 요구가 아니라, 알고리즘을 검산하기 위한 보강입니다.

Correctness를 귀납적으로 확인

  1. Base: nil은 강의 height -1인 AVL tree이며 helper가 -1을 정확히 반환합니다.
  2. Induction: 두 child 결과가 실제 height이고 |\(\text{hR}-\text{hL}|\le 1\)hR-hL|≤1이면 현재 subtree는 AVL이며 1+max가 정확한 height입니다.
  3. 어느 child든 FAIL이거나 |\(\text{hR}-\text{hL}|>1\)hR-hL|>1이면 현재 subtree도 AVL일 수 없어 FAIL 전파가 정확합니다.
  4. root 결과가 FAIL이 아닌 것과 전체 tree의 모든 node가 AVL balance를 만족하는 것이 동치입니다.
실제 풀이를 마친 뒤

답이 맞는지 스스로 검산

  1. \(\text{trace}_{\text{rows}}\)trace(rows)의 모든 balance가 hR-hL과 일치하고 return이 course height 또는 FAIL인지 재계산합니다.
  2. pseudocode에서 \(\text{nil}=-1\)nil=-1과 \(\text{invalid}=\text{FAIL}\)invalid=FAIL이 서로 다른 token이며 isAVL(T)가 FAIL과 비교하는지 확인합니다.
  3. helper 안에서 별도 height 재귀를 다시 호출하지 않아 각 node가 최대 한 번 방문되는지 call structure를 확인합니다.

30초 자가점검

invalid sentinel로 -1을 쓰면 왜 강의 convention과 충돌하는가?

힌트: empty subtree의 정상 height를 확인합니다.

정답: 강의에서 empty tree의 유효한 height가 이미 -1이므로 invalid와 구분할 수 없습니다. 별도 FAIL이 필요합니다.

root balance만 0이면 전체 tree가 AVL인가?

힌트: AVL definition이 어느 node에 적용되는지 봅니다.

정답: 아닙니다. 모든 descendant node의 subtree도 AVL이어야 하므로 postorder로 각 node를 검사하고 failure를 전파해야 합니다.

시험 답안 템플릿

Postorder helper가 course height 또는 FAIL을 반환한다. \(\text{nil}\to -1, \text{child} \text{FAIL}\to \text{FAIL}, |\text{hR}-\text{hL}|>1\to \text{FAIL},\)nil→-1, child FAIL→FAIL, |hR-hL|>1→FAIL,아니면 1+max. isAVL(T)는 \(\text{helper}(T)\ne \text{FAIL}.\)helper(T)!=FAIL.각 node를 최대 한 번 방문하므로 \(O(n)\)O(n), worst-case \(\Theta(n)\)Θ(n), stack \(O(h)\)O(h).

초보자가 자주 틀리는 지점

  • root의 balance만 검사한다.
  • BST order까지 다시 검사하느라 핵심을 흐린다. 입력은 BST라고 주어졌습니다.
  • height를 각 node마다 별도 재귀 계산해 \(O(n^{2})\)O(n²)로 만든다.
  • child가 FAIL인데 높이 숫자로 계속 계산한다.
  • course empty height -1과 invalid sentinel을 같은 값으로 사용한다.
  • 함수를 정의하고 실제 call isAVL(T)를 쓰지 않는다.

근거와 정확성 범위

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