AVL 트리와 레드-블랙 트리

도입: 왜 이진 탐색 트리(BST)만으로는 부족한가

Binary Search Tree(BST)는 key를 비교할 때마다 왼쪽 또는 오른쪽 subtree 하나를 통째로 버릴 수 있어서 빠릅니다. 문제는 tree가 균형을 잃으면 이 장점이 사라진다는 점입니다. 1, 2, 3, 4, 5를 순서대로 넣은 plain BST를 떠올리면 모든 node가 오른쪽으로만 이어진 chain이 됩니다. 이때 search, insert, delete는 tree height h에 비례하므로 \(\Theta(h)\)Θ(h)=\(\Theta(n)\)Θ(n)까지 느려집니다.

AVL tree(AVL-Baum)와 red-black tree(Rot-Schwarz-Baum)의 공통 목표는 “BST order는 유지하고, height는 \(O(\log n)\)O(log n)으로 묶는다”입니다.

먼저 알아야 할 개념

• BST invariant: 왼쪽 subtree key는 작고, 오른쪽 subtree key는 큽니다. duplicate rule은 문제 convention을 따릅니다.
• height(Höhe): node에서 가장 깊은 leaf까지 내려가는 edge 수입니다. Lecture 04 AVL에서는 \(\text{height}(\text{empty})=-1\)height(empty)=-1을 사용합니다.
• inorder traversal: BST에서는 sorted order를 줍니다.
• rotation(Rotation/Drehung): parent-child pointer 몇 개만 바꾸는 \(\Theta(1)\)Θ(1) local operation입니다.

핵심 수식과 기호

단계별 개념 설명

그림처럼 떠올리는 구조

세 그림으로 기억하세요. 첫째, BST order는 바닥 레일입니다. 모든 repair는 이 레일을 벗어나면 안 됩니다. 둘째, AVL은 각 node에 작은 저울을 달아 왼쪽/오른쪽 subtree 높이 차이를 재는 그림입니다. 셋째, red-black tree는 root에서 NIL leaf까지 가는 모든 길에 같은 수의 black checkpoint가 놓인 그림입니다.

풀이 예제: AVL의 RR 경우

1. 빈 AVL tree에 10을 넣으면 10이 root입니다.
2. 20은 10보다 크므로 10의 right child입니다.
3. 30은 10보다 크고 20보다 크므로 20의 right child입니다.
4. node 10에서 Lecture convention으로 \(B(10)=\text{height}(\text{right})-\text{height}(\text{left})=+2\)B(10)=height(right)-height(left)=+2입니다.
5. 무거운 path가 right-right이므로 RR case입니다.
6. rotateLeft(10)을 합니다. 결과는 20이 local root, 10이 left child, 30이 right child입니다.
7. inorder는 전후 모두 10, 20, 30입니다. sorted order는 유지되고 height만 줄었습니다.

AVL 회전(rotation)의 네 경우

AVL insertion에서는 보통 첫 broken node를 고치면 subtree height가 insertion 전과 같아져 repair가 멈춥니다. deletion에서는 height 감소가 위로 전파될 수 있어 root까지 여러 번 rebalancing이 필요할 수 있습니다.

레드-블랙 트리의 필수 성질

1. 먼저 BST property를 만족해야 합니다.
2. 모든 node는 red 또는 black입니다.
3. root는 black입니다.
4. NIL leaf, Sentinel, Halbblatt는 black으로 봅니다. 강의는 \(\text{SH}(\text{nil})=0\)SH(nil)=0으로 둡니다.
5. red node의 child는 모두 black입니다. 이것이 Nicht-Rot-Rot-Regel입니다.
6. 어떤 node에서 아래 NIL leaf까지 가는 모든 path의 black-height(Schwarzhöhe)가 같습니다.

red-red만 확인하면 부족합니다. BST order와 equal black-height까지 모두 맞아야 valid red-black tree입니다.

레드-블랙 트리 삽입·삭제의 직관

AVL 트리와 레드-블랙 트리 비교

자주 생기는 오개념

• rotation이 key 순서를 바꾼다: false. inorder order는 보존됩니다.
• AVL은 perfect tree다: false. 각 node의 두 subtree height 차이가 최대 1이면 됩니다.
• balance factor 부호는 언제나 같다: false. 강의나 책마다 convention이 다를 수 있습니다.
• red node가 있으면 invalid다: false. red-red parent-child edge가 invalid입니다.
• black-height는 normal height와 같다: false. black node만 세는 path count입니다.
• NIL leaf는 무시해도 된다: false. Sentinel/Halbblatt는 black-height 계산에 들어갑니다.

객관식 시험의 함정

• “plain BST search is always \(\Theta(\log n)\)Θ(log n)”은 틀립니다. plain BST는 \(\Theta(h)\)Θ(h)이고 \(h=\Theta(n)\)h=Θ(n)일 수 있습니다.
• “every red-black tree is AVL”은 틀립니다. Sheet06의 관계는 AVL ⊂ RB ⊂ BST입니다.
• “every BST is red-black-colorable”은 틀립니다. Sheet06 solution은 separating example을 사용합니다.
• “red-red만 없으면 valid RB”는 틀립니다. black-height와 BST order도 봐야 합니다.
• “LR case는 right rotation 한 번”은 틀립니다. LR은 left rotation on child, then right rotation on parent입니다.
• “red-black은 perfect balance”는 틀립니다. AVL보다 느슨한 logarithmic balance입니다.
• “AVL deletion도 항상 한 번 repair면 끝”은 틀립니다. height 감소가 위로 전파될 수 있습니다.

구두시험 답변 예시

1. “plain BST의 search/insert/delete는 height h에 비례합니다”로 시작합니다.
2. “h가 \(\Theta(n)\)Θ(n)이 되면 operation도 \(\Theta(n)\)Θ(n)이므로 balanced tree가 필요합니다”라고 연결합니다.
3. “AVL은 모든 node에서 \(B(x)=\text{height}(\text{right})-\text{height}(\text{left})\)B(x)=height(right)-height(left)가 -1,0,+1이어야 합니다”라고 정의합니다.
4. “rotation은 inorder order를 보존하는 \(\Theta(1)\)Θ(1) local pointer change입니다”라고 말합니다.
5. “LL/RR은 single rotation, LR/RL은 double rotation입니다”라고 case를 정리합니다.
6. “red-black tree는 BST plus root black, NIL black, no red-red, equal black-height입니다”라고 정의합니다.
7. “black-height와 red-red 규칙 때문에 \(h\le 2\log_{2}(n+1),\)h≤2log2(n+1),그래서 operations are \(\Theta(\log n)\)Θ(log n)”이라고 마무리합니다.
8. “AVL은 strict/search-friendly, red-black은 looser/update-friendly”라고 비교합니다.

능동 회상 문제

1. plain BST operation이 왜 \(\Theta(h)\)Θ(h)인지 설명하세요.
2. AVL balance factor를 Lecture 04 convention으로 정의하세요.
3. \(\text{height}(\text{empty})=-1\)height(empty)=-1이면 leaf height가 왜 0인지 말하세요.
4. 10,20,30 insertion에서 왜 RR case이고 어떤 rotation인지 설명하세요.
5. LL/RR/LR/RL의 rotation sequence를 말하세요.
6. rotation이 inorder order를 보존하는 이유를 \(A < x < B < y < C\)A < x < B < y < C로 설명하세요.
7. red-black properties를 NIL leaf와 black-height까지 포함해 나열하세요.
8. uncle red case와 uncle black/nil case를 구분하세요.
9. AVL ⊂ RB ⊂ BST에서 참인 문장과 거짓인 문장을 하나씩 만드세요.
10. search-heavy와 update-heavy workload에서 어떤 tree를 고를지 말하세요.

출처에 근거한 설명

• Vorlesung/04AdvancedDataStructures.pdf 1~6쪽: BST의 \(\Theta(h)\)Θ(h), 레드-블랙 성질, \(\text{SH}(\text{nil})=0,\)SH(nil)=0,레드-블랙 높이 경계.
• Vorlesung/04AdvancedDataStructures.pdf 10~18쪽: 센티널(Sentinel), 회전 알고리즘, BST 삽입 뒤 빨강으로 칠하는 레드-블랙 삽입의 시작.
• Vorlesung/04AdvancedDataStructures.pdf 24~29쪽: 레드-블랙 삽입의 반복 불변식과 \(\Theta(\log n)\)Θ(log n) 실행 시간.
• Vorlesung/04AdvancedDataStructures.pdf 31~39쪽: 레드-블랙 삭제 복구의 직관과 실행 시간.
• Vorlesung/04AdvancedDataStructures.pdf 45~50쪽: AVL 정의, 균형 인수의 부호 규칙, 빈 트리 높이 -1, AVL 높이 경계, AVL과 레드-블랙의 장단점.
• Vorlesung/04AdvancedDataStructures.pdf 58~69쪽: AVL 삽입 경우, 회전, 삭제 전파, \(\Theta(\log n)\)Θ(log n) 실행 시간.
• Übung/AuD26_Sheet06.pdf와 Übung/AuD26_Sheet06-Sol.pdf: 레드-블랙 삽입·삭제와 유효성, AVL 삽입·삭제와 유효성, AVL ⊂ RB ⊂ BST, 갱신이 많은 경우의 레드-블랙 선택.

AI 후속 학습 프롬프트

Vorlesung/04AdvancedDataStructures.pdf, Übung/AuD26_Sheet06.pdf, Übung/AuD26_Sheet06-Sol.pdf를 첨부합니다.

AUD 시험을 처음 준비하는 학생에게 AVL 트리와 레드-블랙 트리를 한국어로 가르쳐 주세요. AVL 트리(AVL-Baum), 레드-블랙 트리(Rot-Schwarz-Baum), 회전(Rotation), 검정 높이(Schwarzhöhe), 반잎(Halbblatt), 센티널(Sentinel), 빨강-빨강 금지 규칙(Nicht-Rot-Rot-Regel)은 함께 표시하세요.

일반 BST의 높이 h와 Θ(h) 연산부터 시작하세요. 이어서 Lecture 04의 규칙 B(x)=height(right)-height(left), 허용값 {-1,0,+1}, 빈 트리 높이 -1, LL/RR/LR/RL 회전, 삭제 때의 높이 전파를 설명하세요. 그다음 레드-블랙 성질, SH(nil)=0, 삼촌이 빨강인 경우와 검정/nil인 경우의 삽입 복구, 검정 높이 부족으로 보는 삭제, Θ(log n) 실행 시간, AVL과 레드-블랙의 장단점, Sheet06 포함 관계 AVL ⊂ RB ⊂ BST, 객관식 함정을 가르치고 능동 회상 문제를 한 번에 하나씩 내 주세요.