A SIMPLE BALANCED SEARCH TREE WITH O(1) WORST-CASE UPDATE TIME

DOI10.1142/S0129054196000117zbMATH Open0852.68020OpenAlexW2006131099MaRDI QIDQ4886313FDOQ4886313

Authors Rudolf Fleischer 

Publication date 11 December 1996

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054196000117

zbMATH Keywords

bucketingbalanced search treeoptimal query timepreventive splitting

Mathematics Subject Classification ID

Searching and sorting (68P10) Grammars and rewriting systems (68Q42)

Recommendations

• A balanced search tree O(1) worst-case update time
• scientific article; zbMATH DE number 2105039
• Fast updating of well-balanced trees
• Red-black trees with constant update time
• Binary search trees of almost optimal height

Cited in

(19)

• scientific article; zbMATH DE number 88943 (Why is no real title available?)
• Partially persistent B-trees with constant worst case update time
• Finger search in grammar-compressed strings
• A constant update time finger search tree
• Fully persistent B-trees
• Poketree: A Dynamically Competitive Data Structure with Good Worst-Case Performance
• A balanced search tree O(1) worst-case update time
• Fully persistent B-trees
• Red-black trees with constant update time
• Fully functional static and dynamic succinct trees
• scientific article; zbMATH DE number 2105039 (Why is no real title available?)
• Multidimensional heaps and complementary range searching
• Query-optimal partially persistent B-trees with constant worst-case update time
• Succinct data structure for dynamic trees with faster queries
• Skip lift: a probabilistic alternative to red-black trees
• Time-optimal top-\(k\) document retrieval
• Optimal finger search trees in the pointer machine
• Skip lift: a probabilistic alternative to red-black trees
• Dynamic interpolation search revisited

This page was built for publication: A SIMPLE BALANCED SEARCH TREE WITH O(1) WORST-CASE UPDATE TIME

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