I would like to ask a help from researchers who conduct a research in an area of search trees. Could you please write the list of the must-read papers and most recent papers which are important to read if I want to write papers about search trees.
I personally has the following list of papers (It's nonuniform, quite old and affects different topics. There is also a huge amount of papers about finger search tree but I didn't write references to them). Thank you for help.
Daniel Dominic Sleator and Robert Endre Tarjan. 1985. Self-adjusting binary search trees. J. ACM 32, 3 (July 1985), 652-686. DOI=http://dx.doi.org/10.1145/3828.3835
Daniel D. Sleator and Robert Endre Tarjan. 1983. A data structure for dynamic trees. J. Comput. Syst. Sci. 26, 3 (June 1983), 362-391. DOI=http://dx.doi.org/10.1016/0022-0000(83)90006-5
Scott Huddleston and Kurt Mehlhorn. 1982. A new data structure for representing sorted lists. Acta Inf. 17, 2 (June 1982), 157-184. DOI=http://dx.doi.org/10.1007/BF00288968
Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane, and Mihai Pătraşcu. 2009. The geometry of binary search trees. In Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '09). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 496-505.
Samuel W. Bent, Daniel D. Sleator, and Robert E. Tarjan. Biased Search Trees. SIAM Journal on Computing 1985 14:3, 545-568
Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, Thatchaphol Saranurak: Self-Adjusting Binary Search Trees: What Makes Them Tick? ESA 2015: 300-312
Since I conducted research in area of fast concatenation of search trees:
- Haim Kaplan and Robert E. Tarjan. 1996. Purely functional representations of catenable sorted lists. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (STOC '96). ACM, New York, NY, USA, 202-211. DOI=http://dx.doi.org/10.1145/237814.237865
- Purely Functional Worst Case Constant Time Catenable Sorted Lists. Lecture Notes in Computer Science. Gerth Stølting Brodal, Christos Makris, and Kostas Tsichlas. Algorithms – ESA 2006, Chapter 18, 172-183. Berlin, Heidelberg. http://link.springer.com/10.1007/11841036_18