#optimization #data-structures
#оптимизация #структуры данных
Вопрос:
В некоторых текстовых редакторах необходимо выполнить следующие операции:
- вставить один символ
- удалить один символ
Пример связанного списка:
Insert(3,"x"):
before: [a]-[b]-[c]-[d]-...
after: [a]-[b]-[x]-[c]-[d]-...
Delete(3):
before: [a]-[b]-[x]-[c]-[d]-...
after: [a]-[b]-[c]-[d]-...
Какая структура данных была бы оптимальной для реализации такого поведения? (мое внутреннее ощущение: красно-черное дерево)
Комментарии:
1. Если под оптимальной вы подразумеваете наименьшую большую O, любая древовидная структура будет лучше, чем LinkedList, O (n) против O (log (n)). Это включает в себя поиск персонажа и его удаление. Если время, необходимое для написания программы, является важным фактором, то LinkedList будет оптимальным решением, если предположить, что вы пишете эти структуры данных с нуля.
2. Да, я имею в виду оптимальную сложность алгоритма, т.Е. Наименьшую оценку big-O для наихудшего случая. Обратите внимание, что операции удаления и вставки выполняются в соответствии со смещением от начала данных, а не путем поиска символа. Таким образом, структура данных должна отслеживать положение каждого символа и обеспечивать эффективный алгоритм поиска k-го элемента. Связанный список был просто примером, иллюстрирующим функциональность, я ожидаю, что это можно сделать быстрее с помощью какой-либо другой структуры данных.