스플레이 트리 편집하기

스플레이 트리(splay tree)는 이진 탐색 트리(binary search tree)의 일종으로, 자주 접근하는 노드를 루트에 가깝게 이동시켜 전체적인 접근 효율을 높이는 '''자기 조정형(self-adjusting) 트리'''이다. 1985년 Sleator와 Tarjan에 의해 제안되었으며, 평균적으로 효율적인 탐색 성능을 보장한다.
==개념==
스플레이 트리는 노드에 접근할 때마다 해당 노드를 루트로 올리는 회전 연산(splaying)을 수행한다. 이로 인해 자주 접근하는 노드는 루트 근처에 있게 되어 이후 접근이 빨라진다.

스플레이 연산은 다음 세 가지 패턴을 기준으로 회전한다:
#'''Zig (지그)'''
#*대상 노드가 루트의 자식일 때 한 번의 회전
#'''Zig-Zig (지그-지그)'''
#*대상 노드와 부모가 모두 왼쪽 또는 오른쪽 자식일 때 두 번 연속 같은 방향으로 회전
#'''Zig-Zag (지그-재그)'''
#*대상 노드가 왼쪽 자식이고 부모가 오른쪽 자식이거나, 그 반대인 경우 → 교차 방향 회전
==연산==
*검색(search)
**노드를 찾은 후 splay 연산을 통해 해당 노드를 루트로 올림
*삽입(insert)
**일반적인 BST 방식으로 삽입 후, 그 노드를 루트로 splay
*삭제(delete)
**삭제할 노드를 splay한 뒤 루트에서 제거 → 두 서브트리를 합치는 과정 필요
==성능==
*각 연산의 '''최악 시간복잡도는 O(n)'''이지만, '''평균적으로는 O(log n)'''
*'''암시적 캐싱 효과'''로 인해 자주 쓰이는 데이터는 빠르게 접근 가능
*모든 연산이 동일한 splay 연산으로 구성되므로 구현이 단순
==예시==
노드 20, 10, 30, 5, 15, 25, 35가 삽입된 트리에서 노드 5를 탐색하면, 5는 루트로 올라가고 구조가 재조정된다. 이후 노드 5에 재접근하면 O(1)에 가능할 수 있다.
==장점==
*최근에 접근한 노드에 더 빠르게 접근 가능
*명시적 균형 정보를 저장하지 않아도 트리가 자동으로 균형 잡힘
*삽입, 삭제, 탐색이 동일한 구조의 코드로 구현됨
==단점==
*균형 유지가 명시적이지 않아 트리 높이가 불안정할 수 있음
*특정 연산에 대해서는 AVL 트리, 레드-블랙 트리보다 느릴 수 있음
==같이 보기==
*[[이진 탐색 트리]]
*[[AVL 트리]]
*[[레드-블랙 트리]]
*[[자기 조정형 자료구조]]
*[[트리 회전]]
==참고 문헌==
*Sleator, D. D., & Tarjan, R. E. (1985). Self-adjusting binary search trees. Journal of the ACM (JACM), 32(3), 652–686
*Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press
[[분류:트리 이론]]
[[분류:알고리즘]]