Recursively rotated orders and implicit data structures: A lower bound

DOI10.1016/0304-3975(84)90013-6zbMATH Open0537.68060OpenAlexW2043343347MaRDI QIDQ792764FDOQ792764

Authors: Greg N. Frederickson 

Publication date: 1984

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(84)90013-6

Recommendations

• scientific article; zbMATH DE number 2079398
• Implicit \(B\)-trees: A new data structure for the dictionary problem
• An implicit data structure supporting insertion, deletion, and search in \(O(\log ^ 2\,n)\) time
• Optimal implicit dictionaries over unbounded universes
• Optimal worst-case operations for implicit cache-oblivious search trees.

zbMATH Keywords

lower boundpartial orderdictionaryimplicit data structurerecursively rotated order

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Searching and sorting (68P10)

Cites Work

• Implicit data structures for fast search and update
• Implicit Data Structures for the Dictionary Problem
• Recurrence relations based on minimization

Cited In (3)

• An implicit data structure supporting insertion, deletion, and search in \(O(\log ^ 2\,n)\) time
• A pointer-free data structure for merging heaps and min-max heaps
• Title not available (Why is that?)

This page was built for publication: Recursively rotated orders and implicit data structures: A lower bound

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q792764)