Deletions that Preserve Randomness.

摘要

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)