교수: Jelani Nelson |
1985 년 다니엘 Sleator 와 로버트 Tarjan 이 발명 하였습니다.
스플레이 트리는 최근에 액세스한 요소를 다시 액세스할 때
시간을 줄여주는 추가 속성이 있는 이진 검색 트리입니다.
스플레이 트리의 삽입, 조회 및 삭제시 작업 수행시간은
O(log n)
입니다.
( 자체 균형-이진 검색 트리의 수행시간과 같습니다. )
비균일 분포에서 추출한 랜덤 액세스 패턴의 경우
감소 시간은 엔트로피에 비례하여 log 보다 빠를 수 있습니다.
랜덤 액세스 패턴이 아닌 연산 패턴의 경우
스플레이 트리는 패턴에 대한 정보가 없는 경우 조차
log 보다 더 효율적일 수 있습니다.
* 다이나믹 최적성 추측
액세스 패턴에 대한 성능은 다른 자체 조정-이진 검색 트리 즉,
해당 패턴에 맞게 선택한 하나의 트리에서 조차 달성 가능한
성능의 칸스턴트한 요인 내에 있을 것이다.
이진 검색 트리의 일반 작업은 스플레잉 이라는 하나의 기본
작업으로 결합 합니다.
특정 요소에 대한 트리를 스플레잉 할 때
해당 요소가 트리의 루트에 배치 하게끔 트리를 재정렬 합니다.
기본 검색 작업으로 이를 수행하는 방법은 이렇습니다.
해당 요소에 대한 표준 이진 트리 검색을 수행한 다음에
특정 방법으로 트리 로테이션을 써서 요소를 맨 위로 가져옵니다.
아니면 탑다운 알고리즘이 검색과 트리 재구성을 단일 스텝으로
결합할 수 있습니다.
자료출처 위키백과