55
правок
Изменения
Нет описания правки
Простейший, наиболее общий, но менее эффективный поисковой структурой является простая неупорядоченный последовательная всех элементов. Расположив элементы в такой список, неизбежно возникнет ряд операций, которые потребуют линейного времени, в худшем случае, а также в средней случае. Используемые в реальной жизни поисковые структуры данных позволяют совершать операции более быстро, однако они ограничены запросами некоторого конкретного вида. Кроме того, поскольку стоимость построение таких структур, по крайней мере пропорционально n, они окупятся, даже если поступает лишь несколько запросов.
=== Тип === '''Статические поисковые структуры данных''' (англ. ''Online search structures'') предназначены для ответа на запросы на фиксированной базе данных; '''Динамические поисковые структуры''' (англ. ''Offline search structures'') также позволяют вставки, удаления или модификации элементов между последовательными запросами. В динамическом случае, необходимо также учитывать стоимость изменения структуры данных. Любую динамическую структуру данных можно сделать статической, если запретить вставку и удаление. Также если множество ключей известно, то можно его заранее упорядочить так, чтобы избежать худших случаев в поисках в структурах данных.
=== Время работы ===
| 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 году. Это лучшая известная реализация на данный момент.
|}
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Деревья поиска]]
[[Категория: Структуры данных]]
