Чем ленивое удаление выгодно / невыгодно для двоичного дерева или связанного списка?

Question

Недавно для класса структур данных мне был задан вопрос о том, как отложенное удаление (то есть удаление, которое сначала отмечает элементы, которые необходимо удалить, а затем через некоторое время удаляет все отмеченные элементы) быть выгодным / невыгодным для массива, связанного списка или двоичного дерева. Вот что я придумала:

• Это поможет массивам, потому что вы сэкономите время, затрачиваемое на смещение массива каждый раз, когда индекс удаляется, хотя в алгоритмах, которым необходимо проходить по массиву, могут быть недостатки.
• Это не поможет связанным спискам, потому что вам нужно пройти O (n), чтобы пометить элемент, который будет удален в любом случае.
• Я не совсем уверен насчет бинарных деревьев, но если бы это была реализация связанного списка, я бы подумал, что это похоже на связанный список?

Answer 1

Я думаю, что все зависит от обстоятельств и требований.В общем смысле, используя этот метод, где они помечаются, а затем удаляются позже, все они имеют много похожих плюсов и минусов.

Подобные плюсы: -При маркировке для удаления нет смещения структур данных, чтоделает удаление намного быстрее-Вы можете вставить поверх удаленного элемента, что означает, что смещения для вставок также не требуется, плюс вставка может быть выполнена быстрее, поскольку она может записывать поверх первого удаления вместо поиска конца списка

Аналогичные минусы: -Потеря места для удаленного элемента, так как они просто сидят там -Есть два раза поперек, чтобы удалить элемент, один раз, чтобы пометить его и еще раз, чтобы удалить его -Многие отмеченные элементы для удаления будут загрязнять структуру данных, делая поиск дольшепоскольку удаленные элементы должны быть найдены.

Answer 2

Я думаю, что ответ будет "это зависит" по разным причинам, но я думаю, что вы на правильном пути.

1) Я согласен с вашим ответом относительно массивов, предполагая, что естьТребование, чтобы в вашем массиве не было дыр.Если вам не требуется сдвигать массив при каждом удалении, тогда предложенный подход «пометить сейчас, позже удалить» не поможет вообще.В любом случае, вы имеете дело с O (n) против (2O (n) = O (n)) для алгоритма, которые равны.Реальная вещь, о которой стоит подумать: «Переупорядочивание всех удалений за один раз по сравнению с переупорядочением каждого удаления по отдельности спасет вас в любое время?»Предполагая, что m - это количество удалений, число раз, когда каждый элемент после первого удаления в вашем массиве переупорядочивается, составляет O (m) для подхода немедленного удаления по сравнению с O (1) для отметки сейчас, удалить последующий подход.

2) Я согласен с вашим ответом для связанных списков.

3) Что касается бинарного дерева, я полагаю, что это будет зависеть от его вида.Если вы используете отсортированное сбалансированное двоичное дерево, вам придется рассмотреть тот же вопрос, что и в пункте 1) выше, но если нет, ваши мысли верны, и он должен вести себя точно так же, как связанный список.

Answer 3

Возможно, вам нужно подумать немного глубже о реализации связанных списков. Вы указываете, что отложенное удаление НЕ поможет в любом случае, потому что время для поиска - это все время, необходимое для выполнения удаления.

Подумайте, что нужно, чтобы фактически УДАЛИТЬ элемент из связанного списка. примечание: это предполагает ЕДИНСТВЕННО связанный список (не двойной список) 1) Найдите элемент, который нужно удалить (потому что это ОДИН связанный список, вам всегда нужно искать, потому что вам нужен элемент PREV) 2) Держите указатели на элементы PREV и NEXT 3) Зафиксируйте элемент «PREV», чтобы он указывал на элемент «NEXT», изолируя элемент CURRENT. 3.5) в двойном связанном списке вы также должны позаботиться об элементе NEXT, указывающем обратно на элемент PREV. 4) Освободить память, связанную с элементом CURRENT

Теперь, каков процесс отложенного удаления? --- намного короче 1) Найдите элемент для удаления (вам может даже не потребоваться выполнить поиск, так как у вас уже есть указатель на объект, который вы хотите удалить?) 2) пометить пункт для удаления.

*) Дождитесь запуска потока «Сборка мусора» и фактически выполните оставшиеся шаги, когда система находится в состоянии «IDLE»

Бинарное дерево, реализованное в виде связанного списка, в котором каждый элемент имеет левое и правое - однако вы все равно выполняете те же шаги в поиске. Я полагаю, что поиск двоичного дерева более эффективен с O (Log (n)).

Однако удаление из них становится более сложным, потому что у вас есть больше указателей для работы (и «ВЛЕВО», и «ВПРАВО») - поэтому потребуется больше инструкций для исправления, особенно при удалении узла дерева, который имеет указатели на узлы как для левого, так и для правого - один из них нужно будет перевести в новый корень - однако, что если им обоим уже назначены левый и правый указатели? Куда идет исходный «левый / правый» узел? - Вы должны повторно сбалансировать дерево в этой точке. Таким образом, существует значительная экономия по марке для удаления с точки зрения пользователя и наличия "незанятого" сбора мусора, заботящегося о деталях памяти (поэтому пользователю не нужно ждать этого).