동적 최적성 추측(Dynamic Optimality Conjecture)
스플레이 트리(splay tree)는 스스로 구조를 조정하는(self-adjusting) 이진 탐색 트리로, 자주 접근되는 원소일수록 트리의 상단으로 이동시켜 이후 접근 속도를 높이도록 설계된 자료구조입니다. 이러한 스플레이 트리에는 이미 증명된 성능 보장 외에도, 아직 증명되지 않아 많은 관심을 받고 있는 추측이 하나 있습니다. 바로 동적 최적성 추측입니다.
임의의 이진 탐색 트리 알고리즘 B가 원소 y에 접근할 때, 루트에서 y까지의 경로를 따라 이동하며 d(y)+1의 비용이 든다고 가정합니다. 또한 각 접근 사이에는 트리 안에서 임의의 회전(rotation)을 수행할 수 있으며, 회전 한 번당 비용은 1이라고 가정합니다. B(s)를 알고리즘 B가 접근 순서열 s를 수행하는 데 드는 총비용이라고 정의하면, 스플레이 트리가 동일한 접근 순서열을 수행하는 비용은 다음과 같습니다.
O(n + B(s))
즉, 어떤 이진 탐색 트리 알고리즘과 비교하더라도 스플레이 트리는 상수 배 이내의 성능 차이만 보인다는 의미입니다. 이 추측이 참이라면, 스플레이 트리는 모든 온라인 이진 탐색 트리 알고리즘 중에서 사실상 최적이라고 말할 수 있습니다.
동적 최적성 추측으로부터 여러 흥미로운 따름정리(corollary)가 도출되지만, 아직까지 증명되지 않은 상태로 남아 있습니다. 대표적인 세 가지를 소개합니다.
1. 순회 추측(Traversal Conjecture)
같은 원소들을 담고 있는 두 개의 스플레이 트리 t1과 t2가 있다고 가정합시다. t2의 원소들을 전위 순회(preorder), 즉 깊이 우선 탐색(DFS) 순서로 방문하여 얻은 순서열을 s라고 할 때, t1에서 접근 순서열 s를 수행하는 전체 비용은 O(n)입니다.
2. 덱 추측(Deque Conjecture)
p개의 양방향 큐(deque, double-ended queue) 연산, 즉 push, pop, inject, eject로 구성된 순서열 s가 주어졌을 때, 스플레이 트리에서 이 순서열 s를 수행하는 비용은 O(p + n)입니다.
3. 분할 추측(Split Conjecture)
s를 스플레이 트리 원소들의 임의의 순열(permutation)이라고 합시다. 이때 s에 명시된 순서대로 원소들을 삭제하는 비용은 O(n)입니다.
이처럼 동적 최적성 추측과 그 따름정리들은 스플레이 트리가 이론적으로 얼마나 강력한 자료구조인지 보여주는 중요한 열린 문제들입니다. 오늘날에도 많은 연구자들이 이 추측들의 증명 혹은 반례 발견을 위해 노력하고 있으며, 이진 탐색 트리 이론의 핵심 난제 중 하나로 꼽히고 있습니다.