Open Data Structures 한국어 재편찬

파일을 열고, 연락처를 찾고, 검색 엔진을 쓰고, 로그인 요청을 처리하는 일은 모두 “많은 원소 중 필요한 원소를 빨리 찾는 일”이다. 원소가 100개일 때는 어떤 방식도 그럭저럭 작동하지만, 원소가 10억 개라면 O(n)과 O(log n), O(1)의 차이가 시스템 전체 설계를 갈라놓는다.

효율성은 단순히 CPU 명령 수만 뜻하지 않는다. C++에서는 메모리 할당, 캐시 미스, 분기 예측 실패, 객체 복사 비용이 성능을 크게 흔든다. CUDA/Triton에서는 연속 접근과 정렬된 접근이 warp 단위 메모리 병합에 영향을 주고, 포인터를 따라가는 구조는 병렬성보다 지연 시간을 먼저 드러낸다.

인터페이스는 “무엇을 할 수 있는가”를 정하고, 구현은 “그 일을 어떻게 할 것인가”를 정한다. 같은 List라도 배열로 만들면 임의 접근이 빠르고, 연결 리스트로 만들면 이미 찾은 노드 주변의 삽입 삭제가 빠르다.

C++에서는 인터페이스가 추상 클래스, 템플릿, 관례적 메서드 집합 중 하나로 표현된다. 이 교재에서는 구현의 핵심을 보이기 위해 완전한 표준 라이브러리 호환성보다 불변조건과 복잡도를 우선한다.

분석에서 가장 자주 쓰는 도구는 로그, 합, 지수, 확률의 기대값이다. log n은 균형 트리의 높이, 스킵리스트의 기대 경로 길이, B-트리의 I/O 횟수에서 반복해서 나온다. 밑이 달라도 상수배 차이라서 점근 표기에서는 보통 생략한다.

빅오 표기 O(f(n))은 충분히 큰 n에 대해 어떤 함수가 f(n)의 상수배보다 빨리 커지지 않는다는 뜻이다. 하한은 Omega(f(n)), 같은 차수는 Theta(f(n))로 쓴다.

1 + 2 + ... + n = n(n+1)/2 = Theta(n^2)
1 + 1/2 + 1/3 + ... + 1/n = H_n = Theta(log n)
1 + 2 + 4 + ... + 2^k = 2^(k+1)-1 = Theta(2^k)

무작위 자료구조에서는 “한 실행”이 아니라 동전을 던지는 모든 경우의 평균을 본다. Treap과 스킵리스트의 O(log n)은 이런 기대 시간이다. 상각 분석은 여러 연산의 총비용을 나누어 평균적인 연산 비용을 말한다. 동적 배열의 resize가 대표적이다.

기본 분석은 word-RAM 모델을 사용한다. 하나의 워드는 포인터나 정수 하나를 담을 만큼 충분하고, 워드 단위 산술, 비교, 배열 인덱싱, 포인터 역참조는 O(1)로 본다. 이 모델은 알고리즘의 큰 형태를 설명하는 데 적당하지만, 실제 C++ 성능을 모두 말해주지는 않는다.

정확성은 불변조건으로 잡는다. 배열 기반 리스트에서는 “유효한 원소는 a[0..n-1]에 있다”가 불변조건이고, 이진 검색 트리에서는 “왼쪽 서브트리의 모든 키는 현재 키보다 작고 오른쪽은 크다”가 불변조건이다. 연산의 시작과 끝에서 불변조건이 보존되면 구현을 믿을 수 있다.

시간복잡도는 최악, 평균, 기대, 상각으로 나뉜다. 해시 테이블은 좋은 해시와 적절한 load factor에서 기대 O(1)이지만, 악의적인 충돌에서는 더 나빠질 수 있다. 스케이프고트 트리는 개별 rebuild가 비싸도 긴 연산열 전체로 보면 삽입 삭제가 상각 O(log n)이다.

공간복잡도는 저장된 원소뿐 아니라 보조 배열, 포인터, 색 비트, 우선순위, tombstone까지 포함한다. 고성능 코드에서는 O(n)끼리도 한 원소당 몇 워드를 쓰는지가 중요하다.

본문의 코드는 C++에 가깝지만 설명을 위해 예외 처리, allocator, move semantics, iterator 무효화 같은 산업용 세부는 줄였다. 핵심은 각 연산이 어떤 원소를 움직이고 어떤 포인터를 바꾸며 어떤 조건에서 resize 또는 rebuild를 하는지다.

template <class T>
struct ArrayStack {
  T* a = nullptr;
  int n = 0;
  int capacity = 0;

  T get(int i) const { return a[i]; }
  void set(int i, const T& x) { a[i] = x; }
};

실제 라이브러리 코드라면 RAII, 복사/이동 생성자, 예외 안정성, 경계 검사 정책을 더해야 한다. 여기서는 알고리즘의 골격이 흐려지지 않도록 최소 형태로 둔다.

이 책은 리스트, 큐, 덱, 집합, 정렬 집합, 우선순위 큐, 그래프를 구현하는 여러 방식을 비교한다. 배열 기반 구조는 단순하고 빠른 메모리 접근을 준다. 연결 구조는 삽입 삭제의 국소성을 준다. 트리는 순서를 보존하면서 검색을 빠르게 하고, 해시는 순서를 포기하는 대신 평균 상수 시간을 얻는다.

뒤쪽 장에서는 정수 키에 특화된 트라이와, 메모리 블록 단위로 비용을 재는 B-트리를 다룬다. 이는 GPU와 외부 메모리 모두에서 중요한 사고방식이다. 데이터 하나가 아니라 “한 번의 전송으로 몇 개를 함께 가져오는가”가 성능을 바꾸기 때문이다.

• 같은 O(1)인 배열 접근과 포인터 접근이 실제로 다른 이유를 캐시 관점에서 설명해 보라.
• List와 SSet의 find가 의미하는 바가 어떻게 다른지 예를 들어 보라.
• 상각 O(1)과 평균 O(1)의 차이를 동적 배열과 해시 테이블로 비교해 보라.

ArrayStack은 a[0]부터 a[n-1]까지 원소를 저장한다. get(i)와 set(i,x)는 배열 인덱싱 한 번이므로 O(1)이다. add(i,x)는 i..n-1을 오른쪽으로 한 칸 밀고, remove(i)는 i+1..n-1을 왼쪽으로 민다. 그래서 비용은 O(n-i)다.

void add(int i, const T& x) {
  if (n + 1 > capacity) resize();
  for (int j = n; j > i; --j) a[j] = a[j-1];
  a[i] = x;
  ++n;
}

T remove(int i) {
  T x = a[i];
  for (int j = i; j < n - 1; ++j) a[j] = a[j+1];
  --n;
  if (capacity >= 3 * n) resize();
  return x;
}

용량을 매번 1씩 늘리면 삽입이 비싸다. 보통 새 배열 크기를 max(1, 2n)처럼 잡는다. 그러면 긴 연산열에서 resize로 복사되는 총 원소 수가 O(m)이 되어 연산당 상각 O(1)이 추가된다.

FastArrayStack은 ArrayStack의 논리를 바꾸지 않고, 원소 이동을 더 빠른 블록 복사로 처리하는 버전이다. C++에서 trivially copyable 타입이라면 memmove류 최적화가 가능하고, 일반 객체라면 move assignment 또는 std::move_backward가 더 안전하다.

std::move_backward(a + i, a + n, a + n + 1);
a[i] = x;
++n;

점근 복잡도는 그대로다. 그러나 실제 성능에서는 루프 하나를 직접 도는 것과 런타임/컴파일러가 최적화한 블록 이동 사이에 큰 차이가 날 수 있다. 이 장은 “빅오를 맞춘 뒤 상수를 줄이는 단계”를 보여준다.

큐는 앞에서 빼고 뒤에 넣는다. 매번 a[0]을 제거하고 전체를 왼쪽으로 밀면 느리다. 대신 j를 첫 원소의 위치로 두고, 논리적 k번째 원소를 a[(j+k) % capacity]에 둔다.

void add(const T& x) {
  if (n + 1 > capacity) resize();
  a[(j + n) % capacity] = x;
  ++n;
}

T remove() {
  T x = a[j];
  j = (j + 1) % capacity;
  --n;
  if (capacity >= 3 * n) resize();
  return x;
}

모듈러 연산 때문에 배열이 물리적으로는 두 조각으로 보일 수 있지만, 논리적으로는 한 줄이다. resize할 때는 논리 순서대로 새 배열 b[0..n-1]에 복사하고 j=0으로 되돌린다.

ArrayDeque는 순환 배열 위에서 List 연산을 더 똑똑하게 처리한다. add(i,x)에서 i < n/2이면 앞쪽 원소들을 왼쪽으로 밀고, 그렇지 않으면 뒤쪽 원소들을 오른쪽으로 민다. 삭제도 같은 기준으로 가까운 쪽만 움직인다.

따라서 삽입 삭제 비용은 O(min{i, n-i})이다. 양끝에 가까운 연산은 상수 시간에 가깝고, 가운데만 선형 비용을 낸다.

DualArrayDeque는 앞 절반을 담는 front와 뒤 절반을 담는 back 두 ArrayStack으로 리스트를 표현한다. 중요한 점은 front가 역순이라는 것이다. 논리적 리스트는 reverse(front) + back이다.

front: [c, b, a]   back: [d, e, f]
list : [a, b, c, d, e, f]

삽입 삭제는 해당 절반의 ArrayStack 연산으로 위임한다. 한쪽이 다른 쪽의 세 배보다 커지면 전체 원소를 반반으로 다시 나눈다. 이 재분배는 비싸지만 너무 자주 일어나지 않으므로 상각 비용은 유지된다.

RootishArrayStack은 크기가 1, 2, 3, ...인 블록을 차례로 둔다. r개 블록의 총 칸 수는 r(r+1)/2이므로 n개 원소를 담는 데 필요한 블록 수는 대략 sqrt(2n)이다. 마지막 블록의 빈칸이 많아도 전체 낭비는 O(sqrt n)이다.

인덱스 i가 들어갈 블록 b는 b(b+1)/2 <= i를 만족하는 가장 큰 b를 계산해서 찾는다. 블록 안 위치는 i - b(b+1)/2다.

int block(int i) {
  double db = (-3.0 + std::sqrt(9.0 + 8.0 * i)) / 2.0;
  return static_cast<int>(std::ceil(db));
}

엄밀한 구현에서는 부동소수점 오차를 보정해야 한다. 이 구조의 교훈은 “단일 큰 배열”과 “많은 작은 배열” 사이에서도 공간과 접근 시간을 설계할 수 있다는 점이다.

• ArrayDeque의 add(i,x)에서 앞쪽을 밀지 뒤쪽을 밀지 결정하는 기준을 증명해 보라.
• resize 기준을 capacity >= 2n으로 바꾸면 어떤 장단점이 생기는가?
• RootishArrayStack의 낭비 공간이 O(sqrt n)임을 블록 수로 설명해 보라.

SLList의 노드는 값 x와 다음 노드 포인터 next를 가진다. 리스트는 head, tail, 크기 n을 저장한다. 앞쪽 삽입 삭제는 head만 바꾸면 되고, 뒤쪽 삽입은 tail이 있어서 O(1)이다. 하지만 뒤쪽 삭제는 이전 노드를 찾아야 하므로 O(n)이다.

struct Node {
  T x;
  Node* next;
};

void push(const T& x) {
  head = new Node{x, head};
  if (n == 0) tail = head;
  ++n;
}

따라서 단일 연결 리스트는 스택의 push/pop과 큐의 add/remove를 잘 구현한다. 다만 인덱스 i로 접근하려면 head부터 i번 따라가야 하므로 O(i)다.

DLList는 각 노드에 prev와 next를 둔다. 보통 더미 노드 dummy를 하나 두고, 빈 리스트에서도 dummy.next = dummy.prev = dummy가 되게 만든다. 그러면 첫 노드와 마지막 노드를 특별 취급하는 코드가 줄어든다.

void addBefore(Node* w, const T& x) {
  Node* u = new Node{x, w->prev, w};
  u->prev->next = u;
  u->next->prev = u;
  ++n;
}

인덱스 접근은 앞에서 갈지 뒤에서 갈지 골라 O(min{i, n-i})에 노드를 찾는다. 노드 포인터가 이미 있으면 삽입 삭제는 포인터 네 개 정도를 고치는 O(1) 연산이다.

SEList는 노드 하나에 원소 하나를 담지 않고, 각 노드가 작은 배열 블록을 가진다. 블록 크기 매개변수 b를 두고 대부분의 블록이 b개 안팎의 원소를 담게 유지한다. 이렇게 하면 포인터 수는 줄고 블록 안 원소는 연속 메모리에 놓인다.

삽입할 블록이 꽉 찼을 때 근처에 여유가 있는 블록을 찾으면 원소를 조금씩 밀어 빈칸을 만든다. 근처 b개 블록이 모두 꽉 찼다면 새 블록을 만들고 원소를 골고루 분산한다. 삭제도 반대로 너무 빈 블록들이 생기면 모으거나 병합한다.

• 더미 노드를 쓰면 빈 리스트와 길이 1 리스트의 코드가 어떻게 단순해지는지 포인터 갱신 순서로 설명해 보라.
• SLList에서 removeLast()를 O(1)로 만들려면 어떤 정보가 더 필요한가?
• SEList의 b가 너무 작거나 너무 클 때 생기는 문제를 비교해 보라.

각 원소는 높이 h의 타워를 가진다. 레벨 0은 모든 원소를 연결하고, 높은 레벨일수록 일부 원소만 남아 긴 점프를 제공한다. 검색은 맨 위 sentinel에서 시작해 오른쪽으로 갈 수 있으면 가고, 더 갈 수 없으면 한 층 내려간다.

level 3:  -inf ------------------ 42 -------- +inf
level 2:  -inf ------ 17 -------- 42 -------- +inf
level 1:  -inf -- 9 --17 ---- 31--42 ---- 58- +inf
level 0:  -inf 3 9 12 17 24 31 42 50 58 61 +inf

새 노드의 높이는 동전을 던져 앞면이 계속 나오는 횟수처럼 정한다. 높이가 r 이상일 확률이 1/2^r이므로 높은 타워는 드물다. 이것이 공간 O(n)과 기대 검색 시간 O(log n)의 근거다.

SkiplistSSet의 find(x)는 x 이상인 가장 작은 원소를 찾는다. 검색은 각 레벨에서 next[r]->x < x인 동안 오른쪽으로 가고, 더 갈 수 없으면 아래로 내려간다. 삽입은 각 레벨에서 새 노드 바로 앞에 와야 하는 노드를 기록한 뒤 포인터를 끼운다.

Node* findPredNode(const T& x) {
  Node* u = sentinel;
  int r = h;
  while (r >= 0) {
    while (u->next[r] != nullptr && u->next[r]->x < x) u = u->next[r];
    --r;
  }
  return u;
}

삭제는 같은 경로를 따라가며 각 레벨에서 삭제 대상이 바로 다음이면 건너뛰도록 포인터를 바꾼다. 높은 레벨이 비면 전체 높이를 낮춘다. 모든 연산은 기대 O(log n)이다.

SkiplistList는 각 포인터에 그 포인터가 건너뛰는 레벨 0 원소 수, 즉 길이 정보를 함께 둔다. 그러면 검색 값 대신 인덱스 i를 가지고 현재까지 지나온 원소 수를 누적하며 이동할 수 있다.

삽입과 삭제는 포인터뿐 아니라 길이도 조정해야 한다. 포인터가 가리키는 구간이 새 노드에 의해 둘로 나뉘면 길이도 두 구간으로 나뉜다. 이 작은 장부가 get(i), set(i,x), add(i,x), remove(i)를 기대 O(log n)에 가능하게 한다.

레벨 r에 나타나는 노드의 기대 개수는 n/2^r이다. 따라서 높이는 대략 log n 근처에서 멈춘다. 검색 경로를 거꾸로 보면, 왼쪽으로 움직이거나 위로 올라가는 단계의 기대 수가 각 레벨에서 상수이므로 전체 기대 경로 길이는 O(log n)이다.

• 새 노드 높이를 항상 floor(log n)으로 제한하면 어떤 문제가 생기는가?
• SkiplistList에서 길이 배열을 갱신하지 않으면 어떤 연산이 틀어지는지 예를 만들어 보라.

체이닝 방식은 배열 t의 각 칸에 작은 리스트를 둔다. 키 x는 hash(x) mod t.length가 가리키는 버킷으로 들어간다. 충돌이 나면 같은 버킷 리스트 안에서 찾는다.

bool add(const T& x) {
  if (find(x) != null) return false;
  if (n + 1 > t.size()) resize();
  t[hash(x)].push_back(x);
  ++n;
  return true;
}

해시가 원소를 균등하게 흩뿌리고 적재율 n/t.length를 상수로 유지하면 각 버킷 길이의 기대값은 상수다. 따라서 find/add/remove는 기대 O(1)이다. 최악의 경우 한 버킷에 다 몰리면 O(n)이다.

선형 탐사는 버킷 안에 리스트를 두지 않고 배열 자체에 원소를 저장한다. i = hash(x)에서 시작해 빈 칸을 만날 때까지 i, i+1, i+2, ...를 본다. 삭제된 칸은 검색을 끊으면 안 되므로 del 표식을 둔다.

int findSlot(const T& x) {
  int i = hash(x);
  while (t[i] != null && t[i] != x) i = (i + 1) % t.size();
  return i;
}

선형 탐사는 배열을 순차적으로 읽으므로 캐시에 매우 좋다. 대신 군집화가 생기면 탐사 길이가 늘어난다. 보통 배열 크기를 2의 거듭제곱으로 잡고, 적재율이 일정 수준을 넘기 전에 resize한다.

해시 테이블의 성능은 객체를 정수로 바꾸는 해시 코드와 그 정수를 테이블 범위로 접는 방식에 달려 있다. 반드시 지켜야 하는 조건은 같다고 판단되는 객체는 같은 해시 코드를 가져야 한다는 것이다. 반대로 다른 객체가 같은 해시 코드를 갖는 것은 허용되지만 적을수록 좋다.

정수 키에는 곱셈 해싱이 자주 쓰인다. 큰 홀수 z를 곱하고 상위 d비트를 테이블 인덱스로 쓰면 낮은 비트 패턴에 덜 민감해진다. 문자열은 각 문자를 계수로 보아 다항식처럼 누적하는 방법을 쓸 수 있다.

uint64_t h = seed;
for (unsigned char c : s) {
  h = h * 1315423911u + c;
}

보안이 필요한 해시 테이블은 공격자가 충돌을 만들 수 있다는 점을 고려해야 한다. 일반 알고리즘 분석에서의 기대 O(1)은 해시 함수 선택에 대한 가정 위에 서 있다.

• 체이닝과 선형 탐사를 캐시 지역성, 삭제 구현, 최악 시간 관점에서 비교해 보라.
• 해시 테이블이 정렬 집합 SSet을 직접 구현하기 어려운 이유를 설명해 보라.

기본 노드는 left, right, parent를 가진다. 루트에서 어떤 노드까지의 간선 수가 깊이이고, 노드에서 가장 먼 잎까지의 길이가 높이다. 트리 순회는 전위, 중위, 후위, 레벨 순회로 나뉜다.

void traverse(Node* u) {
  if (u == nullptr) return;
  traverse(u->left);
  visit(u);
  traverse(u->right);
}

재귀 순회는 간결하지만 높이가 큰 트리에서는 호출 스택이 깊어진다. C++에서 반복 구현을 쓰면 스택 메모리를 명시적으로 관리할 수 있다.

이진 검색 트리의 불변조건은 모든 노드 u에 대해 왼쪽 서브트리의 키는 u.x보다 작고, 오른쪽 서브트리의 키는 크다는 것이다. 그래서 중위 순회를 하면 정렬된 순서가 나온다.

검색은 루트에서 시작해 키를 비교하며 왼쪽 또는 오른쪽으로 내려간다. 삽입은 검색이 실패한 위치에 새 잎을 붙인다. 삭제할 노드의 자식이 하나 이하이면 바로 이어 붙이고, 자식이 둘이면 오른쪽 서브트리의 최솟값 또는 왼쪽 서브트리의 최댓값과 바꾼 뒤 잎에 가까운 노드를 제거한다.

Node* findLast(const T& x) {
  Node* w = root;
  Node* prev = nullptr;
  while (w != nullptr) {
    prev = w;
    if (x < w->x) w = w->left;
    else if (w->x < x) w = w->right;
    else return w;
  }
  return prev;
}

모든 연산 시간은 높이 h에 비례한다. 삽입 순서가 이미 정렬되어 있으면 높이가 n이 되어 리스트처럼 느려진다. 다음 장들은 이 높이를 통제하는 여러 방법이다.

• BST에서 중위 순회가 정렬 순서를 내는 이유를 귀납적으로 증명해 보라.
• 정렬된 입력을 순서대로 삽입하면 왜 높이가 n-1이 되는가?

서로 다른 키를 무작위 순서로 BST에 삽입하면, 어떤 원소의 기대 깊이는 O(log n)이다. 직관은 간단하다. 두 키 중 먼저 삽입된 키가 구간의 조상이 되며, 한 원소가 다른 원소의 조상이 될 확률은 둘 사이 구간 크기의 역수로 제한된다. 이를 모두 더하면 조화급수 H_n = O(log n)이 나온다.

문제는 실제 입력이 무작위라는 보장이 없다는 점이다. 그래서 구조 안에 무작위 우선순위를 저장해, 삽입 순서를 내부적으로 섞은 것처럼 만든다.

Treap은 두 조건을 동시에 만족한다. 키에 대해서는 BST이고, 각 노드의 무작위 priority에 대해서는 힙이다. 삽입은 일반 BST처럼 잎에 붙인 뒤, 부모보다 priority가 작으면 회전으로 위로 올린다. 삭제는 대상 노드를 회전으로 아래로 내려 자식이 하나 이하가 되게 한 뒤 제거한다.

void bubbleUp(Node* u) {
  while (u->parent != nullptr && u->parent->p > u->p) {
    if (u == u->parent->left) rotateRight(u->parent);
    else rotateLeft(u->parent);
  }
}

priority가 모두 다르면 Treap의 모양은 “priority가 작은 순서대로 키를 삽입한 BST”와 같다. 그래서 검색, 삽입, 삭제는 기대 O(log n)이다. 단, 회전은 포인터 갱신이 섬세하다. 부모, 자식, 루트 교체 순서를 틀리지 않아야 한다.

• Treap의 priority를 삽입 시간으로 두면 어떤 트리가 되는가?
• 회전이 BST 불변조건을 보존한다는 사실을 작은 그림으로 설명해 보라.

ScapegoatTree는 현재 크기 n과 최근 최대 크기 q를 저장한다. 높이는 log_{3/2} q를 넘지 않게 유지한다. 새 노드가 이 한계를 넘어 깊게 삽입되면, 조상으로 올라가며 어떤 자식 서브트리가 부모 크기의 2/3보다 큰 첫 노드를 찾는다. 그 노드가 scapegoat다.

재구성은 간단하다. 서브트리를 중위 순회해 정렬 배열로 만들고, 가운데 원소를 루트로 하여 균형 BST를 다시 만든다.

rebuild(u):
  a = inorder_nodes(u)
  return build_balanced(a, 0, a.length)

한 번의 rebuild는 해당 서브트리 크기만큼 비싸다. 그러나 rebuild가 일어나려면 그 서브트리에 충분히 많은 삽입이 누적되어 있어야 하므로 삽입의 상각 비용은 O(log n)이다. 삭제 뒤 q > 2n이 되면 전체 트리를 다시 만들고 q=n으로 낮춘다.

• 왜 scapegoat는 반드시 존재하는가? 모든 조상이 2/3 균형이라고 가정하면 깊이가 어떻게 제한되는지 생각해 보라.
• 노드마다 높이나 색을 저장하지 않는 장점과 rebuild 비용의 단점을 비교해 보라.

2-4 트리는 내부 노드가 2, 3, 4개의 자식을 가질 수 있고 모든 잎이 같은 깊이에 있는 다방향 검색 트리다. 노드에 키가 1개면 자식 2개, 키가 2개면 자식 3개, 키가 3개면 자식 4개를 가질 수 있다.

삽입 중 4-노드가 넘치면 가운데 키를 부모로 올리고 양쪽을 나눈다. 삭제 중 너무 작은 노드가 생기면 형제에게 빌리거나 병합한다. 모든 잎 깊이가 같기 때문에 높이는 O(log n)이다.

레드 블랙 트리는 검은 노드가 2-4 트리의 실제 노드이고, 빨간 노드는 같은 2-4 노드 안에 묶인 키라고 보면 이해하기 쉽다. 중요한 불변조건은 루트가 검은색이고, 빨간 노드의 자식은 검은색이며, 루트에서 모든 외부 노드까지 만나는 검은 노드 수가 같다는 것이다.

삽입은 새 노드를 빨간색으로 넣은 뒤 “빨간 부모와 빨간 자식” 충돌을 고친다. 삼촌이 빨간색이면 색을 뒤집고, 삼촌이 검은색이면 회전과 색 교환으로 국소 구조를 바로잡는다. 삭제는 더 복잡하지만 핵심은 검은 높이 부족을 형제의 색과 자식 색에 따라 이동, 회전, 색칠로 해결하는 것이다.

void rotateLeft(Node* u) {
  Node* w = u->right;
  w->parent = u->parent;
  u->right = w->left;
  if (u->right) u->right->parent = u;
  w->left = u;
  u->parent = w;
  // 부모의 child 포인터 또는 root 갱신이 뒤따른다.
}

레드 블랙 트리는 한 연산에서 O(log n)개 노드를 지나고, 회전은 상수 번 또는 로그 횟수 안에 끝난다. 표준 라이브러리의 ordered map/set 류가 이 계열을 사용하는 이유는 최악 시간 보장이 좋기 때문이다.

Treap은 무작위성으로 기대 균형을 얻고, ScapegoatTree는 불균형이 커질 때 부분 재구성으로 고친다. RedBlackTree는 각 노드에 색 1비트를 더해 항상 균형을 유지한다. 구현 난도는 높지만 최악 O(log n)이 필요할 때 강하다.

• 빨간 노드가 연속으로 두 개 나오면 2-4 트리 표현에서 어떤 문제가 생기는지 설명해 보라.
• 레드 블랙 트리와 스케이프고트 트리 중 어떤 구조가 구현 실수에 더 취약한지 생각해 보라.

BinaryHeap은 완전 이진 트리를 배열에 저장한다. 인덱스 i의 부모는 (i-1)/2, 왼쪽 자식은 2i+1, 오른쪽 자식은 2i+2다. 최소 힙에서는 모든 노드가 자식보다 작거나 같다.

void bubbleUp(int i) {
  while (i > 0) {
    int p = (i - 1) / 2;
    if (!(a[i] < a[p])) break;
    std::swap(a[i], a[p]);
    i = p;
  }
}

add(x)는 맨 뒤에 넣고 위로 올린다. remove()는 루트 최솟값을 꺼내고 마지막 원소를 루트에 놓은 뒤 아래로 내린다. 높이가 O(log n)이므로 두 연산은 O(log n), findMin은 O(1)이다. 임의 배열을 힙으로 만드는 heapify는 아래에서 위로 trickleDown하여 O(n)에 끝난다.

MeldableHeap은 두 힙을 합치는 merge(h1,h2)를 기본 연산으로 삼는다. 두 루트 중 작은 쪽을 새 루트로 고르고, 그 루트의 왼쪽 또는 오른쪽 자식 중 하나를 무작위로 골라 다른 힙과 재귀적으로 합친다.

Node* merge(Node* a, Node* b) {
  if (a == nullptr) return b;
  if (b == nullptr) return a;
  if (b->x < a->x) std::swap(a, b);
  if (random_bit()) a->left = merge(a->left, b);
  else a->right = merge(a->right, b);
  return a;
}

삽입은 한 노드 힙과 merge하고, 삭제는 루트의 두 자식을 merge한다. 기대 시간은 O(log n)이다. 포인터 구조라 BinaryHeap보다 지역성은 나쁘지만, “합치기”가 핵심인 알고리즘에서는 유용하다.

• heapify가 O(n log n)이 아니라 O(n)인 이유를 레벨별 노드 수로 설명해 보라.
• 두 우선순위 큐를 자주 합치는 작업에서는 BinaryHeap과 MeldableHeap 중 무엇이 자연스러운가?

비교 기반 정렬은 원소 사이의 < 비교 결과만 사용한다. 가능한 순열은 n!개이고, 비교 하나는 결정 트리에서 두 갈래만 만든다. 따라서 최악의 경우 필요한 비교 수는 log2(n!) = Omega(n log n)이다.

병합 정렬은 배열을 반으로 나누어 정렬한 뒤 두 정렬 배열을 합친다. 시간은 항상 O(n log n)이고 안정 정렬이지만 보조 배열 O(n)이 필요하다. 퀵정렬은 피벗 기준으로 분할하고 재귀 정렬한다. 무작위 피벗이면 기대 O(n log n)이고 in-place에 가깝지만 최악 O(n^2) 가능성이 있다. 힙 정렬은 BinaryHeap을 이용해 O(n log n) 보장과 O(1) 추가 공간을 얻는다.

void mergeSort(vector<T>& a) {
  if (a.size() <= 1) return;
  split a into left and right;
  mergeSort(left);
  mergeSort(right);
  merge left/right back into a;
}

키가 0..k-1 범위의 정수라면 비교 하한을 피할 수 있다. 계수 정렬은 각 키의 개수를 세고 prefix sum으로 출력 위치를 계산한다. 시간은 O(n+k), 공간도 O(n+k)다. 안정성을 유지하면 기수 정렬의 하위 루틴으로 쓸 수 있다.

기수 정렬은 정수를 d비트씩 잘라 여러 라운드의 안정 계수 정렬을 수행한다. 워드 크기가 w라면 라운드 수는 w/d, 각 라운드 비용은 O(n + 2^d)다. 적절한 d를 잡으면 정수 배열 정렬에서 매우 빠르다.

• 비교 기반 정렬의 하한 증명에서 결정 트리의 잎이 왜 최소 n!개 필요한가?
• 기수 정렬에서 d를 너무 크게 잡으면 어떤 비용이 커지는가?

인접 행렬은 n x n 불리언 배열 a를 두고, 간선 i -> j가 있으면 a[i][j] = true로 표시한다. 간선 추가, 삭제, 존재 질의는 모두 O(1)이다. 그러나 한 정점의 이웃을 모두 찾으려면 행 전체를 훑어야 하므로 O(n)이다.

공간은 O(n^2)이다. 간선이 매우 많은 밀집 그래프라면 자연스럽지만, 간선 수 m이 n^2보다 훨씬 작다면 낭비가 크다. 비트셋으로 압축하면 공간과 SIMD 연산에서 이점이 생긴다.

인접 리스트는 각 정점 i마다 i에서 나가는 이웃 목록을 저장한다. 공간은 O(n+m)이고, 이웃 순회는 실제 이웃 수에 비례한다. 간선 존재 확인과 삭제는 해당 리스트를 찾아야 하므로 일반적으로 O(deg(i))다.

vector<vector<int>> adj;
for (int y : adj[x]) {
  visit_edge(x, y);
}

고성능 그래프 처리에서는 vector of vector보다 CSR(compressed sparse row)처럼 큰 연속 배열 두 개로 표현하는 경우가 많다. ODS의 인접 리스트 개념은 그 출발점이다.

BFS는 큐를 사용해 시작 정점에서 가까운 정점부터 방문한다. 가중치 없는 그래프에서는 BFS 방문 레벨이 최단 거리다. DFS는 재귀 또는 스택을 사용해 한 경로를 깊게 따라간 뒤 되돌아온다. 두 알고리즘 모두 인접 리스트 기준 O(n+m)이다.

queue<int> q;
seen[s] = true;
q.push(s);
while (!q.empty()) {
  int x = q.front(); q.pop();
  for (int y : adj[x]) if (!seen[y]) {
    seen[y] = true;
    q.push(y);
  }
}

순회 알고리즘은 자료구조 선택의 영향을 직접 받는다. 행렬 표현에서 모든 이웃을 찾으면 정점마다 n칸을 보므로 전체가 O(n^2)이 된다. 희소 그래프라면 인접 리스트가 훨씬 낫다.

• 간선 존재 질의가 매우 많고 그래프가 밀집했다면 어떤 표현이 좋은가?
• CSR 표현이 인접 리스트보다 GPU에 더 잘 맞는 이유를 메모리 접근 패턴으로 설명해 보라.

BinaryTrie는 w비트 정수를 루트에서 잎까지의 비트 경로로 저장한다. 0비트면 왼쪽, 1비트면 오른쪽으로 내려간다. 검색, 삽입, 삭제는 비트 수만큼 내려가므로 O(w)다.

정렬 집합의 predecessor/successor를 빠르게 찾기 위해 잎들을 이중 연결 리스트로 연결하고, 비어 있는 방향으로 내려가려 할 때 가까운 잎으로 점프하는 포인터를 둔다. 이 보조 포인터가 단순 trie를 정렬 집합으로 만든다.

key 13 = 01101
root -> 0 -> 1 -> 1 -> 0 -> 1

XFastTrie는 각 레벨의 prefix를 해시 테이블에 저장한다. 키 x의 길이 r prefix가 존재하는지 O(1) 기대 시간에 물을 수 있으므로, binary search로 가장 긴 존재 prefix 길이를 찾는다. 레벨 수가 w이므로 탐색은 O(log w) 기대 시간이다.

단점은 공간이다. 하나의 키가 여러 레벨 prefix를 만들기 때문에 전체 공간이 O(nw)가 될 수 있다. 그래서 다음 구조인 YFastTrie가 공간을 줄인다.

YFastTrie는 모든 원소를 XFastTrie에 넣지 않는다. 원소들을 크기 O(w) 정도의 버킷으로 나누고, 각 버킷의 대표값만 XFastTrie에 넣는다. 버킷 내부는 Treap 같은 보통 정렬 집합으로 관리한다.

검색은 먼저 XFastTrie에서 적절한 대표를 O(log w)에 찾고, 해당 버킷에서 Treap 검색을 한다. 버킷 크기의 기대값이 O(w)이므로 내부 검색도 기대 O(log w)다. 공간은 기대 O(n)으로 내려간다.

• w=32인 환경에서 O(log w)와 O(log n)은 어떤 경우에 의미 있게 달라지는가?
• XFastTrie가 빠른 대신 공간을 많이 쓰는 이유를 prefix 수로 설명해 보라.

외부 메모리에서는 원소 하나가 아니라 크기 B의 블록을 한 번에 읽고 쓴다. 그래서 비용은 CPU 명령 수가 아니라 I/O 횟수로 잰다. BlockStore는 블록을 번호로 할당하고 읽고 쓰는 추상 저장소다.

이 모델에서 좋은 자료구조는 한 번 가져온 블록 안에서 많은 비교와 이동을 처리한다. 연속 배열, 정렬된 블록, 높은 차수의 트리가 중요해지는 이유다.

B-트리는 한 노드에 많은 키와 자식 포인터를 담는 검색 트리다. 한 노드가 외부 메모리 블록 하나에 들어가도록 차수를 잡으면, 노드를 한 번 읽을 때 여러 키 비교를 한꺼번에 할 수 있다. 그래서 높이는 log_B n 수준으로 낮아진다.

검색은 노드 안에서 x가 들어갈 구간을 찾고 해당 자식 블록으로 내려간다. 삽입은 잎에 키를 넣고, 노드가 넘치면 가운데 키를 부모로 올리며 split한다. 삭제는 키가 부족한 노드에 대해 형제에게 빌리거나 병합한다. 모든 주요 연산의 I/O 수는 O(log_B n)이다.

node:
  keys     [k0, k1, k2, ...]
  children [c0, c1, c2, c3, ...]

search x:
  i = first index with x <= keys[i]
  if keys[i] == x found
  else descend children[i]

C++ 구현에서는 노드 안 배열의 최대 크기, split 시 복사 순서, 디스크/메모리 포인터의 추상화가 중요하다. 데이터베이스 인덱스와 파일 시스템에서 이 계열 구조가 널리 쓰인다.

• 왜 외부 메모리에서는 이진 트리보다 B-트리가 더 적은 I/O를 쓰는가?
• 노드 하나가 블록보다 조금 커지면 성능에 어떤 문제가 생기는지 설명해 보라.
• GPU shared memory 타일링과 B-트리의 블록 사고가 닮은 점과 다른 점을 정리해 보라.