Удаление узла в дереве BK

Я видел множество различных реализаций BK Trees в множестве разные языки, и буквально ни один из них не включает способ удаления узлов из дерева.

Даже исходная статья, где впервые были представлены BK Trees, не дает осмысленного представления о удаление узла, так как авторы просто предлагают пометить узел для удаления, чтобы он игнорировался:

Удаление ключа в структурах 1 [Дерево BK] и 2 следует процессу, аналогичному описанному выше, с особым вниманием к случаю, когда удаляемый ключ является репрезентативным x° [корневой ключ]. В этом случае ключ нельзя просто удалить, так как он необходим для информации о структуре. Вместо этого для каждого ключа должен использоваться дополнительный бит, который указывает, действительно ли ключ соответствует записи или нет. Алгоритм поиска изменен соответствующим образом, чтобы игнорировать ключи, не соответствующие записям. Это включает проверку дополнительного бита в процедуре обновления.

Хотя теоретически возможно правильно удалить узел в дереве BK, возможно ли это сделать за линейное/сублинейное время?


algorithm tree time-complexity abstract-data-type bk-tree
person farsil    schedule 14.02.2017    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Хотя теоретически возможно правильно удалить узел в дереве BK, возможно ли это сделать за линейное/сублинейное время?

Если вы хотите физически удалить его из BK-дерева, то я не могу придумать способ сделать это за линейное время для всех случаев. Рассмотрим 2 сценарии, когда узел удаляется. Обратите внимание, что я не учитываю временную сложность, связанную с вычислением расстояния Левенштейна, потому что эта операция не зависит от количества слов, хотя и требует некоторого времени обработки.

Удалить некорневой узел

  1. Найдите родителя узла в дереве.
  2. Сохраните дочерние узлы узла.
  3. Обнулить родительскую ссылку на узел.
  4. Повторно добавьте каждый дочерний узел, как если бы это был новый узел.

Здесь, даже если шаг 1 можно выполнить за O(1), шаги 2 и 4 намного дороже. Вставка одного узла — это O(h), где h — высота дерева. Что еще хуже, это нужно сделать для каждого дочернего узла исходного узла, и поэтому это будет O (k * h), где k — количество дочерних узлов.

Удалить корневой узел

  1. Восстановите дерево с нуля, не используя предыдущий корневой узел.

Восстановление дерева будет как минимум O(n) в лучшем случае и O(h*n) в противном случае.

Альтернативное решение

Поэтому лучше не удалять узел физически, а оставить его в дереве и просто пометить как deleted. Таким образом, он будет использоваться, как и прежде, для вставки новых узлов, но будет исключен из результатов предложения для слова с ошибкой. Это можно сделать за O(1).

person Anatolii    schedule 14.04.2021