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

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

zbMATH Keywords

bucketingbalanced search treeoptimal query timepreventive splitting

Mathematics Subject Classification ID

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

Cited In (19)

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

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)