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

DOI10.1142/S0129054196000117MaRDI QIDQ4886313zbMATH OpenOpenAlexFDO

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

balanced search treebucketingoptimal 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

(21)

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

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)