Dynamic Trees with Almost-Optimal Access Cost

DOI10.4230/LIPIcs.ESA.2018.38OpenAlexW2917889020MaRDI QIDQ5009598

John Iacono, J. Ian Munro, Yakov Nekrich, Stefan Langerman, Mordecai J. Golin

Publication date: 4 August 2021

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

zbMATH Keywords

data structuresbinary search treesadaptive alphabetic coding

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items

Efficient and compact representations of some non-canonical prefix-free codes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the costs of optimal and near-optimal binary search trees
• A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time
• Implementing dictionaries using binary trees of very small height
• Randomized search trees
• Symmetric binary B-trees: Data structure and maintenance algorithms
• Optimum binary search trees
• Dynamic huffman coding
• Self-adjusting binary search trees
• Design and analysis of dynamic Huffman codes
• A Best Possible Bound for The Weighted Path Length of Binary Search Trees
• A New Algorithm for Minimum Cost Binary Trees
• File Maintenance: When in Doubt, Change the Layout!
• Upper and Lower Bounds on Constructing Alphabetic Binary Trees
• Binary search trees: How low can you go?
• Algorithms – ESA 2004
• Algorithms – ESA 2005
• Optimal Computer Search Trees and Variable-Length Alphabetical Codes