스플레이 트리

스플레이 트리(splay tree)는 최근에 접근한 요소에 빠르게 다시 액세스할 수 있는 추가 속성이 있는 이진 탐색 트리이다. 자가 균형 이진 탐색 트리와 마찬가지로 스플레이 트리는 O(log n) 상각 시간 내에 삽입, 조회 및 제거와 같은 기본 작업을 수행한다. 균일하지 않은 무작위 분포에서 도출된 무작위 액세스 패턴의 경우 상각 시간은 액세스 패턴의 엔트로피에 비례하여 로그보다 빠를 수 있다. 무작위가 아닌 다양한 작업 패턴의 경우 패턴에 대한 사전 지식 없이도 스플레이 트리가 로그 시간보다 더 오래 걸릴 수 있다. 입증되지 않은 동적 최적성 추측에 따르면 모든 액세스 패턴에 대한 성능은 다른 자체 조정 이진 탐색 트리(해당 패턴에 맞게 선택된 트리 포함)에서 달성할 수 있는 최상의 성능의 상수 요소 내에 있다. 스플레이 트리는 1985년 다니엘 슬레이터(Daniel Sleator)와 로버트 타잔이 발명했다..

이진 탐색 트리의 모든 일반 작업은 스플레잉(splaying)이라는 하나의 기본 작업과 결합된다. 특정 요소에 대한 트리를 확장하면 해당 요소가 트리의 루트에 배치되도록 트리가 재배열된다. 기본 탐색 작업으로 이를 수행하는 한 가지 방법은 먼저 문제의 요소에 대한 표준 이진 트리 탐색을 수행한 다음 특정 방식으로 트리 회전을 사용하여 요소를 맨 위로 가져오는 것이다. 또는 하향식 알고리즘을 사용하여 탐색과 트리 재구성을 단일 단계로 결합할 수 있다.

 같이 보기 
 AVL 트리
 B 트리
 스케이프고트 트리
 Treap
 트리 회전
 트리 구조

 각주 

 출처 

 외부 링크 
 NIST's Dictionary of Algorithms and Data Structures: Splay Tree
 Implementations in C and Java (by Daniel Sleator)
 Pointers to splay tree visualizations
 Fast and efficient implementation of Splay trees
 Top-Down Splay Tree Java implementation
 Zipper Trees

분류:이진 트리
분류:분할 상환 자료 구조
분류:탐색 트리