BST traversal
13, 7, 29, 5, 11, 19를 삽입해 만든 고정 BST입니다. traversal을 고르면 방문 순서를 단계별로 따라갈 수 있습니다.
Left, node, right. BST에서는 항상 정렬된 순서로 나옵니다: 5, 7, 11, 13, 19, 29.
방문 순서
5
삽입 순서: 13, 7, 5, 11, 29, 19
Data Structures & Algorithms
DSA II를 정렬과 탐색을 지탱하는 구조로 뜯어봅니다.
이 페이지는 DSA I에서 이어지며, DSA II 노트에 있는 내용만 다룹니다. binary search tree와 traversal, BST removal과 SkipList, priority queue를 떠받치는 binary heap, 그리고 collision과 load factor를 다루는 HashMap입니다.
DSA I에서 이어지는 Java와 Big-O 복습: Iterable/Iterator, Comparable과 Comparator, worst-case 증가율
Binary search tree: left < node < right invariant과, 삽입 순서가 O(log n)이냐 한쪽으로 치우친 O(n) chain이냐를 가르는 점
BST removal의 leaf / one-child / two-child 케이스, 그리고 coin flip으로 O(log n)에 도달하는 SkipList
array 기반 priority queue로서의 binary heap: O(1) peek, O(log n) add와 remove
HashMap: key를 bucket index로 hashing한 뒤, load factor 아래에서 chaining이나 probing으로 collision을 푸는 방식
학습 지도
-
Module 4 · BST
Binary Search Trees
BST는 정렬 규칙 하나가 붙은 binary tree입니다. 모든 노드에서 왼쪽 subtree는 더 작고 오른쪽은 더 크다는 invariant가, 트리를 O(log n)으로 검색할 수 있게 만드는 핵심입니다.
-
Module 5 · BST ops + SkipLists
BST removal과 SkipList
BST removal의 세 가지 케이스를 직접 따라가 봤습니다. leaf, one-child, 그리고 까다로운 two-child 케이스인데, two-child는 in-order successor를 끌어올리는 GT 강의 기본 방식을 씁니다. 이어지는 SkipList는 트리 모양 대신 정렬된 linked list를 쌓고 coin flip으로 노드를 promote 하면서 같은 O(log n)에 도달합니다.
-
Module 6 · Heaps
Heap과 Priority Queue
heap은 binary-tree 집안에서 BST의 사촌 격입니다. min(또는 max)을 root에 박아두는 complete tree라 peek은 O(1), add/remove는 O(log n)입니다. 순서 규칙이 parent와 child 사이에만 있어서 sibling끼리는 정렬되지 않고, 그래서 1-indexed array에 i/2, 2i, 2i+1 산술만으로 전체를 깔 수 있습니다. pointer가 필요 없습니다.
-
Module 7 · HashMaps
HashMap: hashing으로 평균 O(1)
여기서부터는 comparison tree를 타고 내려가는 대신, key에서 바로 index를 계산하는 방식으로 넘어왔습니다. 모듈 전체가 사실상 하나의 피할 수 없는 결과인 collision, 그리고 그것을 어떻게 처리하느냐에 대한 이야기였습니다.
시각 실험실
1/6
BST removal (two-child)
in-order successor(GT 강의 기본 방식)로 7개 노드 BST에서 root인 4를 지웁니다.
1. root에서 시작합니다. 4가 target이므로, 지울 노드는 root 자신입니다.
Min-heap sift
1-indexed min-heap입니다. add는 값을 위로 swim 시키고, remove min은 마지막 leaf를 아래로 sink 시킵니다. array와 tree가 같이 움직입니다.
값을 추가하면 위로 swim 하는 모습을, min을 제거하면 마지막 leaf가 내려가는 모습을 볼 수 있습니다.
backing array (1-indexed)
0 비어 있음
비어 있음
complete tree
비어 있음
HashMap collision
index = key mod capacity입니다. key 5, 12, 19가 모두 bucket 5로 갑니다. chaining과 linear probing이 각각 이를 어떻게 푸는지, 그리고 load factor가 0.75를 넘을 때의 resize를 볼 수 있습니다.
key를 삽입하면 collision이 풀리는 과정을 볼 수 있습니다. 각 key가 곧 hash이고, index = key mod capacity입니다.
load factor: 0 / 7 = 0.00
0 → 비어 있음
1 → 비어 있음
2 → 비어 있음
3 → 비어 있음
4 → 비어 있음
5 → 비어 있음
6 → 비어 있음
개념 노트
BST ordering invariant
모든 노드에서 왼쪽 subtree는 노드보다 작고 오른쪽은 큽니다. 매 단계마다 후보의 절반을 버릴 수 있고, 이것이 O(log n) 검색을 가능하게 합니다.
Module 4 · BST
SkipList express lane
SkipList는 정렬된 linked list를 쌓습니다. level 0는 모든 원소를 갖고, 삽입마다 coin flip으로 노드를 한 층 promote 합니다(P(level i) = (1/2)^i). 탐색은 다음 노드가 target보다 작은 동안 오른쪽으로 가다가 넘칠 것 같으면 내려갑니다. 위층이 데이터를 건너뛰므로 평균 O(log n)이 나옵니다.
Module 5 · SkipLists
heap은 결국 array
heap은 complete binary tree라 빈칸 없는 1-indexed array에 딱 맞습니다. index i의 parent는 i/2, child는 2i와 2i+1입니다. completeness 덕분에 이 index 산술이 항상 실제 노드를 가리킵니다.
Module 6 · Heaps
load factor와 resize
load factor = size / capacity이고, threshold(보통 0.67~0.75)를 넘으면 resize가 일어납니다. 더 큰 table을 새로 만들고 모든 entry를 새 capacity로 rehash하는 O(n) 작업입니다. threshold가 낮을수록 collision은 줄지만 메모리는 더 씁니다.
Module 7 · HashMaps
스스로 점검
Module 4 · BST
Binary Search Trees
BST의 ordering invariant는 무엇인가요?
모든 노드에서 왼쪽 subtree의 데이터는 노드보다 작고, 오른쪽 subtree는 노드보다 큽니다. root뿐 아니라 모든 노드에서 재귀적으로 성립합니다.
BST 연산이 평균은 O(log n)인데 worst-case는 왜 O(n)인가요?
균형 잡힌 트리에서는 비교마다 남은 노드의 절반이 떨어져 나가므로, 높이 약 log n인 경로만 따라가면 됩니다. 다만 모양이 삽입 순서에 달려 있어서, 이미 정렬된 값을 넣으면 한쪽으로 늘어진 chain이 되어 linked list처럼 동작하고 검색이 O(n)으로 떨어집니다.
Module 5 · BST ops + SkipLists
BST removal과 SkipList
두 자식이 있는 BST 노드를 지울 때 왜 그냥 떼면 안 되고, 강의는 대신 무엇을 하나요?
그냥 떼면 subtree 하나가 통째로 날아갑니다. 대신 노드 위치는 그대로 두고 데이터만 replacement로 덮어쓴 다음, 그 replacement 노드(자식이 0개나 1개)를 지웁니다. 강의는 in-order successor를 쓰는데, 오른쪽으로 한 칸 간 뒤 왼쪽 끝까지 내려가면 successor입니다.
SkipList는 평범한 linked list로 어떻게 O(log n) 기대 탐색을 얻나요?
정렬된 list를 층층이 쌓습니다. level 0는 전부 갖고, 위 level마다 coin flip으로 promote된 부분집합만 둡니다(P(level i) = (1/2)^i). 위층은 express lane이라, 다음 노드가 target을 넘어설 때까지 오른쪽으로 가다가 넘칠 것 같으면 한 층 내려갑니다. binary search처럼 탐색 공간이 절반씩 줄어듭니다.
Module 6 · Heaps
Heap과 Priority Queue
1-indexed array heap에서 index i의 parent, left child, right child는 어떻게 구하나요?
parent = i/2(정수 내림), left child = 2*i, right child = 2*i + 1입니다. index 0은 비워 두므로 root는 index 1에 있고, 모든 이동이 pointer 없이 산술로 끝납니다.
add는 위로, removeMin은 아래로 가는 이유는?
add는 다음 leaf에 붙인 뒤 parent하고만 비교하며 더 작은 동안 위로 swim 합니다. removeMin은 마지막 원소를 root로 옮기고 아래로 sink 하는데, 매 층에서 더 작은 child와 swap 합니다. 둘 다 한 방향으로 한 경로만 따라갑니다.
Module 7 · HashMaps
HashMap: hashing으로 평균 O(1)
collision resolution의 두 갈래는 무엇인가요?
closed addressing은 충돌한 key를 원래 index의 chain에 그대로 둡니다. bucket마다 linked list를 두는 External/Separate Chaining입니다. open addressing은 probing으로 다른 index에 두는데, linear, quadratic, double hashing이 있습니다. 노트는 External Chaining을 가장 비중 있게 다룹니다.
load factor는 무엇이고, threshold를 넘으면 어떻게 되나요?
load factor = size / capacity입니다. threshold(보통 0.67~0.75)를 넘으면 table을 resize 합니다. 더 큰 backing array를 만들고 살아 있는 entry를 전부 새 capacity로 rehash 합니다. resize는 O(n)입니다.