Изменения

'''Поисковая структура данных''' {{- --}} любая структура данных реализующая эффективный поиск конкретных элементов множества, например, конкретной записи в базе данных.

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

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

Эту классификацию обычно считают самой важной. Оценивают худшее время алгоритма, среднее и лучшее для каждой операции. Лучшее время — {{---}} минимальное время работы алгоритма на каком-либо наборе. Худшее время — {{---}} наибольшее время.

Параметр структуры данных, показывающий, сколько памяти ей требуется. Обычно затраты состовляют составляют <tex>O(n)</tex>.

Сравненим эффиктивность посиковых Сравним эффективность поисковых структур данных для реализации интерфейса [[Упорядоченное множество|упорядочего упорядоченного множества]]. Время работы методов <tex>Predecessor</tex> и <tex>Successor</tex> совпадает с временем работы <tex>Search</tex>. <tex>n</tex> {{---}} количество хранимых чисел, каждое из которых представляется с помощью <tex>w</tex> битов.

! Сре-<br>днееstyle="background: #ddffdd;" | Среднее! Худ-<br>шееstyle="background: #ffdddd;" | Худшее! Сре-<br>днееstyle="background: #ddffdd;" | Среднее! Худ-<br>шееstyle="background: #ffdddd;" | Худшее! Сре-<br>днееstyle="background: #ddffdd;" | Среднее! Худ-<br>шееstyle="background: #ffdddd;" | Худшее! Сре-<br>днееstyle="background: #ddffdd;" | Среднее! Худ-<br>шее! Сре-<br>днее! Худ-<br>шее! Сре-<br>днее! Худ-<br>шее! Сре-<br>днее! Худ-<br>шее! Сре-<br>днее! Худ-<br>шееstyle="background: #ffdddd;" | Худшее

| Неотсортированный<br>массив| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>| colspan="2" align="center" style="background: #ffddddddffdd;" | <tex>O(n1)</tex>| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>| colspan="2" align="center" style="background: #ffddddddffdd;" | <tex>O(n1)</tex>| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>

| Отсортированный<br>массив

| Неотсортированный<br>[[Список|список]]

| Отсортированный<br>[[Список|список]]

| [[Дерево поиска, наивная реализация|Дерево поиска,<br>наивная<br> реализация]]| 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>| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>

|[[Красно-черное дерево|Красно-черное<br>дерево]]| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| align="center" style="background: #ffdddd;" | Бинарное дерево, в узлах которого хранится пары <tex> (x,y) </tex>, где <tex>x</tex> - это ключ, а <tex>y</tex> - это приоритет. Также оно является [[Дерево поиска, наивная реализация|двоичным деревом поиска]] по <tex>x</tex> и [[Двоичная куча|пирамидой]] по <tex>y</tex>. Предполагая, что все <tex>x</tex> и все <tex>y</tex> являются различными, получаем, что если некоторый элемент дерева содержит <tex>O(nx_0,y_0)</tex>, то у всех элементов в левом поддереве <tex>x < x_0</tex>, у всех элементов в правом поддереве <tex> x > x_0</tex>, а также и в левом, и в правом поддереве имеем: <tex> y < y_0</tex>.|-|[[Splay-дерево]]

|-|[[Splay-дерево]]| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>[[Дерево поиска, наивная реализация| colspan="2" align="center" style="background: #ffffdd;" | <tex>OДвоичное дерево поиска]]. Оно позволяет находить быстрее те данные, которые использовались недавно, за счёт '''перемещения к корню''' (\log nангл. ''Move to root'')</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>. Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в 1983 году.

|[[Дерево ван Эмде Боаса|Дерево<br>ван Эмде Боаса]]| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log kw)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log kw)</tex>| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log kw)</tex>| colspan="2" align="center" style="background: #ddffddffdddd;" | <tex>O(12^w)</tex>| colspan="2" align="center" style="background: #ddffdd;" | Cтруктура данных, представляющая собой [[Дерево поиска, наивная реализация|дерево поиска]], позволяющее хранить целые неотрицательные числа в интервале <tex>O(1[0;2^w)</tex>и осуществлять над ними все соответствующие дереву поиска операции. Проще говоря, данная структура позволяет хранить <tex>w</tex>-битные числа.| colspan="2" align="center" style="background: #ffffdd;" | Особенностью этой структуры является то, что все операции выполняются за <tex>O(\log kw)</tex>| colspan="2" align="center" style="background: #ffffdd;" | , что асимптотически лучше, чем <tex>O(\log kn)</tex>| colspan="2" align="center" style="background: #ffdddd;" | в большинстве других деревьев поиска, где <tex>O(2^k)n</tex>{{---}} количество элементов в дереве.

| [[Список с пропусками|Список с<br>пропусками]]

|[[Сверхбыстрый цифровой бор|Сверхбыстрый<br> цифровой бор]]| align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>| align="center" style="background: #ffdddd;" | <tex>O(w)</tex>| align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>| align="center" style="background: #ffdddd;" | <tex>O(w)</tex>| align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>| align="center" style="background: #ffdddd;" | <tex>O(w)</tex>| align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>| aligncolspan="center2" style="background: #ffdddd;" | <tex>O(w)</tex>| align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>| align="center" style="background: #ffdddd;" | <tex>O(w)</tex>