Deletions That Preserve Randomness
Donald E. Knuth · IEEE Transactions on Software Engineering · 1977
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 world "random" and under various constraints on the order of insertions and deletions.