On the path length of binary trees

DOI10.1145/62044.62048MaRDI QIDQ3829055zbMATH OpenOpenAlexFDO

Authors Rolf Klein, D. Wood

Publication date 1989

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

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

zbMATH Keywords

binary searchcomparisonfringe thicknessnode visit costpath lengthratio of meansupper bounds

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 176528
• Tight Upper and Lower Bounds on the Path Length of Binary Trees
• Maximal path length of binary trees
• scientific article; zbMATH DE number 4041950
• An almost sure result for path lengths in binary search trees
• Left and right length of paths in binary trees
• scientific article; zbMATH DE number 894188
• Left and right length of paths in binary trees or on a question of Knuth
• On the number of t-ary trees with a given path length

Cited in

(28)

• Binary trees and uniform distribution of traffic cutback
• A note on the path length of red-black trees
• Fringe thickness and maximum path length of binary trees
• Maximal path length of binary trees
• Balance in AVL trees and space cost of brother trees
• A note on the expected path length of trees with known fringe
• Extremal values of the Sackin tree balance index
• An O(n n) time algorithm for computing the path-length distance between trees
• Structure of the path length set in asymmetric trees
• scientific article; zbMATH DE number 3858431 (Why is no real title available?)
• scientific article; zbMATH DE number 4168708 (Why is no real title available?)
• On the structure of paths-like trees
• On the average length of lexicographic paths
• scientific article; zbMATH DE number 4041950 (Why is no real title available?)
• scientific article; zbMATH DE number 4053041 (Why is no real title available?)
• Mean deep coalescence cost under exchangeable probability distributions
• scientific article; zbMATH DE number 176528 (Why is no real title available?)
• Tight Upper and Lower Bounds on the Path Length of Binary Trees
• scientific article; zbMATH DE number 1043915 (Why is no real title available?)
• Binary trees, fringe thickness and minimum path length
• ON WEIGHTED PATH LENGTHS AND DISTANCES IN INCREASING TREES
• Optimal binary search trees
• Minimal path length of trees with known fringe
• Characteristic inequalities for binary trees
• On the number of t-ary trees with a given path length
• A tight upper bound for the path length of AVL trees
• Path length and height in asymmetric binary branching trees
• On Postnikov's hook length formula for binary trees

This page was built for publication: On the path length of binary trees

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