2021/08/12 by Colm Ó Dúnlaing, Dúnlaing, Colm Ó
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #E.2 #FOS: Computer and information sciences #FOS: Mathematics #Mathematical Dynamics and Fractals #Optimization and Search Problems #Topological and Geometric Data Analysis #cs.DS #math.CO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2108.05666
21 pages, 17 figures
arxiv created 2021/08/12 · openalex publication_date 2021/08/12 · arxiv updated 2021/08/13 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
This paper takes another look at the cost of traversing a binary tree using repeated splay-to-root. This was shown to cost O(n) (in rotations) by Tarjan and later, in different ways, by Elmasry and others. It would be interesting to know the minimal possible coefficient implied by the O(n) cost; call this coefficient β. In this paper we define a related coefficient α describing the cost of splay-to-root traversal on maximal (i.e., complete) binary trees, and show that β≥ 2 + α. We give the first 3009 digits of α, including the decimal point, and show that every digit is correct. We make two conjectures: first, that β= 2 + α, and second, that α is irrational.