On the path length of binary trees

DOI10.1145/62044.62048zbMath0674.68012OpenAlexW2080767424MaRDI QIDQ3829055

Rolf Klein, Derick 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

comparisonupper boundsbinary searchpath lengthratio of meansnode visit costfringe thickness

Mathematics Subject Classification ID

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

Related Items (10)

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 ⋮ Binary trees, fringe thickness and minimum path length ⋮ Mean deep coalescence cost under exchangeable probability distributions ⋮ A tight upper bound for the path length of AVL trees ⋮ Minimal path length of trees with known fringe ⋮ Optimal binary search trees ⋮ Extremal values of the Sackin tree balance index ⋮ Fringe thickness and maximum path length of binary trees

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