가상 트리(virtual tree)에서는 일부 간선을 실선(solid)으로, 나머지 간선을 점선(dashed)으로 취급합니다. 일반적인 스플레이 연산은 실선으로만 연결된 트리(solid tree) 내부에서 수행되며, 가상 트리 전체를 한꺼번에 회전시키지 않습니다.
가상 트리의 특정 노드 y에서 스플레이를 수행하려면 다음 절차를 따릅니다. 이 알고리즘은 트리를 총 세 번 순회하면서(각 패스마다 한 번씩) 구조를 점진적으로 변경합니다.
Splay(y) 알고리즘
패스 1: 가상 트리를 루트 방향으로 거슬러 올라가되, 스플레이는 실선 서브트리 내부에서만 수행합니다. 이 패스가 끝나면 y부터 전체 트리의 루트까지의 경로는 점선 상태가 됩니다.
패스 2: 노드 y에서 위로 올라가면서 y의 모든 적절한 조상(proper ancestor)에서 스플라이싱(splicing)을 수행합니다. 이 단계가 끝나면 y부터 루트까지의 경로는 실선으로 바뀝니다. 또한 원래 트리(패스 1 이전의 트리)에서 y와 그 자식들이었던 노드들은 모두 왼쪽 자식 위치로 이동합니다.
패스 3: 노드 y에서 루트까지 올라가며 일반적인 방식으로 스플레이를 수행합니다. 그 결과 노드 y가 전체 트리의 루트가 됩니다.
최소 외부 경로 가중치 트리와 허프만 코드
이러한 트리 구성 기법은 사전 지식을 활용해 확률 추정의 정확도를 높이는 데에도 응용됩니다. 주어진 리프(leaf) 집합에 대해 외부 경로 가중치(external path weight)가 최소가 되는 트리를 구성하는 것이 목표이며, 대표적인 사례가 바로 허프만 코딩(Huffman coding)입니다.
다음은 문자별 빈도표 예시입니다.
| 문자 | z | k | m | c | u | d | l | e |
| 빈도 | 2 | 7 | 24 | 32 | 37 | 42 | 42 | 120 |
위 빈도표를 바탕으로 생성한 허프만 코드는 다음과 같습니다.
| 문자 | 빈도 | 코드 | 비트 수 |
|---|---|---|---|
| e | 120 | 0 | 1 |
| d | 42 | 101 | 3 |
| l | 42 | 110 | 3 |
| u | 37 | 100 | 3 |
| c | 32 | 1110 | 4 |
| m | 24 | 11111 | 5 |
| k | 7 | 111101 | 6 |
| z | 2 | 111100 | 6 |
전체 인코딩 비용은 (빈도 × 비트 수)의 합으로 계산되며, 이 예제에서는 785비트가 됩니다. 즉, 빈도가 높은 문자일수록 짧은 코드를 배정함으로써 전체 경로 가중치를 최소화할 수 있습니다.
위 예제의 허프만 트리는 아래 그림과 같습니다.
