Изменения

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

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

| colspan="2" align="center" style="background: #ffddddddffdd;" | <tex>O(n1)</tex>

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

| colspan="2" align="center" style="background: #ffddddddffdd;" | <tex>O(n1)</tex>

| align="center" | Сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на <tex>1</tex>.

| align="center" | Бинарное дерево, в узлах которого хранится пары <tex> (x,y) </tex>, где <tex>x</tex> {{- --}} это ключ, а <tex>y</tex> {{--- }} это приоритет. Также оно является [[Дерево поиска, наивная реализация|двоичным деревом поиска]] по <tex>x</tex> и [[Двоичная куча|пирамидой]] по <tex>y</tex>. Предполагая, что все <tex>x</tex> и все <tex>y</tex> являются различными, получаем, что если некоторый элемент дерева содержит <tex>(x_0,y_0)</tex>, то у всех элементов в левом поддереве <tex>x < x_0</tex>, у всех элементов в правом поддереве <tex> x > x_0</tex>, а также и в левом, и в правом поддереве имеем: <tex> y < y_0</tex>.

| align="center" stylecolspan="background: #ffffdd;2" | <tex>O(n)</tex> | align="center" style="background: #ffddddffffdd;" | <tex>O(n \log n)</tex>

|[[Сверхбыстрый цифровой бор|Цифровой бор]]| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(w)</tex>| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(w)</tex>| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(w)</tex>| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n \cdot w)</tex>| align="center" | [[Бор]], в котором в качестве строк используются двоичные записи чисел, включая ведущие нули. Таким образом он имеет глубину <tex>w</tex>.|-| [[Сверхбыстрый цифровой бор|Быстрый цифровой бор]]| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(w)</tex>| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(w)</tex>

| align="center" | Улучшеная версия структуры быстрого цифрового бора.|-!! colspan="9" align="center" | Статические структуры данных|-|[[Tango-дерево]]| colspan="2" align="center" style="background: #e5e5e5;" | -| colspan="2" align="center" style="background: #e5e5e5;" | -| 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" | [[Дерево поиска, наивная реализация|Двоичное дерево поиска]], которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и Михаи Патраску в 2004 году. Не поддерживает операции вставки и удаления, но перестраивается по ходу поисковых запросов, чтобы отвечать на них как можно оптимальней. Это лучшая известная реализация на данный момент.

==См. Такжетакже==

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

* [http://habrahabr.ru/post/156361188010/ Алгоритмы и структуры данных Habrahabr {{---}} шпаргалкаЗнай сложности алгоритмов ]