BBST (Splay Tree, Treap)

BBST, Balanced Binary Search Tree, Splay Tree, Treap, 균형 이진 탐색 트리

정의

BBST (Balanced Binary Search Tree) 는 균형이 amortized / expected 로 보장되는 이진 탐색 트리. PS 에서는 split / merge / k 번째 원소 / 구간 합 같은 연산을 함께 지원하는 Splay Tree 와 Treap 이 표준.

set / map 의 일반적인 연산 (insert, erase, find) 만 필요하면 STL std::set 으로 충분. BBST 는 거기에 구간 단위 연산 (배열의 prefix / 부분 reverse / range update) 까지 들고 갈 때 등장.

문제 상황과 동기

문제: 동적 배열 a[0..N-1] 에 대해 다음 연산을 빠르게 처리하고 싶다.

1. insert(k, x): k 번째 위치에 원소 x 삽입
2. erase(k): k 번째 원소 제거
3. reverse(l, r): 구간 [l, r] 을 뒤집음
4. query(l, r): 구간 합 / 최댓값 등 집계

Naive 접근: 배열로 구현하면 insert/erase 가 O(N). 세그먼트 트리로는 reverse 같은 인덱스 재배치 연산을 표현 불가능.

STL set 으로는 왜 안되나: std::set 은 insert/erase/find 는 O(log N) 이지만, k 번째 원소 접근이 O(N). split/merge 도 비지원. 구간 reverse 같은 연산은 아예 불가능.

핵심 통찰: BST 를 implicit key (서브트리 size) 로 keying 하면, 트리를 “k 보다 작은 부분 / 나머지” 로 O(log N) 에 split 가능. 균형을 무작위 priority (Treap) 또는 splay (Splay Tree) 로 보장하면 expected / amortized O(log N).

실전 출현: “동적 배열 reverse”, “k 번째 원소 접근 + 삽입/삭제 섞임”, “구간 갱신 + 인덱스 동적 변화”, BOJ “수열과 쿼리” 시리즈 일부.

Splay Tree

[Sleator-Tarjan 1985]. 접근한 노드를 splay (반복 회전) 로 루트까지 끌어올림. 어떤 회전 / 접근 시퀀스든 amortized O(log N).

splay(x):
  while x 가 루트가 아님:
    if 부모 = 루트:      zig (단순 회전)
    elif 같은 방향:      zig-zig (이중 회전)
    else:                zig-zag

장점: split / merge 가 amortized O(log N), 코드 짧음 단점: 한 번의 연산이 worst O(N) (amortized 만 보장)

시각화

Treap (Tree + Heap)

각 노드에 무작위 priority. 키는 BST 순서, priority 는 max-heap 순서 를 동시에 만족. priority 가 무작위라 트리 모양이 무작위 BST 가 되어 expected O(log N).

insert(x, p):    BST 위치 찾아 삽입 후 priority 가 부모보다 크면 회전 (upheap)
split(t, k):     k 보다 작은 부분트리와 나머지로 분리
merge(a, b):     a 의 모든 키 < b 의 모든 키 일 때, priority 따라 합침

Implicit Treap: 키 대신 서브트리 size 를 keying 으로 사용. 배열의 i 번째 원소 / 부분 reverse / 구간 합 등을 지원.

작동 예시

배열: [3, 1, 4, 1, 5]

Implicit Treap (priority 는 랜덤, 생략):
         4 (idx=2, size=5)
        / \
   1(idx=0)  5(idx=4)
      \
       3(idx=1)

split(t, 3):
  → left: [3, 1, 4] (size=3)
  → right: [1, 5] (size=2)

reverse(0, 2):
  split(t, 0) → [], rest
  split(rest, 3) → mid=[3,1,4], right=[1,5]
  mid.lazy_reverse = true
  merge(left, mid, right)
  → [4, 1, 3, 1, 5]

핵심 불변량: priority 가 max-heap 이면 트리의 expected depth 는 O(log N). split/merge 는 각각 O(depth).

비교

항목	Splay	Treap	Red-Black (std::set)
균형 보장	amortized	expected	worst
split / merge	O(log N) am.	O(log N) exp.	비지원
구현 길이	짧음	중간	매우 김
상수항	회전 많음	깔끔	가장 빠름
persistent	어려움	가능	어려움
구간 연산	가능 (Implicit)	가능 (Implicit)	비지원

핵심 연산

Implicit Treap, 배열의 부분 reverse

각 노드에 lazy_reverse 플래그. push down 할 때 좌/우 자식 swap.

reverse(l, r):
  split t into [..l-1] [l..r] [r+1..]
  middle.lazy_reverse ^= 1
  merge back

전체 O(log N).

Persistent Treap

split / merge 시 새 노드 생성 (copy-on-write). 버전마다 트리의 복사가 노드 O(log N) 추가. 시간 여행 자료구조의 표준.

구현

// O(log N) expected split/merge/reverse. (Implicit Treap with lazy reverse)
#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Node {
    int val, size, priority;
    bool lazy_rev;
    Node *l, *r;
    
    Node(int v) : val(v), size(1), priority(rng()), lazy_rev(false), l(0), r(0) {}
};

int get_size(Node* t) { return t ? t->size : 0; }

void push(Node* t) {
    if (!t || !t->lazy_rev) return;
    swap(t->l, t->r);
    t->lazy_rev = false;
    if (t->l) t->l->lazy_rev ^= 1;
    if (t->r) t->r->lazy_rev ^= 1;
}

void pull(Node* t) {
    if (!t) return;
    t->size = 1 + get_size(t->l) + get_size(t->r);
}

// split: t 를 [0..k-1], [k..n-1] 로 분리
void split(Node* t, int k, Node*& l, Node*& r) {
    if (!t) { l = r = 0; return; }
    push(t);
    int left_size = get_size(t->l);
    if (k <= left_size) {
        split(t->l, k, l, t->l);
        r = t;
    } else {
        split(t->r, k - left_size - 1, t->r, r);
        l = t;
    }
    pull(t);
}

// merge: a 의 모든 원소 < b 의 모든 원소, priority 기준으로 합침
Node* merge(Node* a, Node* b) {
    if (!a) return b;
    if (!b) return a;
    push(a); push(b);
    if (a->priority > b->priority) {
        a->r = merge(a->r, b);
        pull(a);
        return a;
    } else {
        b->l = merge(a, b->l);
        pull(b);
        return b;
    }
}

// insert: k 번째 위치에 val 삽입
void insert(Node*& t, int k, int val) {
    Node *l, *r;
    split(t, k, l, r);
    t = merge(merge(l, new Node(val)), r);
}

// reverse: [l, r] 구간 뒤집기
void reverse(Node*& t, int l, int r) {
    Node *a, *b, *c;
    split(t, l, a, b);
    split(b, r - l + 1, b, c);
    if (b) b->lazy_rev ^= 1;
    t = merge(merge(a, b), c);
}

// k 번째 원소 (0-indexed)
int kth(Node* t, int k) {
    push(t);
    int left_size = get_size(t->l);
    if (k == left_size) return t->val;
    if (k < left_size) return kth(t->l, k);
    return kth(t->r, k - left_size - 1);
}

핵심 구현 포인트:

• split(t, k): 왼쪽 서브트리 size 기준으로 재귀 분할
• merge(a, b): priority 큰 쪽을 루트로, 작은 쪽을 서브트리로 합침
• reverse: lazy_rev 플래그로 자식 swap 을 push down 까지 지연
• mt19937 로 priority 생성 (시드 고정하지 말 것)

응용

• 부분 reverse 가 들어가는 순열 시뮬레이션
• k 번째 원소 + 동적 삽입/삭제
• 구간 + 단일 갱신 + 구간 합 인데 인덱스가 동적
• persistent set / map 으로 시간 여행

함정

1. 무작위 priority 시드

같은 시드를 매번 쓰면 적대적 입력에 의해 worst-case 가 자주 나온다. time(0) + 추가 해시.

2. parent 포인터

split / merge 후 자식 변경 시 parent 갱신을 잊으면 splay / push down 이 어긋난다.

3. push down 누락

lazy 가 있는 BBST 에서 자식 접근 직전에 push down 하는 것이 표준. 빠뜨리면 stale lazy.

4. STL 로 대체 가능한지 확인

split / merge / 구간 연산이 필요 없으면 std::set 이 압도적으로 빠르다. BBST 는 정말 필요한 경우에만.

BOJ 연습 문제

기본

번호	제목	링크
BOJ 13159	배열	kokoa-lab
BOJ 17607	수열과 쿼리 31	kokoa-lab
BOJ 13543	수열과 쿼리 2	kokoa-lab
BOJ 2844	자료 구조	kokoa-lab
BOJ 19497	Subtract if Greater!	kokoa-lab
BOJ 15389	Imelda’s Shopping Spree	kokoa-lab

Persistent BBST

번호	제목	링크
BOJ 17486	수열과 쿼리 30	kokoa-lab

참고

• Segment Tree Beats
• Dynamic Tree (Splay 기반 Link/Cut Tree)
• Permutation Tree
• Stern-Brocot Tree