가상 트리에서 일부 모서리는 솔리드로 처리되고 일부는 대시로 처리됩니다. 일반적인 펼침은 단단한 나무에서만 수행됩니다. 가상 트리의 노드 y에서 재생하기 위해 다음과 같은 방법이 구현됩니다.
알고리즘은 각 패스에서 한 번씩 트리를 세 번 보고 변경합니다. 첫 번째 패스에서는 노드 y에서 시작하여 솔리드 트리에서만 확장되어 y에서 전체 트리의 루트까지의 경로가 점선이 됩니다. 이 경로는 접합에 의해 생성됩니다. 노드 y에서의 마지막 분할은 이제 y 트리의 루트를 생성합니다. 덜 비공식적으로 알고리즘은 다음과 같이 설명됩니다.
Splay(y) 알고리즘
통과 1 가상 트리 위로 올라가지만 확고한 하위 트리 내에서만 확장이 수행됩니다. 이 패스가 끝나면 y에서 루트로의 경로가 파선으로 바뀝니다.
통과 2 노드 y에서 위로 걸어 올라가 y의 각 적절한 조상에서 접합합니다. 이 단계가 끝나면 y에서 루트까지의 경로가 솔리드가 됩니다. 단, 노드 y와 원래 트리의 모든 자식(패스 1 이전의 것)은 이제 왼쪽 자식이 됩니다.
패스 3 노드 y에서 루트까지 일반적인 방식으로 펼칩니다.
이를 통해 사전 지식을 활용하여 확률 추정을 개선할 수 있습니다. 주어진 잎 세트에 대해. 따라서 목표는 최소 외부 경로 가중치로 트리를 구성하는 것입니다.
아래에 예가 나와 있습니다.
문자 빈도 테이블
| 편지 | z | k | 분 | ㄷ | 유 | d | 나 | 이 |
| 빈도 | 2 | 7 | 24 | 32 | 37 | 42 | 42 | 120 |
허프만 코드
| 문자 | 빈도 | 코드 | 비트 |
|---|---|---|---|
| e | 120 | 0 | 1 |
| d | 42 | 101 | 3 |
| 나 | 42 | 110 | 3 |
| 너 | 37 | 37100 | 3 |
| ㄷ | 32 | 1110 | 4 |
| m | 24 | 11111 | 5 |
| k | 7 | 111101 | 6 |
| z | 2 | 111100 | 6 |
허프만 트리(위의 예)는 다음과 같습니다.
