Better analysis of binary search tree on decomposable sequences

DOI10.1016/J.TCS.2018.12.021MaRDI QIDQ2419118zbMATH OpenOpenAlexWikidataFDO

Authors Navin Goyal, Manoj Gupta

Publication date 29 May 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.06997

zbMATH Keywords

binary search treedata structuresdynamic optimality conjecture

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: In their seminal paper [Sleator and Tarjan, J.ACM, 1985], the authors conjectured that the splay tree is dynamically optimal binary search tree (BST). In spite of decades of intensive research, the problem remains open. Perhaps a more basic question, which has also attracted much attention, is if there exists any dynamically optimal BST algorithm. One such candidate is GREEDY which is a simple and intuitive BST algorithm [Lucas, Rutgers Tech. Report, 1988; Munro, ESA, 2000; Demaine, Harmon, Iacono, Kane and Patrascu, SODA, 2009]. [Demaine et al., SODA, 2009] showed a novel connection between a geometric problem. Since dynamic optimality conjecture in its most general form remains elusive despite much effort, researchers have studied this problem on special sequences. Recently, [Chalermsook, Goswami, Kozma, Mehlhorn and Saranurak, FOCS, 2015] studied a type of sequences known as $k$-{em decomposable sequences} in this context, where $k$ parametrizes easiness of the sequence. Using tools from forbidden submatrix theory, they showed that GREEDY takes $n{2}^{O(k^2)}$ time on this sequence and explicitly raised the question of improving this bound. In this paper, we show that GREEDY takes $O(nlogk)$ time on $k$-decomposable sequences. In contrast to the previous approach, ours is based on first principles. One of the main ingredients of our result is a new construction of a lower bound certificate on the performance of any algorithm. This certificate is constructed using the execution of GREEDY, and is more nuanced and possibly more flexible than the previous independent set certificate of Demaine et al. This result, which is applicable to all sequences, may be of independent interest and may lead to further progress in analyzing GREEDY on $k$-decomposable as well as general sequences.

Recommendations

• Greedy is an almost optimal deque
• The geometry of binary search trees
• Upper bounds for maximally greedy binary search trees
• Dynamic Optimality—Almost
• In pursuit of the dynamic optimality conjecture

Cites work

• O(log log n)-competitive dynamic binary search trees
• An \(O(\log \log n)\)-competitive binary search tree with optimal worst-case access times
• Dynamic Optimality—Almost
• scientific article; zbMATH DE number 1670671 (Why is no real title available?)
• scientific article; zbMATH DE number 5764839 (Why is no real title available?)
• scientific article; zbMATH DE number 6297801 (Why is no real title available?)
• In pursuit of the dynamic optimality conjecture
• Lower Bounds for Accessing Binary Search Trees with Rotations
• On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences
• On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
• Self-adjusting binary search trees
• Self-adjusting binary search trees: what makes them tick?
• The geometry of binary search trees
• Upper bounds for maximally greedy binary search trees
• Weighted dynamic finger in binary search trees

Cited in

(4)

• Greedy is an almost optimal deque
• Upper bounds for maximally greedy binary search trees
• The group access bounds for binary search trees
• Hardness amplification for dynamic binary search trees

This page was built for publication: Better analysis of binary search tree on decomposable sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2419118)