[1]   Georgii Maksimovich Adel’son-Vel’skii and Evgenii Mikhailovich Landis: An algorithm for organization of information. Dokl. Akad. Nauk SSSR (Russian), 146(2):263–266, 1962. Math-Net.ru.

[2]   Rudolf Bayer: Symmetric binary B-trees: Data structure and maintenance algorithms. Acta Informatica, 1(4):290–306, 1972. [doi:10.1007/BF00289509]

[3]   Prosenjit Bose, Karim Douïeb, John Iacono, and Stefan Langerman: The power and limitations of static binary search trees with lazy finger. Algorithmica, 76:1264–1275, 2016. Preliminary version in ISAAC’14. [doi:10.1007/s00453-016-0224-x]

[4]   Parinya Chalermsook, Julia Chuzhoy, and Thatchaphol Saranurak: Pinning down the strong Wilber 1 bound for binary search trees. In Proc. 23rd Internat. Conf. on Approximation Algorithms for Combinat. Opt. Probl. (APPROX’20), pp. 33:1–21. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.APPROX/RANDOM.2020.33]

[5]   Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak: Greedy is an almost optimal deque. In Proc. 17th Symp. on Algorithms and Data Structures (WADS’15), pp. 152–165. Springer, 2015. [doi:10.1007/978-3-319-21840-3_13]

[6]   Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak: Pattern-avoiding access in binary search trees. In Proc. 56th FOCS, pp. 410–423. IEEE Comp. Soc., 2015. [doi:10.1109/FOCS.2015.32, arXiv:1507.06953]

[7]   Ranjan Chaudhuri and Hartmut F. Höft: Splaying a search tree in preorder takes linear time. SIGACT News, 24(2):88–93, 1993. [doi:10.1145/156063.156067]

[8]   Richard Cole: On the Dynamic Finger Conjecture for splay trees. Part II: The proof. SIAM J. Comput., 30(1):44–85, 2000. [doi:10.1137/S009753979732699X]

[9]   Richard Cole, Bud Mishra, Jeanette Schmidt, and Alan Siegel: On the Dynamic Finger Conjecture for splay trees. Part I: Splay sorting log n-block sequences. SIAM J. Comput., 30(1):1–43, 2000. [doi:10.1137/S0097539797326988]

[10]   Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein: Introduction to Algorithms. MIT press, 2022. MIT Press.

[11]   Erik D. Demaine, Dion Harmon, John Iacono, Daniel M. Kane, and Mihai Pǎtraşcu: The geometry of binary search trees. In Proc. 20th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’09), pp. 496–505. SIAM, 2009. ACM DL.

[12]   Erik D. Demaine, Dion Harmon, John Iacono, and Mihai Pǎtraşcu: Dynamic optimality–almost. SIAM J. Comput., 37(1):240–251, 2007. Preliminary version in FOCS’04. [doi:10.1137/S0097539705447347]

[13]   Jonathan C. Derryberry and Daniel Dominic Sleator: Skip-splay: Toward achieving the unified bound in the BST model. In Proc. 11th Symp. on Algorithms and Data Structures (WADS’09), pp. 194–205. Springer, 2009. [doi:10.1007/978-3-642-03367-4_18]

[14]   Jonathan C. Derryberry, Daniel Dominic Sleator, and Chengwen Chris Wang: A lower bound framework for binary search trees with rotations. Technical report, CMU-CS-05-187, 2005. Available on author’s website.

[15]   Amr Elmasry: On the sequential access theorem and deque conjecture for splay trees. Theoret. Comput. Sci., 314(3):459–466, 2004. [doi:10.1016/j.tcs.2004.01.019]

[16]   George F. Georgakopoulos: Chain-splay trees, or, how to achieve and prove log log N-competitiveness by splaying. Inform. Process. Lett., 106(1):37–43, 2008. [doi:10.1016/j.ipl.2007.10.001]

[17]   Dion Harmon: New Bounds on Optimal Binary Search Trees. Ph. D. thesis, MIT, 2006. MIT.

[18]   John Iacono: In pursuit of the dynamic optimality conjecture. In A. Brodnik, A. López-Ortiz, V. Raman, and A. Viola, editors, Space-Efficient Data Structures, Streams, and Algorithms, volume 8066 of LNCS, pp. 236–250. Springer, 2013. [doi:10.1007/978-3-642-40273-9_16]

[19]   John Iacono and Stefan Langerman: Weighted dynamic finger in binary search trees. In Proc. 27th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’16), pp. 672–691. SIAM, 2016. [doi:10.1137/1.9781611974331.ch49]

[20]   László Kozma: Binary search trees, rectangles and patterns. Ph. D. thesis, Saarland University, Saarbrücken, Germany, 2016. Saarland U.

[21]   Victor Lecomte and Omri Weinstein: Settling the relationship between Wilber’s bounds for dynamic optimality. In Proc. 28th Eur. Symp. Algorithms (ESA’20), pp. 68:1–21. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.ESA.2020.68, arXiv:1912.02858]

[22]   Caleb C. Levy and Robert E. Tarjan: A new path from splay to dynamic optimality. In Proc. 30th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’19), pp. 1311–1330. SIAM, 2019. [doi:10.1137/1.9781611975482.80]

[23]   Joan M. Lucas: On the competitiveness of splay trees: Relations to the union-find problem. In Lyle A. McGeoch and Daniel D. Sleator, editors, On-line Algorithms, volume 7 of DIMACS Ser. in Discrete Math. and Theor. Comp. Sci., pp. 95–124. Amer. Math. Soc., 1992. [doi:10.1090/dimacs/007]

[24]   Seth Pettie: Splay trees, Davenport-Schinzel sequences, and the Deque Conjecture. In Proc. 19th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’08), pp. 1115–1124. SIAM, 2008. [doi:10.5555/1347082.1347204, arXiv:0707.2160]

[25]   Daniel Dominic Sleator and Robert Endre Tarjan: Self-adjusting binary search trees. J. ACM, 32(3):652–686, 1985. Preliminary version in STOC’83. [doi:10.1145/3828.3835]

[26]   Rajamani Sundar: On the Deque Conjecture for the splay algorithm. Combinatorica, 12(1):95–124, 1992. [doi:10.1007/BF01191208]

[27]   Robert Endre Tarjan: Sequential access in splay trees takes linear time. Combinatorica, 5(4):367–378, 1985. [doi:10.1007/BF02579253]

[28]   Chengwen C. Wang, Jonathan C. Derryberry, and Daniel Dominic Sleator: O(log log N)-competitive dynamic binary search trees. In Proc. 17th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’06), pp. 374–383. SIAM, 2006. ACM DL.

[29]   Robert E. Wilber: Lower bounds for accessing binary search trees with rotations. SIAM J. Comput., 18(1):56–67, 1989. Preliminary version in FOCS’86. [doi:10.1137/0218004]