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

DOI10.1007/BF00299635zbMath0662.68016OpenAlexW2134458085MaRDI QIDQ1114387

Mark H. Overmars, Christos Levcopoulos

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

data structurebalanced search treemember and neighbor queries

Mathematics Subject Classification ID

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

Related Items

A constant update time finger search tree ⋮ The randomized complexity of maintaining the minimum ⋮ Binary search trees: How low can you go? ⋮ Multidimensional heaps and complementary range searching ⋮ Persistence, randomization and parallelization: On some combinatorial games and their applications (abstract) ⋮ ISB-tree: A new indexing scheme with efficient expected behaviour ⋮ Red-black trees with constant update time ⋮ Unnamed Item ⋮ Fully persistent B-trees ⋮ Dynamic 3-sided planar range queries with expected doubly-logarithmic time ⋮ Skip lift: a probabilistic alternative to red-black trees ⋮ Dynamic interpolation search in o(log log n) time ⋮ Skip Lift: A Probabilistic Alternative to Red-Black Trees ⋮ A simple greedy algorithm for dynamic graph orientation ⋮ Optimal finger search trees in the pointer machine ⋮ Dynamic interpolation search revisited ⋮ Unnamed Item ⋮ Dynamic Trees and Dynamic Point Location ⋮ Improved Dynamic Graph Coloring

Cites Work

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