Optimum lopsided binary trees
From MaRDI portal
Publication:4710685
DOI10.1145/65950.65955zbMath0825.68344MaRDI 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
Fibonacci numbers; information theory; unbounded search; coding theory; binary search trees; data structure; prefix-free codes; algorithmic analysis; Kraft's inequality; Fibonacci trees; optimal trees; path lengths; edge-weighted trees; minimax recurrence relations
68Q25: Analysis of algorithms and problem complexity
68P10: Searching and sorting
68R10: Graph theory (including graph drawing) in computer science
Related Items
A dynamic programming algorithm for constructing optimal prefix-free codes for unequal letter costs, Binary trees with choosable edge lengths, Optimal point-to-point broadcast algorithms via lopsided trees, An asymptotic theory for recurrence relations based on minimization and maximization., Operations research applications of dichotomous search, Solutions of two minmax recurrences in parallel processing with variable recombination overhead, On the cost of optimal alphabetic code trees with unequal letter costs, F-Chord: Improved uniform routing on Chord