정적 손가락 정리(Static Finger Theorem)란?
정적 손가락 정리는 스플레이 트리(Splay Tree)의 성능을 분석하는 대표적인 이론 중 하나입니다. 스플레이 트리는 자기 조절(self-adjusting) 이진 탐색 트리로, 자주 접근되는 항목일수록 트리의 루트에 가깝게 배치되어 빠른 접근이 가능합니다. 정적 손가락 정리는 이러한 스플레이 트리가 특정 고정된 위치(손가락) 근처의 항목들에 반복적으로 접근할 때 얼마나 효율적인지를 수학적으로 보여줍니다.
정리의 정의
STATIC FINGER THEOREM — 트리 내의 특정 원소 하나를 기준점으로 삼고 이를 손가락(finger)이라고 부릅니다. 이때 손가락 f를 기준으로 수행되는 일련의 스플레이 연산 비용은 아래 식으로 상한(bound)이 주어집니다.
O(m + n log(n) + Σ log(|f − i[j]| + 1))
NOTE — 여기서 |f − i|는 손가락 f와 항목 i 사이의 대칭 순서(symmetric order) 상의 거리를 의미합니다. 즉, 두 항목이 트리에서 중위 순회(in-order) 기준으로 몇 칸 떨어져 있는지를 나타냅니다.
각 변수의 의미
식에 등장하는 주요 변수들은 다음과 같습니다.
m — 최대 n개의 노드를 가진 트리에 대해 수행되는 갱신(update) 또는 접근(access) 연산의 총 횟수입니다.
n — 트리가 가질 수 있는 최대 노드 수입니다.
f — 기준이 되는 고정된 손가락(finger) 항목입니다.
i[j] — j번째 연산에서 접근하는 항목입니다.
정리가 주는 시사점
이 정리의 핵심은 분할상환(amortized) 관점에서 도출됩니다. 노드 수가 n을 넘지 않는 트리에 대해 처음 m번의 연산을 수행하는 데 걸리는 시간은, AVL 트리나 2-3 트리 같은 균형 이진 탐색 트리(balanced binary search tree)에서 소요되는 시간과 유사하다는 것입니다.
즉, 접근 패턴이 특정 위치(손가락) 근처에 집중되어 있다면, 추가 항 Σ log(|f − i[j]| + 1)의 값이 작아져 전체 비용이 크게 줄어듭니다. 반대로 손가락에서 멀리 떨어진 항목에만 계속 접근하면 이 항이 커져 비용이 증가합니다. 이는 스플레이 트리가 국소성(locality of reference)이 높은 워크로드에서 특히 강력한 성능을 발휘한다는 점을 잘 보여줍니다.