스플레이 트리란 무엇인가?
스플레이 트리(splay tree)는 최근에 접근한 요소를 다시 빠르게 찾을 수 있다는 독특한 속성을 가진 자가 균형(self-balancing) 이진 탐색 트리입니다. 이 자료구조는 1985년 다니엘 슬레이터(Daniel Sleator)와 로버트 타잔(Robert Tarjan)이 제안했으며, 삽입·조회·삭제와 같은 기본 연산을 분할 상환(amortized) 시간 O(log n) 안에 처리할 수 있습니다.
흥미로운 점은, 연산 시퀀스의 특정 패턴을 미리 알지 못하더라도 비무작위(non-random) 연산이 반복되는 많은 상황에서 스플레이 트리가 다른 탐색 트리보다 우수한 성능을 보인다는 것입니다. 이는 최근 사용된 데이터가 트리 상단으로 올라와 다음 접근이 빨라지기 때문입니다.
이진 탐색 트리의 기본 속성
설명의 편의를 위해 각 노드 a에 실수(real number) 형태의 키 값 key(a)를 저장한다고 가정하겠습니다.
모든 이진 탐색 트리에서는 다음 속성이 유지됩니다.
- 임의의 노드 a의 왼쪽 서브트리에는 key(a)보다 작은 키 값을 가진 항목들이 위치합니다.
- 노드 a의 오른쪽 서브트리에는 key(a)보다 큰 키 값을 가진 항목들이 위치합니다.
스플레이 트리의 검색과 회전 과정
스플레이 트리에서의 검색은 일반적인 이진 탐색 트리와 동일하게 시작됩니다. 질의 항목 a를 루트의 값과 비교하여, 더 작으면 왼쪽 서브트리를 재귀적으로 탐색하고, 더 크면 오른쪽 서브트리를 재귀적으로 탐색하며, 값이 같으면 탐색이 종료됩니다.
검색 이후가 스플레이 트리의 핵심입니다. 대상 노드 a의 연속된 조상들을 서로소(disjoint) 쌍으로 묶어 살펴봅니다. 예를 들어 b = parent(a), c = parent(b)라고 할 때, 각 쌍에 대해 특정한 회전(rotation) 연산을 수행합니다. 이러한 회전들이 진행되면서 노드 a는 점차 위로 올라가 결국 c의 자리를 차지하게 되며, 최종적으로는 트리의 루트까지 이동합니다. 이 전체 과정을 '스플레잉(splaying)'이라고 부릅니다.
세 가지 기본 회전 단계
스플레잉은 노드 a와 그 조상들의 배치 관계에 따라 세 가지 단계로 나뉩니다.
1. 지그(Zig) 단계 — 종단 경우
a가 홀수 개의 적절한(proper) 조상을 가지는 경우, 마지막에 남는 a의 조상(루트의 직접적인 자식)은 별도로 처리해야 합니다. 이 종단 경우(terminal case)에서는 a와 루트 사이의 간선(edge)을 한 번 회전합니다. 이 단계를 지그(zig) 단계라고 합니다.
2. 지그-지그(Zig-Zig) 단계
a와 b가 같은 방향의 자식, 즉 둘 다 각자 부모의 왼쪽 자식이거나 둘 다 오른쪽 자식인 경우입니다. 이때는 먼저 b와 그 부모 c 사이의 간선을 회전한 후, 이어서 a와 그 부모 b 사이의 간선을 회전합니다. 이 순서의 두 번 회전을 지그-지그(zig-zig) 단계라고 합니다.
3. 지그-재그(Zig-Zag) 단계
a와 b가 반대 방향의 자식, 즉 a가 왼쪽(또는 오른쪽) 자식이고 b가 오른쪽(또는 왼쪽) 자식인 경우입니다. 이때는 먼저 a와 b 사이의 간선을 회전한 후, 이어서 a와 c 사이의 간선을 회전합니다. 이 단계를 지그-재그(zig-zag) 단계라고 합니다.
마무리
스플레이 트리는 균형 정보를 별도로 저장하지 않으면서도 분할 상환 O(log n)의 성능을 보장하는 우아한 자료구조입니다. 지그·지그-지그·지그-재그라는 세 가지 회전 규칙만 정확히 이해하면 스플레잉의 동작 원리를 명확하게 파악할 수 있으며, 이는 캐시 친화적인 응용 프로그램이나 네트워크 라우팅 테이블 등 접근 지역성(locality of reference)이 중요한 분야에서 특히 유용하게 활용됩니다.