Изменения

ПростейшийПростейшей, наиболее общийобщей, но менее эффективный эффективной поисковой структурой является простая неупорядоченный неупорядоченная последовательная всех элементов. Расположив элементы в такой список, неизбежно возникнет ряд операций, которые потребуют линейного времени, в худшем случае, а также в средней случае. Используемые в реальной жизни поисковые структуры данных позволяют совершать операции более быстро, однако они ограничены запросами некоторого конкретного вида. Кроме того, поскольку стоимость построение таких структур пропорциональна <tex>n</tex>, их построение окупится, даже если поступает лишь несколько запросов.

'''Статические поисковые структуры данных''' (англ. ''Online Offline search structures'') предназначены для ответа на запросы на фиксированной базе данных.

'''Динамические поисковые структуры''' (англ. ''Offline Online search structures'') также позволяют вставки, удаления или модификации элементов между последовательными запросами. В динамическом случае, необходимо также учитывать стоимость изменения структуры данных. Любую динамическую структуру данных можно сделать статической, если запретить вставку и удаление. Также если множество ключей известно, то можно его заранее упорядочить так, чтобы избежать худших случаев в поисках в структурах данных.

| align="center" rowspan="2" | Аналогично массиву, но храним данные в [[Список|списке]]. Можно хранить дополнительную информацию о вершинах, что позволит ускорить время работы операции delete.

| align="center" | Вариант [[Дерево поиска, наивная реализация|двоисного двоичного дерево поиска]] с добавлением инвариата "случайности", что уменьнашает ожидаемую высоту дерева.|-

*[[:Сортировка|Сортировка]]*[[:Поиск_подстроки_в_строке|Поиск подстроки в строке]]*[[:Приоритетные_кучи|Приоритетные кучиочереди]]