동적 최적성 추측
splay tree에 대한 입증된 성능 보장 외에도 많은 관심을 갖고 있는 입증되지 않은 추측이 있습니다. 동적 최적성 추측은 이 추측을 나타냅니다. B와 같은 이진 탐색 트리 알고리즘이 d(y)+1의 비용으로 루트에서 y까지의 경로를 순회하여 요소 y에 액세스하도록 하고 액세스 간에는 1/1의 비용으로 트리에서 회전을 만들 수 있습니다. 회전. B(s)를 B가 액세스 시퀀스 s를 수행하는 비용이라고 하자. 그러면 동일한 액세스를 수행하기 위한 스플레이 트리의 비용은 O[n+B(s)]입니다.
증명되지 않은 상태로 남아 있는 동적 최적성 추측의 결과가 너무 많습니다.
순회 추측 et 동일한 요소는 두 개의 스프레이 트리 t1 및 t2에 포함됩니다. t2의 요소를 사전 순서(즉, 깊이 우선 탐색 순서)로 방문하여 얻은 시퀀스를 s로 가정합니다. t1에 대한 일련의 액세스를 수행하는 데 드는 전체 비용은 O(n)입니다.
데크 추측 p 양방향 대기열 작업(푸시, 팝, 주입, 꺼내기)의 시퀀스가 정의됩니다. 그러면 스플레이 트리에서 s 시퀀스를 수행하는 비용은 O(p+n)입니다.
분할 추측 et s는 splay 트리 요소의 순열입니다. 그러면 순서 s의 요소를 삭제하는 데 드는 비용은 O(n)입니다.