A tight upper bound for the path length of AVL trees

DOI10.1016/0304-3975(90)90037-IzbMath0698.68019MaRDI QIDQ912600

Rolf Klein, Derick Wood

Publication date: 1990

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

binary treeAVL treesbrother treespath lengthAdel'son-Vel'skij-Landis treecomparison costnode visit cost

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Related Items (5)

Insertion reachability, skinny skeletons, and path length in red-black trees ⋮ Balance in AVL trees and space cost of brother trees ⋮ A note on the expected path length of trees with known fringe ⋮ Minimal path length of trees with known fringe ⋮ A note on the path length of red-black trees

Cites Work

• Unnamed Item
• Unnamed Item
• The node visit cost of brother trees
• On the correspondence between AVL trees and brother trees
• Minimal-Cost Brother Trees
• Balancing binary trees by internal path reduction
• On the path length of binary trees
• 1-2 Brother Trees or AVL Trees Revisited

This page was built for publication: A tight upper bound for the path length of AVL trees