From
computer science, this is the notion of tagging an item to be
ignored instead of actually deleting it. When an
algorithm traverses down a tree (or other data structure) and hits a
node that is tagged, it procedes through the
traversal without considering the item. Periodically, the
data structure in question is rebuilt with the tagged data excluded. Often this is done when the
percentage of deleted nodes reaches a
threshold (say, 10%), or after a certain amount of
time has passed.
You use a lazy delete in structures which take a prohibitively long time to do a real delete. In trees, for instance, you not only have to find the node and delete it, but do processing farther down in the tree to fill in the empty node created. Balanced trees (such as the AVL tree) are even worse, as the tree needs to be rebalanced after each real delete.
Lazy deletes may strike you as inelegant, but when you consider how much larger the worst case complexity for a delete operation can be than a find operation (O(n lg n) as opposed to O(lg n), etc.), they starts making much more sense.