Greedy is an almost optimal deque

DOI10.1007/978-3-319-21840-3_13MaRDI QIDQ3449813zbMATH OpenOpenAlexFDO

Authors Parinya Chalermsook, Mayank Goswami, László Kozma, K. Mehlhorn, Thatchaphol Saranurak

Publication date 30 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: In this paper we extend the geometric binary search tree (BST) model of Demaine, Harmon, Iacono, Kane, and Patrascu (DHIKP) to accommodate for insertions and deletions. Within this extended model, we study the online Greedy BST algorithm introduced by DHIKP. Greedy BST is known to be equivalent to a maximally greedy (but inherently offline) algorithm introduced independently by Lucas in 1988 and Munro in 2000, conjectured to be dynamically optimal. With the application of forbidden-submatrix theory, we prove a quasilinear upper bound on the performance of Greedy BST on deque sequences. It has been conjectured (Tarjan, 1985) that splay trees (Sleator and Tarjan, 1983) can serve such sequences in linear time. Currently neither splay trees, nor other general-purpose BST algorithms are known to fulfill this requirement. As a special case, we show that Greedy BST can serve output-restricted deque sequences in linear time. A similar result is known for splay trees (Tarjan, 1985; Elmasry, 2004). As a further application of the insert-delete model, we give a simple proof that, given a set U of permutations of [n], the access cost of any BST algorithm is Omega(log |U| + n) on "most" of the permutations from U. In particular, this implies that the access cost for a random permutation of [n] is Omega(n log n) with high probability. Besides the splay tree noted before, Greedy BST has recently emerged as a plausible candidate for dynamic optimality. Compared to splay trees, much less effort has gone into analyzing Greedy BST. Our work is intended as a step towards a full understanding of Greedy BST, and we remark that forbidden-submatrix arguments seem particularly well suited for carrying out this program.

Recommendations

• Better analysis of binary search tree on decomposable sequences
• The geometry of binary search trees
• Upper bounds for maximally greedy binary search trees
• Sequential access in splay trees takes linear time
• De-amortizing binary search trees

Cites work

• A study of least squares and maximum likelihood for image reconstruction in positron emission tomography
• Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts
• 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 deque conjecture for the splay algorithm
• 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
• On the sequential access theorem and deque conjecture for splay trees
• Sequential access in splay trees takes linear time
• The geometry of binary search trees
• Upper bounds for maximally greedy binary search trees

Cited in

(8)

• Better analysis of binary search tree on decomposable sequences
• The geometry of binary search trees
• Smooth heaps and a dual view of self-adjusting data structures
• Upper bounds for maximally greedy binary search trees
• scientific article; zbMATH DE number 7758335 (Why is no real title available?)
• The group access bounds for binary search trees
• Efficiency of self-adjusting heaps
• Hardness amplification for dynamic binary search trees

This page was built for publication: Greedy is an almost optimal deque

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