Deletions That Preserve Randomness

DOI10.1109/TSE.1977.231160zbMath0355.68036OpenAlexW2066949144MaRDI QIDQ4127383

Donald E. Knuth

Publication date: 1977

Published in: IEEE Transactions on Software Engineering (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/tse.1977.231160

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Algorithms in computer science (68W99)

Related Items (14)

ISB-tree: A new indexing scheme with efficient expected behaviour ⋮ Dynamic planar range skyline queries in log logarithmic expected time ⋮ Improved bounds for finger search on a RAM ⋮ Dynamic 3-sided planar range queries with expected doubly-logarithmic time ⋮ Analysis of dynamic algorithms in Knuth's model ⋮ Dynamic algorithms in D. E. Knuth's model: A probabilistic analysis ⋮ Search performance of double-linked coalesced hashing can not exceed bucketing ⋮ Deletions in random binary search trees: a story of errors ⋮ A trivial algorithm whose analysis isn't ⋮ Randomness Preserving Deletions on Special Binary Search Trees ⋮ Sorting Algorithms in MOQA ⋮ Maintaining Ideally Distributed Random Search Trees without Extra Space ⋮ \(\mathcal{MOQA}\); unlocking the potential of compositional static average-case analysis ⋮ Non-overlapping partitions, continued fractions, Bessel functions and a divergent series

This page was built for publication: Deletions That Preserve Randomness