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

DOI10.1142/S0129054196000117zbMath0852.68020OpenAlexW2006131099MaRDI QIDQ4886313

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)

Related Items (14)

A constant update time finger search tree ⋮ Multidimensional heaps and complementary range searching ⋮ Succinct data structure for dynamic trees with faster queries ⋮ Red-black trees with constant update time ⋮ Time-Optimal Top-$k$ Document Retrieval ⋮ Fully persistent B-trees ⋮ Skip lift: a probabilistic alternative to red-black trees ⋮ Skip Lift: A Probabilistic Alternative to Red-Black Trees ⋮ Optimal finger search trees in the pointer machine ⋮ Fully Functional Static and Dynamic Succinct Trees ⋮ Dynamic interpolation search revisited ⋮ Query-Optimal Partially Persistent B-Trees with Constant Worst-Case Update Time ⋮ Finger search in grammar-compressed strings ⋮ Unnamed Item

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