스플레이 트리

접근이 구조를 바꾼다

키를 탐색한 뒤 해당 노드를 루트로 올리면서 연결을 다시 배치한다. 키를 지우거나 추가하지 않는 조회도 트리 모양을 바꿀 수 있다. 각 회전은 이진 탐색 트리의 정렬 순서를 보존하므로 모양이 달라져도 키의 대소 관계는 유지된다.

회전 조합

부모가 루트일 때는 한 번의 회전으로 끝낸다. 그 외에는 현재 노드와 부모가 같은 방향의 자식인지 반대 방향인지에 따라 두 번의 회전 순서를 정한다. 단순히 매번 현재 노드만 부모 위로 올리는 방법과는 다르며 이 차이가 비용 분석에서 중요하다.

분할 상환의 뜻

개별 연산의 비용이 늘 작다는 보장이 아니라 최악의 연산열 전체에 걸친 비용을 나누어 평가한다. 한 번 깊은 노드를 찾는 데 선형 시간이 들더라도 이후의 구조 변화까지 함께 분석한다. 무작위 입력에서의 평균 시간이나 확률적 기대 시간과 같은 개념으로 취급하면 안 된다.

균형 트리와의 차이

AVL 트리의 높이 차나 적흑 트리의 색 조건 같은 명시적인 균형 정보를 기본 구성에서 유지하지 않는다. 자주 접근하는 항목을 루트 가까이 옮기며 접근 패턴에 적응할 수 있다. 그러나 매 요청의 지연 상한이 엄격한 상황에서는 한 번의 연산이 길어질 수 있다는 점을 고려해야 한다.