Optimum lopsided binary trees

DOI10.1145/65950.65955zbMath0825.68344OpenAlexW1982998010MaRDI QIDQ4710685

Sanjiv Kapoor, Edward M. Reingold

Publication date: 25 June 1992

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/65950.65955

zbMATH Keywords

Fibonacci numbersinformation theoryunbounded searchcoding theorybinary search treesdata structureprefix-free codesalgorithmic analysisKraft's inequalityFibonacci treesoptimal treespath lengthsedge-weighted treesminimax recurrence relations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)

Related Items (8)

Solutions of two minmax recurrences in parallel processing with variable recombination overhead ⋮ Operations research applications of dichotomous search ⋮ An asymptotic theory for recurrence relations based on minimization and maximization. ⋮ F-Chord: Improved uniform routing on Chord ⋮ A dynamic programming algorithm for constructing optimal prefix-free codes for unequal letter costs ⋮ On the cost of optimal alphabetic code trees with unequal letter costs ⋮ Binary trees with choosable edge lengths ⋮ Optimal point-to-point broadcast algorithms via lopsided trees

This page was built for publication: Optimum lopsided binary trees