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.

Log in or register to write something here or to contact authors.