트리를 사용한 집합과 맵 (Tree Set / Tree Map)

정의

트리 집합 (Tree Set) 과 트리 맵 (Tree Map) 은 균형 이진 탐색 트리 (Balanced BST) 를 기반으로 한 정렬된 자료구조로, 삽입, 조회, 삭제를 O(log N) 에 처리하며 순서를 보장한다. C++ std::set, std::map (Red-Black Tree), Java TreeSet, TreeMap (Red-Black Tree), Python sortedcontainers.SortedSet 이 대표적이다.

균형 BST는 1962년 Adelson-Velsky와 Landis가 AVL 트리로 처음 고안했으며, 1972년 Bayer가 Red-Black Tree를 제안했다.

문제 상황과 동기

다음 쿼리를 Q번 처리해야 한다:

• 정렬된 상태 유지: 삽입/삭제 후에도 오름차순 유지
• 범위 쿼리: “x 이상 최초 원소” (lower_bound), “k번째 작은 원소”
• 순서 통계: “원소 x의 순위는?”

해시 집합: 평균 O(1) 이지만 순서 없음. 정렬하려면 매번 O(N log N).

트리 집합: O(log N) 삽입/조회/삭제, 순회 시 자동 정렬 O(N).

핵심 통찰: 균형 이진 탐색 트리는 정렬 불변성을 유지하면서 동적 삽입/삭제를 logarithmic time 에 처리한다. 회전 (rotation) 으로 트리 높이를 O(log N) 으로 제한.

실무 위치: DB 인덱스 (B-tree), 운영체제 가상 메모리 관리, 네트워크 라우팅 테이블, 우선순위 큐 대안.

시각화

핵심 아이디어

이진 탐색 트리 (BST)

노드마다:

• 왼쪽 서브트리 < 노드 < 오른쪽 서브트리

in-order 순회 = 정렬 순서.

문제: 편향 트리 (skewed tree) 는 높이 N, 모든 연산 O(N).

균형 유지

균형 (balanced): 모든 리프의 깊이 차이가 O(log N).

대표 균형 트리:

STL std::set = Red-Black Tree. Java TreeSet = Red-Black Tree.

주요 연산

insert(x):
    BST 삽입 후 회전으로 균형 복구
    O(log N)

find(x):
    BST 탐색
    O(log N)

erase(x):
    BST 삭제 후 회전으로 균형 복구
    O(log N)

lower_bound(x):
    x 이상 최초 원소
    O(log N)

order_of_key(x):
    x보다 작은 원소 개수
    O(log N) (augmented tree 필요)

find_by_order(k):
    k번째 작은 원소 (0-indexed)
    O(log N) (augmented tree)

알고리즘

BST 삽입

insert(root, x):
    if root == null:
        return new_node(x)
    if x < root.val:
        root.left = insert(root.left, x)
    else if x > root.val:
        root.right = insert(root.right, x)
    // 균형 복구 (AVL/RB 규칙에 따라)
    return balance(root)

lower_bound (x 이상 최초)

lower_bound(root, x):
    result = null
    while root != null:
        if root.val >= x:
            result = root
            root = root.left
        else:
            root = root.right
    return result

Red-Black Tree 회전 (좌회전 예시)

left_rotate(x):
    y = x.right
    x.right = y.left
    y.left = x
    return y

삽입/삭제 후 최대 2번 회전으로 균형 복구 (RB 특성).

구현

// std::set (Red-Black Tree)
#include <bits/stdc++.h>
using namespace std;
int main() {
  set<int> s;
  s.insert(5); s.insert(3); s.insert(7); s.insert(1);
  
  cout << "sorted: ";
  for (auto x : s) cout << x << " ";
  cout << "\n";
  
  auto it = s.lower_bound(4);
  cout << "lower_bound(4) = " << (it != s.end() ? to_string(*it) : "none") << "\n";
  
  s.erase(3);
  cout << "after erase(3): ";
  for (auto x : s) cout << x << " ";
  cout << "\n";
}

# sortedcontainers.SortedSet (C 확장 기반 B-tree)
from sortedcontainers import SortedSet
s = SortedSet([5, 3, 7, 1])
​
print("sorted:", list(s))
​
idx = s.bisect_left(4)
print("lower_bound(4) =", s[idx] if idx < len(s) else "none")
​
s.discard(3)
print("after erase(3):", list(s))

// TreeSet (Red-Black Tree)
import java.util.*;
public class Main {
  public static void main(String[] args) {
      TreeSet<Integer> s = new TreeSet<>();
      s.add(5); s.add(3); s.add(7); s.add(1);
      
      System.out.println("sorted: " + s);
      
      Integer lb = s.ceiling(4);
      System.out.println("lower_bound(4) = " + (lb != null ? lb : "none"));
      
      s.remove(3);
      System.out.println("after erase(3): " + s);
  }
}

sorted: 1 3 5 7 
lower_bound(4) = 5
after erase(3): 1 5 7

복잡도

변형 및 활용

1. Order Statistics Tree (GNU PBDS)

C++ 에서 __gnu_pbds::tree 는 k번째 원소, 순위 쿼리 지원.

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

ordered_set s;
s.insert(5); s.insert(3); s.insert(7);
cout << *s.find_by_order(1);  // 1번째 (0-indexed) = 5
cout << s.order_of_key(6);    // 6보다 작은 개수 = 2

2. Multiset

중복 허용 트리 집합. std::multiset, Java TreeMultiset.

multiset<int> ms = {3, 3, 5};
cout << ms.count(3);  // 2
ms.erase(ms.find(3)); // 하나만 제거

3. TreeMap (순서 보장 맵)

map<int, string> m;
m[3] = "three"; m[1] = "one";
for (auto [k, v] : m) cout << k << ": " << v << "\n"; // 1: one, 3: three

4. Interval Tree

구간 쿼리 최적화. augmented BST 로 max endpoint 저장.

함정

1. 중복 허용 여부

set 은 중복 무시, multiset 은 허용. 실수로 set.insert() 반복해도 크기 1.

2. iterator 무효화

삭제 후 iterator 무효화. erase(it++) 패턴 사용.

for (auto it = s.begin(); it != s.end(); ) {
    if (*it % 2 == 0) it = s.erase(it);
    else ++it;
}

3. 비교 함수 일관성

커스텀 비교 함수는 strict weak ordering 만족 필요. a < b 와 b < a 동시 true 면 undefined behavior.

4. 해시 대비 느림

단순 존재 여부만 묻는다면 unordered_set 이 평균 2~3배 빠름. 정렬/범위 쿼리 필요할 때만 트리.

BOJ 연습 문제

참고

• 집합과 맵
• 해시 집합과 맵
• 이진 탐색 트리