A balanced search tree O(1) worst-case update time

DOI10.1007/BF00299635MaRDI QIDQ1114387zbMATH OpenOpenAlexFDO

Authors Christos Levcopoulos, Mark H. Overmars

Publication date 1988

Published in Acta Informatica (Search for Journal in Brave)

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

zbMATH Keywords

balanced search treedata structuremember and neighbor queries

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Information storage and retrieval of data (68P20)

Review text

A new data structure is described for performing member and neighbor queries in O(log n) time that allows for O(1) worst-case update time once the position of the inserted or deleted element is known. In this way previous solutions that achieved only O(1) amortized time or \(O(\log^* n)\) worst-case time are improved. The method is based on a combinatorial result on the height of piles that are split after some fixed number of insertions. This combinatorial result is interesting in its own right and might have other applications as well.

Recommendations

• A SIMPLE BALANCED SEARCH TREE WITH O(1) WORST-CASE UPDATE TIME
• scientific article; zbMATH DE number 2105039
• scientific article; zbMATH DE number 3856424
• A TOP-DOWN UPDATING ALGORITHM FOR WEIGHT-BALANCED TREES
• Fast updating of well-balanced trees
• An \(O(\log \log n)\)-competitive binary search tree with optimal worst-case access times
• scientific article; zbMATH DE number 1754613
• A new weight balanced binary search tree
• scientific article; zbMATH DE number 5046289

Cites work

• A new data structure for representing sorted lists
• The design of dynamic data structures
• Worst-case optimal insertion and deletion methods for decomposable searching problems

Cited in

(21)

• A constant update time finger search tree
• A simple greedy algorithm for dynamic graph orientation
• Fully persistent B-trees
• Dynamic interpolation search revisited
• Red-black trees with constant update time
• Dynamic 3-sided planar range queries with expected doubly-logarithmic time
• Skip lift: a probabilistic alternative to red-black trees
• Dynamic Trees and Dynamic Point Location
• Skip lift: a probabilistic alternative to red-black trees
• Dynamic interpolation search in o( n) time
• A SIMPLE BALANCED SEARCH TREE WITH O(1) WORST-CASE UPDATE TIME
• Fully dynamic almost-maximal matching: breaking the polynomial worst-case time barrier
• Improved dynamic graph coloring
• The randomized complexity of maintaining the minimum
• Binary search trees: How low can you go?
• Persistence, randomization and parallelization: On some combinatorial games and their applications (abstract)
• A simple greedy algorithm for dynamic graph orientation
• Poketree: A Dynamically Competitive Data Structure with Good Worst-Case Performance
• Optimal finger search trees in the pointer machine
• ISB-tree: A new indexing scheme with efficient expected behaviour
• Multidimensional heaps and complementary range searching

This page was built for publication: A balanced search tree 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 Q1114387)