Binary search trees of almost optimal height

DOI10.1007/BF01237235MaRDI QIDQ911247zbMATH OpenOpenAlexFDO

Authors N. E. Zubov

Publication date 1990

Published in Acta Informatica (Search for Journal in Brave)

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

zbMATH Keywords

complexityupper bounddictionary problembinary search trees

Mathematics Subject Classification ID

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

Recommendations

• Optimal binary search trees
• Optimal binary search trees
• Height Restricted Optimal Binary Trees
• Reflections on Optimal and Nearly Optimal Binary Search Trees
• A note on the height of binary search trees
• An analytic approach to the height of binary search trees
• Optimal alphabetic trees for binary search
• A Fast Algorithm For Optimum Height-Limited Alphabetic Binary Trees
• scientific article; zbMATH DE number 1741002
• An Approximation Algorithm for Binary Searching in Trees

Cites work

• scientific article; zbMATH DE number 4088895 (Why is no real title available?)
• scientific article; zbMATH DE number 3767009 (Why is no real title available?)
• scientific article; zbMATH DE number 3770965 (Why is no real title available?)
• Binary Search Trees of Bounded Balance
• Implementing dictionaries using binary trees of very small height
• On the relationship between son-trees and symmetric binary B-trees
• Optimizing binary trees grown with a sorting algorithm
• Organization and maintenance of large ordered indexes
• Priority Search Trees
• Stratified balanced search trees
• Symmetric binary B-trees: Data structure and maintenance algorithms
• The design of dynamic data structures
• UPDATING BINARY TREES WITH CONSTANT LINKAGE COST
• Updating a balanced search tree in 0(1) rotations

Cited in

(27)

• Revisiting 2-3 red-black trees with a pedagogically sound yet efficient deletion algorithm: parity-seeking
• Almost optimal dynamic 2-3 trees
• scientific article; zbMATH DE number 219270 (Why is no real title available?)
• Optimal binary search trees
• Optimal binary search trees
• Fully dynamic distributed search trees can be balanced in \(O(\lg^{2} N)\) time.
• A note on the height of binary search trees
• Improving time and space efficiency in generalized binary search trees
• Tight(er) worst-case bounds on dynamic searching and priority queues
• Binary search trees: How low can you go?
• Binary search tree recursions with harmonic toll functions
• The Analysis of an Improved Symmetric Binary B-tree Algorithm
• scientific article; zbMATH DE number 3852445 (Why is no real title available?)
• Supernode Binary Search Trees
• Balanced search trees made simple
• On \(k\)-dimensional balanced binary trees.
• scientific article; zbMATH DE number 1754613 (Why is no real title available?)
• Jump interpolation search trees and symmetric binary numbers
• scientific article; zbMATH DE number 437541 (Why is no real title available?)
• On the Height of Multidimensional Height-Balanced Trees
• A subquadratic algorithm for constructing approximately optimal binary search trees
• A new weight balanced binary search tree
• DYNAMIC TREE REBALANCING USING RECURRENT ROTATIONS: DYNAMIC TREE REBALANCING
• The optimal binary search tree for Andersson's search algorithm
• Optimal alphabetic trees for binary search
• scientific article; zbMATH DE number 1552324 (Why is no real title available?)
• Optimal binary trees with order constraints

This page was built for publication: Binary search trees of almost optimal height

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