延迟删除如何对二叉树或链表有利/不利？

Question

最近,对于数据结构类,我被问到一个问题,即如何删除懒惰(即,首先标记需要删除的项目的删除,然后在某个时候删除所有标记的项目)将是有利的/不利于数组,链表或二叉树.以下是我的想法:

• 这将有助于数组,因为每次删除索引时都会节省移动数组所花费的时间,尽管在需要遍历数组的算法中,可能效率低下.
• 这对链接列表没有帮助,因为您需要遍历O(n)以标记要删除的项目.
• 我不完全确定二叉树,但如果它是一个链表实现,我会想象它就像链表？

Answer 1

我认为这一切都取决于具体情况和要求。一般来说，使用这种方法对它们进行标记，然后将其删除，它们都有很多相似的优点和缺点。

类似的优点： - 当标记为删除时，数据结构不会发生变化，这使得删除速度更快。-您可以在已删除的项目之上插入，这意味着插入也无需移动，而且插入可以更快地完成，因为它可以覆盖第一个删除，而不是查找列表的末尾

类似的缺点： - 删除的项目浪费空间，因为它们只是坐在那里 - 必须横向两次才能删除项目，一次标记它，再一次删除它 - 许多标记的删除项目会污染进行搜索的数据结构由于必须搜索已删除的项目，因此需要更长的时间。