Обзор поисковых структур данных — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «'''Поисковая структура данных''' - любая структура данных реализующая эффективный поиск к...»)
 
м (rollbackEdits.php mass rollback)
 
(не показано 5 промежуточных версий 2 участников)
Строка 1: Строка 1:
'''Поисковая структура данных''' - любая структура данных реализующая эффективный поиск конкретных элементов множества, например, конкретной записи в базе данных.
+
'''Поисковая структура данных''' {{---}} любая структура данных реализующая эффективный поиск конкретных элементов множества, например, конкретной записи в базе данных.
  
Простейший, наиболее общий, но менее эффективный поисковой структурой является простая неупорядоченный последовательная всех элементов. Расположив элементы в такой список, неизбежно возникнет ряд операций, которые потребуют линейного времени, в худшем случае, а также в средней случае. Используемные в реальной жизни поисковые структуры данных позволяют совершать операции более быстро, однако они ограничены запросами некоторого конкретного вида. Кроме того, поскольку стоимость построение таких структур, по крайней мере пропорционально n, они окупятся, даже если поступает лишь несколько запросов.
+
Простейший, наиболее общий, но менее эффективный поисковой структурой является простая неупорядоченный последовательная всех элементов. Расположив элементы в такой список, неизбежно возникнет ряд операций, которые потребуют линейного времени, в худшем случае, а также в средней случае. Используемые в реальной жизни поисковые структуры данных позволяют совершать операции более быстро, однако они ограничены запросами некоторого конкретного вида. Кроме того, поскольку стоимость построение таких структур, по крайней мере пропорционально n, они окупятся, даже если поступает лишь несколько запросов.
  
'''Статические''' поисковые структуры данных предназначены для ответа на запросы на фиксированной базе данных; '''Динамические''' поиковые структуры также позволяют вставки, удаления или модификации элементов между последовательными запросами. В динамическом случае, необходимо также учитывать стоимость изменения структуры данных.
+
'''Статические поисковые структуры данных''' (англ. ''Static search structures'') предназначены для ответа на запросы на фиксированной базе данных; '''Динамические поисковые структуры''' (англ. ''Dynamic search structures'') также позволяют вставки, удаления или модификации элементов между последовательными запросами. В динамическом случае, необходимо также учитывать стоимость изменения структуры данных.
  
 
=== Время работы ===
 
=== Время работы ===
  
Эту классификацию обычно считают самой важной. Оценивают худшее время алгоритма, среднее и лучшее для каждой операции. Лучшее время минимальное время работы алгоритма на каком-либо наборе. Худшее время наибольшее время.
+
Эту классификацию обычно считают самой важной. Оценивают худшее время алгоритма, среднее и лучшее для каждой операции. Лучшее время {{---}} минимальное время работы алгоритма на каком-либо наборе. Худшее время {{---}} наибольшее время.
  
 
=== Используемая память ===
 
=== Используемая память ===
  
Параметр структуры данных, показывающий, сколько памяти ей требуется. Обычно затраты состовляют <tex>O(n)</tex>.
+
Параметр структуры данных, показывающий, сколько памяти ей требуется. Обычно затраты составляют <tex>O(n)</tex>.
  
 
=== Сравнение структур данных ===
 
=== Сравнение структур данных ===
  
Сравненим эффиктивность посиковых структур данных для реализации интерфейса [[Упорядоченное множество|упорядочего множества]].
+
Сравним эффективность поисковых структур данных для реализации интерфейса [[Упорядоченное множество|упорядоченного множества]]. Время работы методов <tex>Predecessor</tex> и <tex>Successor</tex> совпадает с временем работы <tex>Search</tex>.
 +
 
 +
<tex>n</tex> {{---}} количество хранимых чисел, каждое из которых представляется с помощью <tex>w</tex> битов.
  
 
{| class="wikitable"
 
{| class="wikitable"
Строка 23: Строка 25:
 
! colspan="2" | Delete
 
! colspan="2" | Delete
 
! colspan="2" | Search
 
! colspan="2" | Search
! colspan="2" | Minimum
 
! colspan="2" | Maximum
 
! colspan="2" | Predecessor
 
! colspan="2" | Successor
 
 
! colspan="2" | Память
 
! colspan="2" | Память
 +
! rowspan="2" | Описание
 
|-
 
|-
! Сре-<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>шее
+
! style="background: #ffdddd;" | Худшее
! Сре-<br>днее
 
! Худ-<br>шее
 
! Сре-<br>днее
 
! Худ-<br>шее
 
! Сре-<br>днее
 
! Худ-<br>шее
 
! Сре-<br>днее
 
! Худ-<br>шее
 
 
|-
 
|-
| Неотсортированный<br>массив
+
| Неотсортированный массив
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
+
| align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
+
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
+
| align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
+
| 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: #ffdddd;" | <tex>O(n)</tex>
 
 
| 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: #ffffdd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 +
| align="center" | Наивная реализация, использующая [[Динамический массив|динамический массив]]. Добавление происходит в конец массива, а для поиска элемента просто проходим по всему массиву.
 
|-
 
|-
| Отсортированный<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: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
 
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
 
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</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>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 +
| align="center" | То же самое, но теперь массив отсортирован. Поиск ускоряется за счёт возможности применить [[Целочисленный двоичный поиск|двоичный поиск]]. Вставка замедляется из-за необходимости поддерживать инвариант отсортированности.
 
|-
 
|-
| Неотсортированный<br>[[Список|список]]
+
| Неотсортированный [[Список|список]]
 
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
 
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
| 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: #ffdddd;" | <tex>O(n)</tex>
 
| 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: #ffdddd;" | <tex>O(n)</tex>
 
| 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: #ffffdd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 +
| align="center" rowspan="2" | Аналогично массиву, но храним данные в [[Список|списке]]. Можно хранить дополнительную информацию о вершинах, что позволит ускорить время работы операции delete.
 
|-
 
|-
| Отсортированный<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: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
 
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
 
 
| 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: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 
|-
 
|-
| [[Дерево поиска, наивная реализация|Дерево поиска,<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>
 
 
| align="center" style="background: #ffffdd;" | <tex>O(\log 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: #ffdddd;" | <tex>O(n)</tex>
Строка 102: Строка 74:
 
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 
| 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>.
 
|-
 
|-
 
|[[АВЛ-дерево]]
 
|[[АВЛ-дерево]]
| 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(\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>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 +
| align="center" | Сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.
 
|-
 
|-
 
|[[2-3 дерево]]
 
|[[2-3 дерево]]
| 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(\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>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 +
| align="center" | Структура данных, представляющая собой сбалансированное дерево поиска, такое что из каждого узла может выходить две или три ветви и глубина всех листьев одинакова. Является частным случаем [[B-дерево#B.2B-.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D0.BE|B+ дерева]].
 
|-
 
|-
 
|[[B-дерево]]
 
|[[B-дерево]]
| 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(\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>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 +
| align="center" | Cильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за <tex>O(\log n)</tex>. B-дерево с <tex>n</tex> узлами имеет высоту <tex>O(\log n)</tex>. Количество детей узлов может быть от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время <tex>O(\log 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>
 
| 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>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 +
| align="center" | Сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором баланс осуществляется на основе "цвета" узла дерева, который принимает только два значения: "красный" (англ. ''red'') и "чёрный" (англ. ''black'').  При этом все листья дерева являются фиктивными и не содержат данных, но относятся к дереву и являются чёрными.
 
|-
 
|-
 
| [[Декартово дерево]]
 
| [[Декартово дерево]]
Строка 150: Строка 111:
 
| align="center" style="background: #ffffdd;" | <tex>O(\log 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: #ffdddd;" | <tex>O(n)</tex>
| align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>
+
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
| align="center" style="background: #ffdddd;" | <tex>O(n)</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>.
 +
|-
 +
|[[Splay-дерево]]
 
| align="center" style="background: #ffffdd;" | <tex>O(\log 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: #ffdddd;" | <tex>O(n)</tex>
Строка 159: Строка 122:
 
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
|-
+
| align="center" | [[Дерево поиска, наивная реализация|Двоичное дерево поиска]]. Оно позволяет находить быстрее те данные, которые использовались недавно, за счёт '''перемещения к корню''' (англ. ''Move to root''). Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в 1983 году.
|[[Splay-дерево]]
 
| 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(\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>
 
 
|-
 
|-
 
|[[Tango-дерево]]
 
|[[Tango-дерево]]
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(\log \log n)</tex>
 
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(\log \log n)</tex>
 
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(\log \log n)</tex>
 
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(\log \log n)</tex>
 
 
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(\log \log n)</tex>
 
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(\log \log n)</tex>
 
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(\log \log n)</tex>
 
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(\log \log n)</tex>
 
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(\log \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>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 +
| align="center" | Online [[Дерево поиска, наивная реализация|двоичное дерево поиска]], которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и Михаи Патраску в 2004 году. Это лучшая известная реализация на данный момент.
 
|-
 
|-
|[[Дерево ван Эмде Боаса|Дерево<br>ван Эмде Боаса]]
+
|[[Дерево ван Эмде Боаса]]
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log k)</tex>
+
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log k)</tex>
+
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log k)</tex>
+
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
+
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(2^w)</tex>
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
+
| align="center" | Cтруктура данных, представляющая собой [[Дерево поиска, наивная реализация|дерево поиска]], позволяющее хранить целые неотрицательные числа в интервале <tex>[0;2^w)</tex> и осуществлять над ними все соответствующие дереву поиска операции. Проще говоря, данная структура позволяет хранить <tex>w</tex>-битные числа.
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log k)</tex>
+
Особенностью этой структуры является то, что все операции выполняются за <tex>O(\log w)</tex>, что асимптотически лучше, чем <tex>O(\log n)</tex> в большинстве других деревьев поиска, где <tex>n</tex> {{---}} количество элементов в дереве.
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log k)</tex>
 
| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(2^k)</tex>
 
 
|-
 
|-
| [[Список с пропусками|Список с<br>пропусками]]
+
| [[Список с пропусками]]
 
| align="center" style="background: #ffffdd;" | <tex>O(\log 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: #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: #ddffdd;" | <tex>O(1)</tex>
 
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(1)</tex>
 
 
| align="center" style="background: #ffffdd;" | <tex>O(\log 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: #ffdddd;" | <tex>O(n)</tex>
Строка 205: Строка 148:
 
| align="center" style="background: #ffffdd;" | <tex>O(n)</tex>  
 
| align="center" style="background: #ffffdd;" | <tex>O(n)</tex>  
 
| align="center" style="background: #ffdddd;" | <tex>O(n \log n)</tex>  
 
| align="center" style="background: #ffdddd;" | <tex>O(n \log n)</tex>  
 +
| align="center" | Вероятностная структура данных, основанная на нескольких отсортированных односвязных списках.
 +
Отсортированный связный список является простейшей структурой с временем поиска <tex>\Theta(n)</tex>. Добавление дополнительных уровней, обеспечивающих быстрый доступ через несколько элементов, помогает улучшить асимптотику до <tex>\Theta(\log(n))</tex>
 
|-
 
|-
 
|[[Fusion tree]]
 
|[[Fusion tree]]
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log_{w} n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log_{w} n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log_{w} n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log_{w} n)</tex>
 
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log_{w} n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log_{w} n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log_{w} n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log_{w} n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log_{w} n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log_{w} n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 +
| align="center" | Дерево поиска, позволяющее хранить <tex>n</tex> <tex>w</tex>-битных чисел, используя <tex>O(n)</tex> памяти, и выполнять операции поиска за время <tex>O(\log_{w} n)</tex>. Эта структура данных была впервые предложена в 1990 году М. Фредманом (M. Fredman) и Д. Уиллардом (D. Willard).
 
|-
 
|-
|[[Сверхбыстрый цифровой бор|Сверхбыстрый<br> цифровой бор]]
+
|[[Сверхбыстрый цифровой бор]]
| align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>
+
| colspan="2" 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>
 
| 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: #ffffdd;" | <tex>O(\log w)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(w)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(w)</tex>
Строка 232: Строка 165:
 
| align="center" style="background: #ffdddd;" | <tex>O(w)</tex>
 
| align="center" style="background: #ffdddd;" | <tex>O(w)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 +
| align="center" | Улучшеная версия структуры цифрового бора.
 
|}
 
|}
 +
 +
==См. Также==
 +
 +
*[[:Сортировка|Сортировка]]
 +
*[[:Поиск_в_строках|Поиск в строках]]
 +
*[[:Поиск_подстроки_в_строке|Поиск подстроки в строке]]
 +
*[[:Приоритетные_кучи|Приоритетные кучи]]
 +
 +
== Источники информации ==
 +
 +
* [[wikipedia:en:Search_data_structure|Wikidedia {{---}} Search data structure]]
 +
* [http://habrahabr.ru/post/156361/ Алгоритмы и структуры данных {{---}} шпаргалка]
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Деревья поиска]]

Текущая версия на 19:31, 4 сентября 2022

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

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

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

Время работы

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

Используемая память

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

Сравнение структур данных

Сравним эффективность поисковых структур данных для реализации интерфейса упорядоченного множества. Время работы методов [math]Predecessor[/math] и [math]Successor[/math] совпадает с временем работы [math]Search[/math].

[math]n[/math] — количество хранимых чисел, каждое из которых представляется с помощью [math]w[/math] битов.

Insert Delete Search Память Описание
Среднее Худшее Среднее Худшее Среднее Худшее Среднее Худшее
Неотсортированный массив [math]O(1)[/math] [math]O(n)[/math] [math]O(1)[/math] [math]O(n)[/math] [math]O(n)[/math] [math]O(n)[/math] Наивная реализация, использующая динамический массив. Добавление происходит в конец массива, а для поиска элемента просто проходим по всему массиву.
Отсортированный массив [math]O(n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] То же самое, но теперь массив отсортирован. Поиск ускоряется за счёт возможности применить двоичный поиск. Вставка замедляется из-за необходимости поддерживать инвариант отсортированности.
Неотсортированный список [math]O(1)[/math] [math]O(n)[/math] [math]O(n)[/math] [math]O(n)[/math] Аналогично массиву, но храним данные в списке. Можно хранить дополнительную информацию о вершинах, что позволит ускорить время работы операции delete.
Отсортированный список [math]O(n)[/math] [math]O(n)[/math] [math]O(n)[/math] [math]O(n)[/math]
Дерево поиска, наивная реализация [math]O(\log n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] [math]O(n)[/math] Бинарное дерево поиска обладает следующим свойством: если [math]x[/math] — узел бинарного дерева с ключом [math]k[/math], то все узлы в левом поддереве должны иметь ключи, меньшие [math]k[/math], а в правом поддереве большие [math]k[/math].
АВЛ-дерево [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] Сбалансированное двоичное дерево поиска, в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.
2-3 дерево [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] Структура данных, представляющая собой сбалансированное дерево поиска, такое что из каждого узла может выходить две или три ветви и глубина всех листьев одинакова. Является частным случаем B+ дерева.
B-дерево [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] Cильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за [math]O(\log n)[/math]. B-дерево с [math]n[/math] узлами имеет высоту [math]O(\log n)[/math]. Количество детей узлов может быть от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время [math]O(\log n)[/math]
Красно-черное дерево [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] Сбалансированное двоичное дерево поиска, в котором баланс осуществляется на основе "цвета" узла дерева, который принимает только два значения: "красный" (англ. red) и "чёрный" (англ. black). При этом все листья дерева являются фиктивными и не содержат данных, но относятся к дереву и являются чёрными.
Декартово дерево [math]O(\log n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] [math]O(n)[/math] Бинарное дерево, в узлах которого хранится пары [math] (x,y) [/math], где [math]x[/math] - это ключ, а [math]y[/math] - это приоритет. Также оно является двоичным деревом поиска по [math]x[/math] и пирамидой по [math]y[/math]. Предполагая, что все [math]x[/math] и все [math]y[/math] являются различными, получаем, что если некоторый элемент дерева содержит [math](x_0,y_0)[/math], то у всех элементов в левом поддереве [math]x \lt x_0[/math], у всех элементов в правом поддереве [math] x \gt x_0[/math], а также и в левом, и в правом поддереве имеем: [math] y \lt y_0[/math].
Splay-дерево [math]O(\log n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] [math]O(n)[/math] Двоичное дерево поиска. Оно позволяет находить быстрее те данные, которые использовались недавно, за счёт перемещения к корню (англ. Move to root). Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в 1983 году.
Tango-дерево [math]O(\log \log n)[/math] [math]O(\log \log n)[/math] [math]O(\log \log n)[/math] [math]O(n)[/math] Online двоичное дерево поиска, которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и Михаи Патраску в 2004 году. Это лучшая известная реализация на данный момент.
Дерево ван Эмде Боаса [math]O(\log w)[/math] [math]O(\log w)[/math] [math]O(\log w)[/math] [math]O(2^w)[/math] Cтруктура данных, представляющая собой дерево поиска, позволяющее хранить целые неотрицательные числа в интервале [math][0;2^w)[/math] и осуществлять над ними все соответствующие дереву поиска операции. Проще говоря, данная структура позволяет хранить [math]w[/math]-битные числа.

Особенностью этой структуры является то, что все операции выполняются за [math]O(\log w)[/math], что асимптотически лучше, чем [math]O(\log n)[/math] в большинстве других деревьев поиска, где [math]n[/math] — количество элементов в дереве.

Список с пропусками [math]O(\log n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] [math]O(\log n)[/math] [math]O(n)[/math] [math]O(n)[/math] [math]O(n \log n)[/math] Вероятностная структура данных, основанная на нескольких отсортированных односвязных списках.

Отсортированный связный список является простейшей структурой с временем поиска [math]\Theta(n)[/math]. Добавление дополнительных уровней, обеспечивающих быстрый доступ через несколько элементов, помогает улучшить асимптотику до [math]\Theta(\log(n))[/math]

Fusion tree [math]O(\log_{w} n)[/math] [math]O(\log_{w} n)[/math] [math]O(\log_{w} n)[/math] [math]O(n)[/math] Дерево поиска, позволяющее хранить [math]n[/math] [math]w[/math]-битных чисел, используя [math]O(n)[/math] памяти, и выполнять операции поиска за время [math]O(\log_{w} n)[/math]. Эта структура данных была впервые предложена в 1990 году М. Фредманом (M. Fredman) и Д. Уиллардом (D. Willard).
Сверхбыстрый цифровой бор [math]O(\log w)[/math] [math]O(\log w)[/math] [math]O(w)[/math] [math]O(\log w)[/math] [math]O(w)[/math] [math]O(n)[/math] Улучшеная версия структуры цифрового бора.

См. Также

Источники информации