Deletions that Preserve Randomness.

Abstract

This paper discusses dynamic properties of data structures under insertions and deletions. It is shown that, in certain circumstances, the result of n random insertions and m random deletions will be equivalent to n-m random insertions, under various interpretations of the work random and under various constraints on the order of insertions and deletions. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1976
Accession Number
ADA038865

Entities

People

  • Donald Knuth

Organizations

  • Stanford University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Bessel Functions
  • Computer Programming
  • Computer Science
  • Computers
  • Military Research
  • Notation
  • Numbers
  • Permutations
  • Probability
  • Probability Distributions
  • Real Numbers
  • Sequences
  • Trees (Data Structures)
  • United States
  • United States Government

Readers

  • Microwave Engineering.
  • Regression Analysis.