10
$\begingroup$

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
Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

Sleator-Tarjan '85 and Demaine et al '09 definitely belong on any such list. There is a lot of other recent work related to splay trees and dynamic optimality, for instance:

  • Applications of forbidden 0-1 matrices to search tree and path compression-based data structures, Seth Pettie, SODA 2010
  • An O (log log n)-competitive binary search tree with optimal worst-case access times, Bose et al, SWAT 2010
  • Upper bounds for maximally greedy binary search trees, Kyle Fox, WADS 2011.
  • De-amortizing binary search trees, Bose et al, ICALP 2012
  • Pattern-avoiding access in binary search trees, Chalermsook et al, FOCS 2015
  • Weighted dynamic finger in binary search trees, Iacono and Langerman, SODA 2016

On more classical lines, I think

  • Rank-balanced trees, Haeupler, Sen, and Tarjan, ACM TALG 2015

is worth including as an elegant unification of AVL and red-black trees.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.