스플레이 트리

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

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

같이 보기

• AVL 트리
• B 트리
• 스케이프고트 트리
• Treap
• 트리 회전
• 트리 구조