Title :
Deletions That Preserve Randomness
Author :
Knuth, Donald E.
Author_Institution :
Department of Computer Science, Stanford University
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 world "random" and under various constraints on the order of insertions and deletions.
Keywords :
Analysis of algorithms; binary search trees; data organization; deletions; priority queues; Artificial intelligence; Binary search trees; Computer science; Data structures; Tree data structures; US Government; Analysis of algorithms; binary search trees; data organization; deletions; priority queues;
Journal_Title :
Software Engineering, IEEE Transactions on
DOI :
10.1109/TSE.1977.231160
