스플레이 트리

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

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

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

• Afek, Yehuda; Kaplan, Haim; Korenfeld, Boris; Morrison, Adam; Tarjan, Robert E. (2014). “The CB tree: a practical concurrent self-adjusting search tree”. 《Distributed Computing》 27 (6): 393–417. doi:10.1007/s00446-014-0229-0. 
• Albers, Susanne; Karpinski, Marek (2002년 2월 28일). “Randomized Splay Trees: Theoretical and Experimental Results” (PDF). 《Information Processing Letters》 81 (4): 213–221. doi:10.1016/s0020-0190(01)00230-7. 
• Allen, Brian; Munro, Ian (October 1978). “Self-organizing binary search trees”. 《Journal of the ACM》 25 (4): 526–535. doi:10.1145/322092.322094. S2CID 15967344. 
• Brinkmann, Gunnar; Degraer, Jan; De Loof, Karel (January 2009). “Rehabilitation of an unloved child: semi-splaying” (PDF). 《Software: Practice and Experience》 39 (1): 33–45. CiteSeerX 10.1.1.84.790. doi:10.1002/spe.v39:1. hdl:11382/102133. The results show that semi-splaying, which was introduced in the same paper as splaying, performs better than splaying under almost all possible conditions. This makes semi-splaying a good alternative for all applications where normally splaying would be applied. The reason why splaying became so prominent while semi-splaying is relatively unknown and much less studied is hard to understand. 
• Cole, Richard; Mishra, Bud; Schmidt, Jeanette; Siegel, Alan (January 2000). “On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences”. 《SIAM Journal on Computing》 30 (1): 1–43. CiteSeerX 10.1.1.36.4558. doi:10.1137/s0097539797326988. 
• Cole, Richard (January 2000). “On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof”. 《SIAM Journal on Computing》 30 (1): 44–85. CiteSeerX 10.1.1.36.2713. doi:10.1137/S009753979732699X. 
• Elmasry, Amr (April 2004). “On the sequential access theorem and Deque conjecture for splay trees”. 《Theoretical Computer Science》 314 (3): 459–466. doi:10.1016/j.tcs.2004.01.019. 
• Goodrich, Michael; Tamassia, Roberto; Goldwasser, Michael (2014). 《Data Structures and Algorithms in Java》 (영어) 6판. Wiley. 506쪽. ISBN 978-1-118-77133-4. 
• Grinberg, Dennis; Rajagopalan, Sivaramakrishnan; Venkatesan, Ramarathnam; Wei, Victor K. (1995). 〈Splay trees for data compression〉. Clarkson, Kenneth L. 《Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 22–24 January 1995. San Francisco, California, USA》. ACM/SIAM. 522–530쪽. Average depth of access in a splay tree is proportional to the entropy. 
• Knuth, Donald (1997). 《The Art of Computer Programming》. 3: Sorting and Searching 3판. Addison-Wesley. 478쪽. ISBN 0-201-89685-0. The time needed to access data in a splay tree is known to be at most a small constant multiple of the access time of a statically optimum tree, when amortized over any series of operations. 
• Lucas, Joan M. (1991). 〈On the Competitiveness of Splay Trees: Relations to the Union-Find Problem〉. 《On-line Algorithms: Proceedings of a DIMACS Workshop, February 11–13, 1991》. Series in Discrete Mathematics and Theoretical Computer Science 7. Center for Discrete Mathematics and Theoretical Computer Science. 95–124쪽. ISBN 0-8218-7111-0. 
• Pettie, Seth (2008). 《Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture》 (PDF). 《Proc. 19th ACM-SIAM Symposium on Discrete Algorithms》 0707. 1115–1124쪽. arXiv:0707.2160. Bibcode:2007arXiv0707.2160P. 
• Sleator, Daniel D.; Tarjan, Robert E. (1985). “Self-Adjusting Binary Search Trees” (PDF). 《Journal of the ACM》 32 (3): 652–686. doi:10.1145/3828.3835. S2CID 1165848. 
• Sundar, Rajamani (1992). “On the Deque conjecture for the splay algorithm”. 《Combinatorica》 12 (1): 95–124. doi:10.1007/BF01191208. S2CID 27422556. 
• Tarjan, Robert E. (1985). “Sequential access in splay trees takes linear time”. 《Combinatorica》 5 (4): 367–378. doi:10.1007/BF02579253. S2CID 34757821. 
• Bender, Michael A.; Conway, Alex; Farach-Colton, Martin; Kuszmaul, William; Tagliavini, Guido (2023). “Tiny Pointers”. 《Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)》: 477–508. doi:10.1137/1.9781611977554.ch21. ISBN 978-1-61197-755-4. S2CID 244709005. 

• NIST's Dictionary of Algorithms and Data Structures: Splay Tree
• Implementations in C and Java (by Daniel Sleator)
• Pointers to splay tree visualizations
• Fast and efficient implementation of Splay trees
• Top-Down Splay Tree Java implementation
• Zipper Trees