한양과기고 에듀테크 수업도구 대시보드

방금 접근한 노드를 루트로 끌어올리는 트리

AVL·레드-블랙 트리는 항상 균형을 강제해서 최악에도 O(log n)을 보장한다. 스플레이 트리는 다른 전략을 쓴다 — 균형 규칙이 따로 없는 대신, 노드를 삽입하거나 검색할 때마다 그 노드를 회전으로 루트까지 끌어올린다(splay). 단 한 번의 접근은 최악 O(n)일 수 있지만, 자주 쓰는 값이 트리 위쪽에 몰려 있게 되어 여러 번 접근한 평균(amortized)은 O(log n)이 된다. "최근에 만진 것이 다음에도 또 필요하다"는 지역성(locality of reference)을 구조 자체가 활용하는 셈이다.

삽입 · 검색 시뮬레이터

값을 삽입하거나 검색하면, 그 값을 담은 노드가 zig / zig-zig / zig-zag 회전을 거쳐 루트로 이동한다. 같은 값을 여러 번 검색해 보면 그 값이 계속 트리 꼭대기 근처에 머무는 것을 볼 수 있다.

노드 수 n

트리 높이

누적 회전 횟수

값을 삽입하거나 검색하면 splay 과정이 여기에 표시됩니다.

💡 같은 값을 검색 버튼으로 반복해서 눌러 보자. 첫 접근에서는 깊은 곳까지 내려가지만, splay 때문에 루트가 되고, 두 번째부터는 즉시 찾아진다 — 캐시처럼 동작하는 이유다.

세 가지 splay 동작 — zig · zig-zig · zig-zag

splay는 대상 노드 x가 루트가 될 때까지 부모·조부모와의 상대적 위치에 따라 아래 세 가지 중 하나를 반복한다. 매번 중위 순회 순서(BST 성질)는 그대로 유지된다.

Zig — 부모가 루트일 때 (1번만 발생)

x와 부모 p 사이를 한 번만 회전한다.

  p          x
 /            \
x     ──▶    p

Zig-Zig — x, p가 같은 쪽 자식

조부모 g를 먼저 돌리고, 그 다음 p를 돌린다 (먼 것부터).

    g          p
   /          / \
  p    ──▶   x   g
 /
x

Zig-Zag — x, p가 반대쪽 자식

AVL의 이중 회전과 비슷하게, x를 두 번 연속 돌려 곧장 조부모 자리로 올린다.

g          g          x
 \          \        / \
  p   ──▶   x   ──▶ g   p
 /            \
x              p

Zig-Zig을 "부모부터" 먼저 도는 이유가 핵심이다. x부터 두 번 돌리면 일반 BST 재조정과 다를 게 없어 한쪽으로 길게 늘어진 모양이 그대로 남는다. 조부모부터 돌리면 늘어진 경로가 반으로 접혀 트리가 납작해지고, 이 덕분에 국소적으로 나쁜 접근이 이어져도 전체 평균은 O(log n)으로 수렴한다(포텐셜 함수로 증명 — 분할 상환 분석의 대표 사례).

splay 함수

회전 자체는 AVL·레드-블랙과 같은 rotate_left / rotate_right다. 다른 점은 "균형이 깨졌을 때"가 아니라 접근할 때마다 무조건 이 루프를 돈다는 것.

# x가 루트가 될 때까지 반복 def splay(x): while x.parent: p = x.parent g = p.parent if g is None: # zig rotate(p, toward=opposite_side(x, p)) elif side(x, p) == side(p, g): # zig-zig: g부터! rotate(g, toward=opposite_side(p, g)) rotate(p, toward=opposite_side(x, p)) else: # zig-zag rotate(p, toward=opposite_side(x, p)) rotate(g, toward=opposite_side(x, g)) root = x def insert(key): z = bst_insert(key) # 평범한 BST 삽입 splay(z) # 방금 넣은 노드를 루트로 def search(key): node, last = bst_find_or_last_touched(key) splay(last) # 찾았든 못 찾았든, 마지막으로 본 노드를 루트로 return node

AVL · 레드-블랙 트리와 비교

	스플레이 트리	AVL / 레드-블랙
균형 유지 방식	접근할 때마다 splay (규칙 없음)	삽입·삭제 때 규칙 위반만 교정
단일 연산 최악	`O(n)` 가능 (한쪽으로 늘어진 상태)	항상 `O(log n)` 보장
m번 접근 총합	`O(m log n)` (분할 상환)	`O(m log n)` (매번 보장)
추가 정보	없음 (색·높이 필드 불필요)	색 비트 또는 균형 인수 저장
강점	자주 쓰는 값이 자동으로 빨라짐 (지역성)	접근 패턴과 무관하게 예측 가능한 속도
쓰이는 곳	GCC 내부 자료구조, 네트워크 라우터 캐시, LRU 유사 캐시	DB 인덱스, C++ `std::map`, 리눅스 스케줄러

요약: 접근 패턴이 편중되어 있으면(핫스팟이 있으면) 스플레이 트리가 유리하다 — 실시간 성능 보장이 필요 없고 평균이 중요한 상황에 적합하다. 매 연산 속도가 균일해야 하면 AVL·레드-블랙이 안전하다.

자주 나오는 질문

💡 삭제는 어떻게 하나?

지울 노드 x를 먼저 splay로 루트까지 올린다. 루트가 되면 왼쪽 서브트리 L과 오른쪽 서브트리 R로 쪼개지는데, x를 버리고 L에서 가장 큰 값을 splay로 루트로 올린 다음 그 오른쪽 자식으로 R을 붙이면 끝난다.

💡 왜 "최악 O(n)"인데 쓸 만한가?

포텐셜 함수(각 노드 크기의 로그 합)를 이용한 분할 상환 분석으로, 어떤 접근 순서를 넣어도 m번의 연산 총 비용이 O((m+n) log n)을 넘지 않음이 증명되어 있다. 가끔 한 번 느려도 그 대가로 이후 접근이 훨씬 빨라지는 식으로 상쇄된다 — 분할 상환 분석 문서의 동적 배열 확장과 같은 논리다.

💡 이진 탐색 트리(BST) 성질이 회전 후에도 유지되나?

그렇다. zig·zig-zig·zig-zag 모두 AVL·레드-블랙과 동일한 기본 회전을 조합한 것뿐이라 중위 순회 결과(정렬 순서)는 절대 바뀌지 않는다. 오직 어떤 노드가 트리의 "위쪽"에 있는지만 바뀐다.