A tight upper bound for the path length of AVL trees

DOI10.1016/0304-3975(90)90037-IMaRDI QIDQ912600zbMATH OpenFDO

Authors Rolf Klein, D. Wood

Publication date 1990

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

Full work available at URL https://doi.org/10.1016/0304-3975(90)90037-I

zbMATH Keywords

Adel'son-Vel'skij-Landis treeAVL treesbinary treebrother treescomparison costnode visit costpath length

Mathematics Subject Classification ID

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

Review text

See the review in Zbl 0645.68076.

Cites work

• 1-2 Brother Trees or AVL Trees Revisited
• Balancing binary trees by internal path reduction
• scientific article; zbMATH DE number 3518272 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Minimal-Cost Brother Trees
• On the correspondence between AVL trees and brother trees
• On the path length of binary trees
• The node visit cost of brother trees

Cited in

(7)

• A note on the path length of red-black trees
• 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
• Tight Upper and Lower Bounds on the Path Length of Binary Trees
• Minimal path length of trees with known fringe
• Grandchildren-weight-balanced binary search trees

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

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