
개요Splay Tree는 자주 접근하는 노드를 루트로 끌어올려 접근 성능을 최적화하는 자가 조정형(Self-adjusting) 이진 탐색 트리입니다. 특별한 균형 기준 없이, 최근 접근 노드를 우선시하며 트리 구조를 동적으로 재조정하는 방식으로, 캐시 성능을 높이고 평균 연산 시간을 줄이는 데 효과적입니다.1. 개념 및 정의Splay Tree는 1985년 Sleator와 Tarjan에 의해 제안된 트리 자료구조로, 검색·삽입·삭제 연산 시 해당 노드를 루트로 끌어올리는(Splay) 과정을 통해 접근 성능을 개선합니다.목적: 자주 접근되는 노드를 빠르게 찾기 위한 트리 구조 최적화특징: 별도의 균형 조건 없이도 amortized O(log n) 성능 보장구조: 이진 탐색 트리의 변형 형태2. 연산 구조Sp..