AVL 삽입과 삭제
10, 5, 7을 넣어 left-right double rotation을 일으킨 뒤, 3을 넣고 10을 지워 deletion 후 rebalance를 봅니다.
1. 빈 트리에 10을 insert합니다. 노드 하나, balance factor 0.
Data Structures & Algorithms
DSA III: self-balancing 트리와 divide-and-conquer 알고리즘.
self-balancing 트리는 삽입 순서와 상관없이 search를 logarithmic하게 유지하고, divide-and-conquer는 정렬을 더 작은 부분 문제로 나눠 효율적으로 합칩니다. Georgia Tech DSA III에서 공부한 내용을 단계별로 따라가는 데모로 정리했습니다.
Java generic, Big-O, 그리고 과정 전체를 관통하는 balance invariant를 다시 짚는 Module 0 복습.
AVL 트리: balance factor와 O(log n) 높이를 회복하는 네 가지 rotation.
(2,4) tree: split으로 커지고 fusion으로 작아지는 multi-way 노드.
Iterative sort: bubble, insertion, selection, cocktail shaker를 stability와 adaptivity로 비교.
Divide-and-conquer sort: merge, quicksort, LSD radix, quickselect와 비교 정렬의 lower bound.
#
학습 맵
-
Module 8 · AVL
AVL Trees
각 노드의 balance factor를 저장하고 그 크기가 1을 넘으면 rotation으로 균형을 맞추는 self-balancing BST입니다. 덕분에 삽입 순서와 무관하게 트리 높이가 logarithmic하게 유지됩니다.
-
Module 9 · (2,4)
(2,4) Trees
노드마다 key를 1~3개, 자식을 2~4개 갖는 multi-way search tree입니다. overflow된 노드를 split하며 커지고 빌리거나 merge하며 작아지는데, 모든 leaf가 같은 깊이에 유지됩니다.
-
Module 10 · Iterative sorts
Iterative Sorts
bubble, insertion, selection, cocktail shaker sort입니다. 모두 quadratic 비교 정렬이지만 stability, adaptivity, in-place 여부, 그리고 comparison 대 swap 횟수로 갈립니다.
-
Module 11 · Divide & conquer
Divide & Conquer Sorts
merge sort, Hoare partition을 쓰는 randomized in-place quicksort, 비교하지 않는 LSD radix sort, 그리고 order statistic을 위한 quickselect입니다. Ω(n log n) 비교 lower bound가 배경이 됩니다.
#
비주얼 랩
1/8
(2,4) tree: split과 fusion
가득 찬 노드에 40을 insert해 split을 일으키고, 이어서 key를 remove하며 transfer와 fusion을 살펴봅니다.
1. 가득 찬 root [10, 20, 30]에서 시작합니다. (2,4) 노드는 key를 최대 3개까지 담습니다.
Bubble sort, pass별로
Bubble sort는 인접한 쌍을 비교해 순서가 어긋나면 swap하고, 한 pass에서 swap이 없으면 last-swap 검사로 멈춥니다.
1. Bubble sort는 인접한 쌍을 비교해 순서가 어긋나면 swap합니다. 시작: [5, 1, 4, 2, 8].
Merge sort: divide & conquer
배열을 원소 하나까지 나눈 뒤, 정렬된 조각들을 다시 merge합니다.
1. Merge sort는 배열을 반으로 나누고 각 반을 정렬한 뒤 merge합니다. 시작: [5, 1, 4, 2].
#
개념 노트
balance factor
모든 AVL 노드는 height(left) − height(right)를 저장합니다. 이 값을 {−1, 0, +1}로 유지하면 높이가 Θ(log n)이 되어 삽입 순서와 무관하게 search·insert·delete가 O(log n)에 머뭅니다.
Module 8 · AVL
insert는 한 번, delete는 여러 번
한 번의 insertion은 조상 하나만 불균형하게 만들어 rotation 한 번이면 됩니다. deletion은 subtree를 짧게 만들어 연쇄될 수 있어 root로 돌아가는 길에 여러 노드에서 rotation할 수 있습니다.
Module 8 · AVL
split으로 크고 fusion으로 작게
(2,4) tree는 rotation을 쓰지 않습니다. overflow 노드는 split하며 가운데 key를 promote하고, underflow 노드는 sibling에서 빌리거나(transfer) 합칩니다(fusion). 높이는 root에서만 바뀝니다.
Module 9 · (2,4) Trees
stability와 adaptivity
정렬은 Big-O만으로 갈리지 않습니다. stability는 같은 key의 순서를 보존하고, adaptivity는 거의 정렬된 입력을 더 빠르게 처리합니다. insertion sort는 둘 다 갖고, selection sort는 둘 다 없지만 swap을 최소화합니다.
Module 10 · Iterative Sorts
비교 정렬의 lower bound
key만 비교하는 정렬은 최악의 경우 Ω(n log n)번 비교해야 합니다. decision tree에 leaf가 n!개 필요하기 때문입니다. merge와 quicksort는 이 한계에 도달하고, radix sort는 비교하지 않아 이를 우회합니다.
Module 11 · Divide & Conquer
partition 후 재귀
divide-and-conquer는 문제를 나누고, 부분을 풀고, 합칩니다. merge sort는 반씩 나눠 merge하고, quicksort는 pivot을 기준으로 partition하며, quickselect는 한쪽 partition으로만 재귀해 기대 선형 시간에 order statistic을 찾습니다.
Module 11 · Divide & Conquer
#
스스로 점검
Module 8 · AVL
AVL Trees
AVL의 balance factor는 무엇이고, 언제 rotation이 필요한가요?
balance factor = height(left) − height(right)입니다. −1, 0, +1이면 정상이고, insert나 delete 후 크기가 2가 되면 rotation이 필요합니다.
insertion과 deletion은 각각 rotation이 몇 번 필요한가요?
insertion은 가장 아래의 불균형 노드에서 최대 한 번이면 됩니다. deletion은 균형을 맞출 때마다 subtree가 짧아져 조상이 다시 불균형해질 수 있어 최대 O(log n)번까지 연쇄될 수 있습니다.
네 가지 rotation case는 어떻게 구분하나요?
left-heavy(BF +2)일 때 왼쪽 자식이 왼쪽으로 기울면 LL(single right rotation), 오른쪽으로 기울면 LR(double)입니다. right-heavy(BF −2)일 때 오른쪽 자식이 오른쪽이면 RR(single left rotation), 왼쪽이면 RL(double)입니다.
관례상 height(null)은 무엇이고 왜 중요한가요?
height(null) = −1이라서 leaf의 높이가 0이 되고 height(node) = 1 + max(자식 높이)가 됩니다. balance factor 계산을 일관되게 유지해 줍니다.
rotation 후에는 무엇부터 다시 계산하나요?
rotation한 노드들의 height와 balance factor를 아래에서 위로 갱신합니다. 내려간 노드를 먼저, 그다음 그 높이에 의존하는 새 subtree root를 갱신합니다.
Module 9 · (2,4)
(2,4) Trees
(2,4) tree는 rotation 없이 어떻게 균형을 유지하나요?
모든 leaf가 같은 깊이에 있습니다. overflow가 나면 4-node를 split하고 가운데 key를 위로 promote하므로, 높이는 오직 root에서만 늘어납니다.
deletion에서 transfer와 fusion의 차이는 무엇인가요?
노드가 underflow되면, 인접 sibling이 여유가 있을 때 parent를 거쳐 key를 빌려오는 것이 transfer이고, 여유가 없으면 노드·parent key·sibling을 하나로 합치는 것이 fusion입니다.
(2,4) tree가 red-black tree와 동등한 이유는?
각 (2,4) 노드가 작은 red-black 클러스터에 대응하고, split/fuse가 red-black의 recoloring과 rotation에 대응합니다. 같은 O(log n)을 보장합니다.
Module 10 · Iterative sorts
Iterative Sorts
iterative sort 중 stable한 것은?
bubble, insertion, cocktail shaker는 stable합니다. selection sort는 멀리 떨어진 swap이 같은 key의 순서를 바꿀 수 있어 stable하지 않습니다.
adaptive한 iterative sort는 무엇이고 무슨 뜻인가요?
insertion sort가 adaptive합니다. 거의 정렬된 입력에서는 shift가 적어 O(n)에 가까워집니다. selection sort는 항상 정렬 안 된 구간 전체를 훑습니다.
O(n²)인데도 selection sort를 쓰는 이유는?
quadratic 정렬 중 swap이 최대 O(n)으로 가장 적습니다. write가 comparison보다 훨씬 비쌀 때 유리합니다.
Module 11 · Divide & conquer
Divide & Conquer Sorts
비교 정렬의 lower bound가 O(n log n)인 이유는?
비교 정렬은 leaf가 n!개인 decision tree이고, leaf가 n!개인 이진 트리의 높이는 최소 log₂(n!) = Ω(n log n)이기 때문입니다.
merge sort와 quicksort의 stability와 공간은?
merge sort는 stable하고 out-of-place(O(n) 추가)입니다. quicksort는 in-place(O(log n) stack)지만 unstable하며, randomized pivot으로 기대 O(n log n)이 됩니다.
LSD radix sort는 어떻게 비교 lower bound를 넘나요?
key를 비교하지 않습니다. least-significant digit부터 자릿수별 bucket으로 분배해 k자리에 대해 O(k·n)으로 동작하므로 Ω(n log n)이 적용되지 않습니다.
quickselect는 무엇을 하고 얼마나 빠른가요?
quicksort처럼 partition하되 k가 있는 쪽으로만 재귀해서 k번째로 작은 원소를 기대 O(n)에 찾습니다.