스플레이 트리 (Splay Tree)

스플레이 트리 (Splay Tree)

접근된 노드를 Splaying 연산으로 루트로 이동시키는 자가 조정 이진 탐색 트리로, 자주 접근하는 원소가 루트 근처에 위치하여 평균 O(log n) 성능 제공

목적: 자가 균형, 자주 사용 데이터 빠른 접근, 캐시 효과, 상각 분석

특징: 자가 조정, Splay 연산, 엄격한 균형 없음, 상각 O(log n)

Splay 연산 (회전 조합)

• •Zig: 부모가 루트일 때 단순 회전
• •Zig-Zig: 노드·부모·조부모가 같은 방향일 때, 조부모-부모 회전 → 부모-노드 회전
• •Zig-Zag: 노드·부모·조부모가 다른 방향일 때, 부모-노드 회전 → 조부모-노드 회전

연산

• •search: 노드 탐색 후 Splay, O(log n) 상각
• •insert: 삽입 후 Splay, O(log n) 상각
• •delete: 노드 Splay → 삭제 → 서브트리 병합, O(log n) 상각

시간 복잡도: 최악 O(n), 상각 O(log n)

공간 복잡도: O(n)

장점: 자동 캐시 효과, 단순 구현(균형 조건 없음), 상각 분석으로 효율 보장

단점: 최악 O(n), 단일 연산 성능 불안정, 멀티스레드 부적합

Working Set 정리: 최근 접근 원소일수록 빠른 접근 보장

적용사례: 캐시, 가비지 컬렉션, 네트워크 라우터, 동적 최적성 연구

비교: Splay(자가조정/상각) vs AVL(엄격균형/보장) vs Red-Black(완화균형/실용)

연관: 이진 탐색 트리, AVL, 회전, 상각 분석, 캐시