A unified access bound on comparison-based dynamic dictionaries

DOI10.1016/j.tcs.2007.03.002zbMath1127.68023OpenAlexW2154937603MaRDI QIDQ2381520

Erik D. Demaine, John Iacono, Mihai Bădoiu, Richard John Cole

Publication date: 18 September 2007

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.03.002

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items (13)

A Distribution-Sensitive Dictionary with Low Space Overhead ⋮ Rank-Sensitive Priority Queues ⋮ Skip-Splay: Toward Achieving the Unified Bound in the BST Model ⋮ On the hierarchy of distribution-sensitive properties for data structures ⋮ A priority queue with the time-finger property ⋮ A study on splay trees ⋮ A distribution-sensitive dictionary with low space overhead ⋮ Layered working-set trees ⋮ Biased predecessor search ⋮ Belga B-trees ⋮ Multi-Finger Binary Search Trees ⋮ A History of Distribution-Sensitive Data Structures ⋮ In Pursuit of the Dynamic Optimality Conjecture

Cites Work

• Unnamed Item
• Sequential access in splay trees takes linear time
• On the deque conjecture for the splay algorithm
• On the sequential access theorem and deque conjecture for splay trees
• Organization and maintenance of large ordered indexes
• Optimum binary search trees
• Self-adjusting binary search trees
• Design and Analysis of a Data Structure for Representing Sorted Lists
• 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
• Optimal Computer Search Trees and Variable-Length Alphabetical Codes
• LATIN 2004: Theoretical Informatics

This page was built for publication: A unified access bound on comparison-based dynamic dictionaries