<p>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:</p>

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

<p>On more classical lines, I think</p>

<ul>
<li>Rank-balanced trees, Haeupler, Sen, and Tarjan, ACM TALG 2015</li>
</ul>

<p>is worth including as an elegant unification of AVL and red-black trees.</p>

CC BY-SA 3.0
2016-08-05T00:48:40.900Z
2016-08-05T00:48:40.900Z
David Eppstein
<p>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.</p>

<p>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. </p>

<ul>
<li><p>Daniel Dominic Sleator and Robert Endre Tarjan. 1985. Self-adjusting binary search trees. J. ACM 32, 3 (July 1985), 652-686. DOI=<a href="http://dx.doi.org/10.1145/3828.3835">http://dx.doi.org/10.1145/3828.3835</a></p></li>
<li><p>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=<a href="http://dx.doi.org/10.1016/0022-0000(83)90006-5">http://dx.doi.org/10.1016/0022-0000(83)90006-5</a></p></li>
<li><p>Scott Huddleston and Kurt Mehlhorn. 1982. A new data structure for representing sorted lists. Acta Inf. 17, 2 (June 1982), 157-184. DOI=<a href="http://dx.doi.org/10.1007/BF00288968">http://dx.doi.org/10.1007/BF00288968</a></p></li>
<li><p>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.</p></li>
<li><p>Samuel W. Bent, Daniel D. Sleator, and Robert E. Tarjan. Biased Search Trees. SIAM Journal on Computing 1985 14:3, 545-568</p></li>
<li><p>Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, Thatchaphol Saranurak:
Self-Adjusting Binary Search Trees: What Makes Them Tick? ESA 2015: 300-312</p></li>
</ul>

<p>Since I conducted research in area of fast concatenation of search trees:</p>

<ul>
<li>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=<a href="http://dx.doi.org/10.1145/237814.237865">http://dx.doi.org/10.1145/237814.237865</a></li>
<li>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.  <a href="http://link.springer.com/10.1007/11841036_18">http://link.springer.com/10.1007/11841036_18</a></li>
</ul>

<ds.data-structures><binary-trees>
What are the must-read search trees paper?
rbtrht
# What are the must-read search trees paper?

(Asked by: username_0 on 2016-08-03)

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>

**Tags:** ds.data-structures, binary-trees


---

## 1 answers

### Answer by username_1 on 2016-08-05. Score: 7 | Accepted answer

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.


---

