균형 탐색 트리, 회전, 이진 max-heap

레드-블랙 트리(red-black tree)는 먼저 BST이며, 그 위에 색과 흑색 높이(black-height) 조건을 얹은 구조다. AVL 트리(AVL tree)는 모든 노드에서 부분 트리 높이 차이가 1 이하인 더 엄격한 BST다. 회전(rotation)은 BST의 중위 순회 순서를 보존하는 국소 포인터 변경이다. 이진 최대 힙(binary max-heap)은 거의 완전한 이진트리와 부모 >= 자식 조건만 요구하므로 BST가 아니며, 삽입·최댓값 삭제는 회전이 아니라 교환·힙 정리(swap/heapify)로 복구한다.

BST 연산은 \(O(h)\)O(h)이다. AVL·RB 트리는 \(h = O(\log n)\)h = O(log n)을 유지한다. AVL은 \(B(x) \in \{-1, 0, +1\}, \text{RB}\)B(x) ∈ {-1, 0, +1}, RB트리는 적색 노드 연속 금지(no red-red)와 동일한 흑색 높이(equal black-height)를 지킨다. 최대 힙의 루트는 최댓값이며 삽입·최댓값 추출은 \(O(\log n)\)O(log n)이다.

문장에 Jeder, immer, brauchen keine가 나오면 작은 반례를 먼저 찾고, 구조를 BST·AVL·RB·힙(heap) 네 범주로 분리한다.

II

\(\text{exactly}_{\text{two}}\)exactly(two)

2

• II-5
• II-6
• II-7

정답 조합을 외우는 대신 각 문장을 BST 순서, 균형·색 규칙, 회전 필요 여부, 힙의 모양·순서로 분해해 참거짓을 판정한다.

로컬 말뭉치의 복원 시험 Markdown에는 독일어 움라우트가 깨진 글자가 있다. 아래 독일어 문장은 명확한 움라우트만 복원했으며 수학적 의미는 그대로 보존했다.

이 세 문항의 핵심은 '비슷하게 생긴 이진트리'를 같은 것으로 착각하지 않는 것이다. BST는 좌우 키 순서를 지키는 검색 구조이고, AVL과 레드-블랙 트리(red-black tree)는 BST의 높이를 \(O(\log n)\)O(log n)으로 제한하는 균형 규칙을 추가한다. 힙(heap)은 최댓값을 빨리 꺼내기 위한 우선순위 큐(priority queue) 구현이므로 좌우 전체 정렬을 요구하지 않는다.

이진 탐색 트리(Binary Search Tree, binärer Suchbaum)는 모든 노드 z에서 왼쪽 부분 트리의 키가 z.key 이하이고 오른쪽 부분 트리의 키가 z.key 이상인 구조다. 레드-블랙 트리(red-black tree, Rot-Schwarz-Baum)는 BST에 노드 색, 검은 루트, 적색 노드 연속 금지, 동일한 흑색 높이 규칙을 추가한다. AVL 트리(AVL tree, AVL-Baum)는 BST이며 모든 노드 x에서 '오른쪽 높이 - 왼쪽 높이'인 균형 인수(balance factor) B(x)가 -1, 0, +1 중 하나다. 이진 최대 힙(binary max-heap)은 거의 완전한 이진트리이며 루트가 아닌 모든 x에서 \(\text{parent}.\text{key} \ge x.\text{key}\)parent.key ≥ x.key를 만족한다.

• BST 키 순서를 먼저 검사한다. AVL·RB는 모두 BST 계열이므로 BST 순서가 깨지면 바로 탈락한다.
• 회전(rotation)은 키 순서를 바꾸지 않는다. 바뀌는 것은 부모·자식 모양(parent-child shape)이다.
• 힙(heap)의 왼쪽 자식과 오른쪽 자식 사이에는 정렬 관계가 없다.

회전(rotation)은 중위 순회 키 순서를 보존한다. 즉 \(A < x < B < y < C\)A < x < B < y < C와 같은 순서가 회전 전후에 유지된다. 레드-블랙 트리의 높이는 \(O(\log n)\)O(log n)이고 강의의 상한은 \(h \le 2 \log_{2}(n+1)\)h ≤ 2 log₂(n+1)이다. AVL 트리의 높이도 \(O(\log n)\)O(log n)이며 강의 상한은 \(h \le 1.441 \log_{2} n\)h ≤ 1.441 log₂ n이다. 힙은 맨 아래 층을 제외하면 완전 이진트리이므로 높이가 \(O(\log n)\)O(log n)이다.

일반 BST의 탐색·삽입·삭제 비용은 \(O(h)\)O(h)이며 최악의 경우 h는 n이 될 수 있다. 강의 요약에서 AVL·레드-블랙 트리의 탐색·삽입·삭제는 \(\Theta(\log n)\)Θ(log n)이다. 스플레이 연산(splay operation)은 회전을 사용하며 한 번의 연산은 \(O(h)\)O(h), 연속 연산의 분할 상환 비용(amortized cost)은 \(O(\log n)\)O(log n)이다. 최대 힙의 삽입·최댓값 추출은 교환·힙 정리(swap/heapify)를 사용해 \(O(\log n)\)O(log n)에 실행되고 최댓값 읽기는 \(O(1)\)O(1)이다.

루트 9와 자식 8, 7로 이루어진 올바른 최대 힙은 오른쪽 자식 7이 루트보다 작으므로 BST가 아니다. 레드-블랙 트리는 AVL 균형을 만족하지 않아도 유효할 수 있으며 강의도 \(\text{AVL} \ne \text{Rot}-\text{Schwarz}\)AVL != Rot-Schwarz를 명시한다. Sheet06의 관계에서는 모든 AVL 트리를 레드-블랙으로 색칠할 수 있지만, 이는 BST 모양의 색칠 가능성에 관한 명제이지 힙에 관한 명제가 아니다. 일반 BST 삽입은 탐색 후 리프를 붙이므로 자기 균형 변형을 쓰지 않는다면 rotateLeft나 rotateRight가 필요하지 않다.

• Jeder
• immer
• brauchen keine
• binärer Suchbaum
• Max-Heap
• Rotation
• Heapify
• Rot-Schwarz-färbbar
• 필요조건과 충분조건 (necessary vs. sufficient)

\(\text{RB} = \text{BST} +\)RB = BST +색·흑색 높이\((\text{color}/\text{black}-\text{height}), \text{AVL} = \text{BST} +\)(color/black-height), AVL = BST +엄격한 높이 균형, 힙 = 완전한 모양 + 부모·자식 우선순위이며 BST가 아니다.

일반 BST는 \(O(h)\)O(h), AVL·RB 연산은 \(\Theta(\log n)\)Θ(log n), 힙 삽입·최댓값 추출은 \(O(\log n)\)O(log n), 최댓값·루트 읽기는 \(O(1)\)O(1)이다.

노드 세 개인 힙 [9,8,7]이면 '힙은 BST다'와 '최댓값은 리프에 있다'를 반박할 수 있다. 10,20,30을 정렬 순서로 삽입하면 AVL 회전을 유발하기에 충분하다.

각 보기에서 키 순서를 보존해 탐색하는지, 높이·색으로 균형을 맞추는지, BST 포인터 변경으로 회전하는지, 교환으로 힙 정리(heapify)하는지를 묻는다.