Balancing binary trees by internal path reduction

DOI10.1145/358476.358509MaRDI QIDQ3714475zbMATH OpenOpenAlexWikidataFDO

Authors Gaston H. Gonnet

Publication date 1983

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

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

zbMATH Keywords

algorithm for balancing binary search treesnumber of rotations

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 3852445
• A new weight balanced binary search tree
• Binary search trees: How low can you go?
• Height balance distribution of search trees
• scientific article; zbMATH DE number 1754613

Cited in

(24)

• Height balance distribution of search trees
• A note on the path length of red-black trees
• Path balance heuristic for self-adjusting binary search trees
• The modification of the Sedgewick's balancing algorithm
• Balancing weight-balanced trees
• scientific article; zbMATH DE number 437541 (Why is no real title available?)
• Rank-Balanced Trees
• scientific article; zbMATH DE number 3845369 (Why is no real title available?)
• scientific article; zbMATH DE number 3852445 (Why is no real title available?)
• A Maximally Parallel Balancing Algorithm for Obtaining Complete Balanced Binary Trees
• The Analysis of an Improved Symmetric Binary B-tree Algorithm
• scientific article; zbMATH DE number 140484 (Why is no real title available?)
• Three algorithms on Braun trees
• scientific article; zbMATH DE number 2044508 (Why is no real title available?)
• scientific article; zbMATH DE number 1754613 (Why is no real title available?)
• scientific article; zbMATH DE number 219270 (Why is no real title available?)
• DYNAMIC TREE REBALANCING USING RECURRENT ROTATIONS: DYNAMIC TREE REBALANCING
• How to update a balanced binary tree with a constant number of rotations
• A new weight balanced binary search tree
• The relationship between balance and the speed of algorithms
• UPDATE-EFFICIENT DATA STRUCTURES FOR DYNAMIC IP ROUTER TABLES
• UPDATE-EFFICIENT DATA STRUCTURES FOR DYNAMIC IP ROUTER TABLES
• Average number of rotations access cost in iR-trees
• A tight upper bound for the path length of AVL trees

This page was built for publication: Balancing binary trees by internal path reduction

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