Competitive Online Search Trees on Trees
Authors: 
Prosenjit Bose, Jean Cardinal, John Iacono, Grigorios Koumoutsos, 
Stefan LangermanAuthors Info & Claims
Article No.: 25, Pages 1 - 19
Abstract
We consider the design of adaptive data structures for searching elements of a tree-structured space. We use a natural generalization of the rotation-based online binary search tree model in which the underlying search space is the set of vertices of a tree. This model is based on a simple structure for decomposing graphs, previously known under several names including elimination trees, vertex rankings, and tubings. The model is equivalent to the classical binary search tree model exactly when the underlying tree is a path. We describe an online O(log log n)-competitive search tree data structure in this model, where n is the number of vertices. This matches the best-known competitive ratio of binary search trees. Our method is inspired by Tango trees, an online binary search tree algorithm, but critically needs several new notions including one that we call Steiner-closed search trees, which may be of independent interest. Moreover, our technique is based on a novel use of two levels of decomposition, first from search space to a set of Steiner-closed trees and, second, from these trees into paths.
References
[1]
G. M. Adel’son-Vel’skii and E. M. Landis. 1962. An algorithm for the organization of information. Soviet Mathematics - Doklady 3, (1962), 1259–1263.
[2]
Bengt Aspvall and Pinar Heggernes. 1994. Finding minimum height elimination trees for interval graphs in polynomial time. BIT Numer. Math. 34, 4 (01 December1994), 484–509.
[3]
Yosi Ben-Asher, Eitan Farchi, and Ilan Newman. 1999. Optimal search in trees. SIAM J. Comput. 28, 6 (1999), 2090–2102.
[4]
Hans L. Bodlaender, Jitender S. Deogun, Klaus Jansen, Ton Kloks, Dieter Kratsch, Haiko Müller, and Zsolt Tuza. 1998. Rankings of graphs. SIAM J. Discr. Math. 11, 1 (1998), 168–181.
[5]
Hans L. Bodlaender, John R. Gilbert, Hjálmtyr Hafsteinsson, and Ton Kloks. 1995. Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. J. Algor. 18, 2 (1995), 238–255.
[6]
Prosenjit Bose, Karim Douïeb, John Iacono, and Stefan Langerman. 2016. The power and limitations of static binary search trees with lazy finger. Algorithmica 76, 4 (2016), 1264–1275.
[7]
Jean Cardinal, Stefan Langerman, and Pablo Pérez-Lantero. 2018. On the diameter of tree associahedra. Electr. J. Comb. 25, 4 (2018), P4.18.
[8]
Michael Carr and Satyan L. Devadoss. 2006. Coxeter complexes and graph-associahedra. Topol. Appl. 153, 12 (2006), 2155–2168.
[9]
Cesar Ceballos, Francisco Santos, and Günter M. Ziegler. 2015. Many non-equivalent realizations of the associahedron. Combinatorica 35, 5 (01 October2015), 513–551.
[10]
Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. 2015. Pattern-avoiding access in binary search trees. In Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS’15). 410–423.
[11]
Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. 2015. Self-adjusting binary search trees: What makes them tick?. In Proceedings of the 23rd Annual European Symposium on Algorithms (ESA’15). 300–312.
[12]
Ferdinando Cicalese, Tobias Jacobs, Eduardo Sany Laber, and Marco Molinaro. 2011. On the complexity of searching in trees and partially ordered structures. Theor. Comput. Sci. 412, 50 (2011), 6879–6896.
[13]
Ferdinando Cicalese, Tobias Jacobs, Eduardo Sany Laber, and Marco Molinaro. 2014. Improved approximation algorithms for the average-case tree searching problem. Algorithmica 68, 4 (2014), 1045–1074.
[14]
Ferdinando Cicalese, Balázs Keszegh, Bernard Lidický, Dömötör Pálvölgyi, and Tomás Valla. 2016. On the tree search problem with non-uniform costs. Theor. Comput. Sci. 647 (2016), 22–32.
[15]
Richard Cole. 2000. On the dynamic finger conjecture for splay trees. Part II: The proof. SIAM J. Comput. 30, 1 (2000), 44–85.
[16]
Richard Cole, Bud Mishra, Jeanette P. Schmidt, and Alan Siegel. 2000. On the dynamic finger conjecture for splay trees. Part I: Splay sorting log n-block sequences. SIAM J. Comput. 30, 1 (2000), 1–43.
[17]
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, 3rd Edition. MIT Press.
[18]
Erik D. Demaine, Dion Harmon, John Iacono, Daniel M. Kane, and Mihai Pǎtraşcu. 2009. The geometry of binary search trees. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’09). 496–505.
[19]
Erik D. Demaine, Dion Harmon, John Iacono, and Mihai Pǎtraşcu. 2007. Dynamic optimality—Almost. SIAM J. Comput. 37, 1 (2007), 240–251.
[20]
Jitender S. Deogun, Ton Kloks, Dieter Kratsch, and Haiko Müller. 1999. On the vertex ranking problem for trapezoid, circular-arc and other graphs. Discr. Appl. Math. 98, 1 (1999), 39–63.
[21]
Ehsan Emamjomeh-Zadeh, David Kempe, and Vikrant Singhal. 2016. Deterministic and probabilistic binary search in graphs. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC’16). 519–532.
[22]
Michael L. Fredman. 1975. Two applications of a probabilistic search technique: Sorting x + y and building balanced search trees. In Proceedings of the 7th Annual ACM Symposium on Theory of Computing. 240–244.
[23]
George F. Georgakopoulos. 2008. Chain-splay trees, or, how to achieve and prove loglogN-competitiveness by splaying. Inf. Process. Lett. 106, 1 (2008), 37–43.
[24]
George F. Georgakopoulos and David J. McClurkin. 2004. Generalized template splay: A basic theory and calculus. Comput. J. 47, 1 (2004), 10–19.
[25]
Leonidas J. Guibas and Robert Sedgewick. 1978. A dichromatic framework for balanced trees. In Proceedings of the 19th Annual Symposium on Foundations of Computer Science. 8–21.
[26]
Frank Harary. 1969. Graph Theory. Addison-Wesley.
[27]
Brent Heeringa, Marius Catalin Iordan, and Louis Theran. 2011. Searching in dynamic tree-like partial orders. In Proceedings of the 12th International Symposium on Algorithms and Data Structures (WADS’11). 512–523.
[28]
John Iacono. 2013. In pursuit of the dynamic optimality conjecture. In Space-Efficient Data Structures, Streams, and Algorithms—Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday. 236–250.
[29]
John Iacono and Stefan Langerman. 2016. Weighted dynamic finger in binary search trees. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’16). 672–691.
[30]
Camille Jordan. 1869. Sur les assemblages de lignes. J. reine angew. Math. 70 (1869), 185–190.
[31]
Donald E. Knuth. 1971. Optimum binary search trees. Acta Inf. 1 (1971), 14–25.
[32]
Carl W. Lee. 1989. The associahedron and triangulations of the n-gon. Eur. J. Combin. 10, 6 (1989), 551–560.
[33]
Joan M. Lucas. 1988. Canonical Forms for Competitive Binary Search Tree Algorithms. DGS-TR-250, Department of Computer Science, Hill Center for the Mathematical Sciences Busch Campus, Rutgers University.
[34]
Thibault Manneville and Vincent Pilaud. 2015. Graph properties of graph associahedra. Sémin. Lothar. Combin. B73d (2015).
[35]
Kurt Mehlhorn. 1975. Nearly optimal binary search trees. Acta Inf. 5 (1975), 287–295.
[36]
Kurt Mehlhorn. 1977. A best possible bound for the weighted path length of binary search trees. SIAM J. Comput. 6, 2 (1977), 235–239.
[37]
Shay Mozes, Krzysztof Onak, and Oren Weimann. 2008. Finding an optimal tree searching strategy in linear time. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’08). 1096–1105.
[38]
J. Ian Munro. 2000. On the competitiveness of linear search. In Proceeding of the 8th European Symposium on Algorithms (ESA’00), Lecture Notes in Computer Science, Vol. 1879. Springer, 338–345.
[39]
Jaroslav Nešetřil and Patrice Ossona de Mendez. 2012. Sparsity: Graphs, Structures, and Algorithms. Springer, Chapter 6, 115–144.
[40]
Krzysztof Onak and Pawel Parys. 2006. Generalization of binary search: Searching in trees and forest-like partial orders. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06). 379–388.
[41]
Alexander Postnikov. 2009. Permutohedra, associahedra, and beyond. Int. Math. Res. Not. 2009, 6 (2009), 1026–1106.
[42]
Alex Postnikov, Victor Reiner, and Lauren Williams. 2008. Faces of generalized permutohedra. Doc. Math. 13 (2008), 207–273.
[43]
Alex Pothen. 1988. The Complexity of Optimal Elimination Trees. Technical Report CS-88-13, Pennsylvania State University.
[44]
Lionel Pournin. 2014. The diameter of associahedra. Adv. Math. 259 (2014), 13–42.
[45]
Alejandro A. Schäffer. 1989. Optimal node ranking of trees in linear time. Inform. Process. Lett. 33, 2 (1989), 91–96.
[46]
Claude Elwood Shannon. 1948. A mathematical theory of communication. Bell Syst. Techn. J. 27, 3 (71948), 379–423.
[47]
Daniel Dominic Sleator and Robert Endre Tarjan. 1983. A data structure for dynamic trees. J. Comput. Syst. Sci. 26, 3 (1983), 362–391.
[48]
Daniel Dominic Sleator and Robert Endre Tarjan. 1985. Self-adjusting binary search trees. J. ACM 32, 3 (1985), 652–686.
[49]
Daniel Dominic Sleator, Robert Endre Tarjan, and William P. Thurston. 1986. Rotation distance, triangulations, and hyperbolic geometry. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing. 122–135.
[50]
James Dillon Stasheff. 1963. Homotopy associativity of H-spaces. I. Trans. Am. Math. Soc. 108, 2 (1963), 275–292.
[51]
Ashok Subramanian. 1996. An explanation of splaying. J. Algor. 20, 3 (1996), 512–525.
[52]
Dov Tamari. 1951. Monoïdes préordonnés et chaînes de Malcev. Thèse de Mathématiques, Paris.
[53]
Robert Endre Tarjan. 1983. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA.
[54]
Chengwen Chris Wang, Jonathan Derryberry, and Daniel Dominic Sleator. 2006. O(log log n)-competitive dynamic binary search trees. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’06). 374–383.
[55]
Robert E. Wilber. 1989. Lower bounds for accessing binary search trees with rotations. SIAM J. Comput. 18, 1 (1989), 56–67.
Index Terms
- Competitive Online Search Trees on Trees
Recommendations
Competitive online search trees on trees
SODA '20: Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete AlgorithmsWe consider the design of adaptive data structures for searching elements of a tree-structured space. We use a natural generalization of the rotation-based online binary search tree model in which the underlying search space is the set of vertices of a ...
Self-adjusting binary search trees
The splay tree, a self-adjusting form of binary search tree, is developed and analyzed. The binary search tree is a data structure for representing tables and lists so that accessing, inserting, and deleting items is easy. On an n-node splay tree, all ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2023
281 pages
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 24 June 2023
Online AM: 28 April 2023
Accepted: 23 April 2023
Revised: 09 April 2023
Received: 19 December 2020
Published in TALG Volume 19, Issue 3
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- European Union’s Horizon 2020
- NSERC
- Fonds de la Recherche Scientifique-FNRS
- NSF AitF
- Fonds de la Recherche Scientifique-FNRS
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 245Total Downloads
- Downloads (Last 12 months)176
- Downloads (Last 6 weeks)7
Reflects downloads up to 24 Sep 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderFull Text
View this article in Full Text.
Full TextHTML Format
View this article in HTML Format.
HTML Format