Improved bounds for the expected behaviour of AVL trees

DOI10.1007/BF01994883MaRDI QIDQ1196459zbMATH OpenOpenAlexFDO

Authors Ricardo Baeza-Yates, Gaston H. Gonnet, Nivio Ziviani

Publication date 14 December 1992

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01994883

zbMATH Keywords

AVL treesfringe analysis

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Recommendations

• Expected behaviour analysis of AVL trees
• An Amortized Analysis of Insertions into AVL-Trees
• scientific article; zbMATH DE number 2050880
• Height balance distribution of search trees
• The theory of fringe analysis and its application to 23 trees and b-trees

Cites work

• 1-2 Brother Trees or AVL Trees Revisited
• A Look at Symmetric Binary B-Trees
• A Partial Analysis of Height-Balanced Trees under Random Insertions and Deletions
• A Partial Analysis of Random Height-Balanced Trees
• An Amortized Analysis of Insertions into AVL-Trees
• scientific article; zbMATH DE number 88944 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3518272 (Why is no real title available?)
• scientific article; zbMATH DE number 3303655 (Why is no real title available?)
• On random 2-3 trees
• The theory of fringe analysis and its application to 23 trees and b-trees

Cited in

(7)

• On rotations in fringe-balanced binary trees
• An Amortized Analysis of Insertions into AVL-Trees
• scientific article; zbMATH DE number 2050880 (Why is no real title available?)
• scientific article; zbMATH DE number 2050881 (Why is no real title available?)
• Expected behaviour analysis of AVL trees
• Analytical estimates and proof of the scale-free character of efficiency and improvement in Barabási-Albert trees
• Average number of rotations access cost in iR-trees

This page was built for publication: Improved bounds for the expected behaviour of AVL trees

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