Практическая реализация деталей краев наклейки/расщепление в деревьях оснований

Question

Это вопрос о том, что обычно делается на практике.

Скажем, у нас было базисное дерево с одним входом (по какой-либо причине, считают, что это будет одна запись для демонстрации):

"tests are really hard, no one likes taking tests, they're the worst" 

И тогда мы хотим поставить на второй вход

"team" 

Мы хотим, чтобы в конечном итоге с краю от корня с

"te" 

и два края от того, один с

"sts are really hard, no one likes taking tests, they're the worst" 

и один с

"am" 

наивность, мы могли бы создать новые строки (символьные массивы, что угодно) для "тэ" и "петель являются на самом деле ...". Это требует многих операций, даже если наше новое слово «команда» короткое.

С другой стороны, мы могли бы иметь «тэ» и «СЦ является на самом деле ...» этикетка может содержать ссылку на ту же исходную строку, а также запуск/конечные значения, то есть:

[0, 2] for "te" 

и

[2, <whatever it is>] for "sts are really..." 

Таким образом, мы избегаем любого копирования, и время вставки «команды» зависит только от длины «команды», а не на длинах других строк, а именно «тесты являются на самом деле ... " в этом случае.

Так что вопрос о том, является ли k в O(k), означает длину вставляемой строки или длинную строку.

Очевидно, что последняя реализация сложнее и может на практике использовать больше памяти (из-за хранения конечных точек), но похоже, что теоретический худший случай время улучшено.

Мне интересно, знает ли кто, что обычно делается на практике?

Благодаря

EDIT: Я думаю, одна проблемы с последней реализацией будет возникать с удалениями. Если вы позже ввели «телепатию», но затем удалили «тесты действительно тяжелые ...», край «te» остался бы и все еще будет иметь ссылку на строку намного дольше, чем нужно.

Answer 1

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

Предполагая, что метки краев сохраняются в виде пар индексов в целую клавишу, тогда сращивание может быть выполнено путем изменения нижнего индекса для оставшегося ребенка. Чтобы «мусор собирать» все остальные экземпляры удаляемого ключа, можно сканировать rootward, переписывая метки границ, содержащие удаленный ключ, для ссылки на родного брата. В худшем случае нам нужно полностью отсканировать назад к корню, не увеличивая асимптотическое время работы, но для случайных операций ожидаемое количество переписываний является постоянным.Неясно, стоит ли накладные расходы сохраненным копиям.