Competitive Online Search Trees on Trees
Open Access
- 24 June 2023
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 19 (3) , 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.Keywords
Funding Information
- European Union’s Horizon 2020 (734922)
- NSERC
- Fonds De La Recherche Scientifique-FNRS (J.0146.18, and MISU F 6001 1)
- NSF AITF (1533564)
- Fonds De La Recherche Scientifique-FNRS (40000886)
This publication has 34 references indexed in Scilit:
- Improved Approximation Algorithms for the Average-Case Tree Searching ProblemAlgorithmica, 2012
- On the complexity of searching in trees and partially ordered structuresTheoretical Computer Science, 2011
- Generalized Template Splay: A Basic Theory and CalculusThe Computer Journal, 2004
- On the vertex ranking problem for trapezoid, circular-arc and other graphsDiscrete Applied Mathematics, 1999
- An Explanation of SplayingJournal of Algorithms, 1996
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination TreeJournal of Algorithms, 1995
- Finding minimum height elimination trees for interval graphs in polynomial timeBIT Numerical Mathematics, 1994
- Optimal node ranking of trees in linear timeInformation Processing Letters, 1989
- The Associahedron and Triangulations of the n-gonEuropean Journal of Combinatorics, 1989
- A data structure for dynamic treesJournal of Computer and System Sciences, 1983