1632
правки
Изменения
м
ПростейшийПростейшей, наиболее общийобщей, но менее эффективный эффективной поисковой структурой является простая неупорядоченный неупорядоченная последовательная всех элементов. Расположив элементы в такой список, неизбежно возникнет ряд операций, которые потребуют линейного времени, в худшем случае, а также в средней случае. Используемые в реальной жизни поисковые структуры данных позволяют совершать операции более быстро, однако они ограничены запросами некоторого конкретного вида. Кроме того, поскольку стоимость построение таких структур, по крайней мере пропорционально пропорциональна <tex>n</tex>, они окупятсяих построение окупится, даже если поступает лишь несколько запросов.
rollbackEdits.php mass rollback
'''Поисковая структура данных''' {{---}} любая структура данных реализующая эффективный поиск конкретных элементов множества, например, конкретной записи в базе данных.
=== Тип === '''Статические поисковые структуры данных''' (англ. ''Online Offline search structures'') предназначены для ответа на запросы на фиксированной базе данных; . '''Динамические поисковые структуры''' (англ. ''Offline Online search structures'') также позволяют вставки, удаления или модификации элементов между последовательными запросами. В динамическом случае, необходимо также учитывать стоимость изменения структуры данных. Любую динамическую структуру данных можно сделать статической, если запретить вставку и удаление. Также если множество ключей известно, то можно его заранее упорядочить так, чтобы избежать худших случаев в поисках в структурах данных.
=== Время работы ===
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
| align="center" rowspan="2" | Аналогично массиву, но храним данные в [[Список|списке]]. Можно хранить дополнительную информацию о вершинах, что позволит ускорить время работы операции delete.
|-
| Отсортированный [[Список|список]]
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
| align="center" | Бинарное дерево поиска обладает следующим свойством: если <tex>x</tex> {{---}} узел бинарного дерева с ключом <tex>k</tex>, то все узлы в левом поддереве должны иметь ключи, меньшие <tex>k</tex>, а в правом поддереве большие <tex>k</tex>.
|-
| [[Рандомизированное бинарное дерево поиска]]
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
| align="center" | Вариант [[Дерево поиска, наивная реализация|двоичного дерево поиска]] с добавлением инвариата "случайности", что уменьнашает ожидаемую высоту дерева.
|-
|[[АВЛ-дерево]]
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
| align="center" stylecolspan="background: #ffffdd;2" | <tex>O(n)</tex> | align="center" style="background: #ffddddffffdd;" | <tex>O(n \log n)</tex>
| align="center" | Вероятностная структура данных, основанная на нескольких отсортированных односвязных списках.
Отсортированный связный список является простейшей структурой с временем поиска <tex>\Theta(n)</tex>. Добавление дополнительных уровней, обеспечивающих быстрый доступ через несколько элементов, помогает улучшить асимптотику до <tex>\Theta(\log(n))</tex>
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(\log \log n)</tex>
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
| align="center" | Online [[Дерево поиска, наивная реализация|двоичное Двоичное дерево поиска]], которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и Михаи Патраску в 2004 году. Не поддерживает операции вставки и удаления, но перестраивается по ходу поисковых запросов, чтобы отвечать на них как можно оптимальней. Это лучшая известная реализация на данный момент.
|}
==См. также==
*[[:Сортировка|Сортировка]]*[[:Поиск_подстроки_в_строке|Поиск подстроки в строке]]*[[:Приоритетные_кучи|Приоритетные кучиочереди]]
== Источники информации ==
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Деревья поиска]]
[[Категория: Структуры данных]]
