В информатике структура данных поиска [ нужна ссылка ] — это любая структура данных , которая позволяет эффективно извлекать определенные элементы из набора элементов, например конкретную запись из базы данных .
Самая простая, общая и наименее эффективная структура поиска — это просто неупорядоченный последовательный список всех элементов. Нахождение искомого элемента в таком списке методом линейного поиска неизбежно требует ряда операций, пропорциональных числу n элементов, как в худшем, так и в среднем случае . Полезные структуры данных поиска позволяют ускорить поиск; однако они ограничены запросами определенного типа. Более того, поскольку стоимость построения таких структур как минимум пропорциональна n , они окупаются только в том случае, если необходимо выполнить несколько запросов к одной и той же базе данных (или к базе данных, которая мало меняется между запросами).
Статические структуры поиска предназначены для ответа на множество запросов в фиксированной базе данных; динамические структуры также позволяют вставлять, удалять или изменять элементы между последовательными запросами. В динамическом случае необходимо также учитывать стоимость исправления структуры поиска для учета изменений в базе данных.
Самый простой вид запроса — найти запись, имеющую определенное поле (ключ ) , равное указанному значению v . Другими распространенными типами запросов являются «найти элемент с наименьшим (или наибольшим) значением ключа», «найти элемент с наибольшим значением ключа, не превышающим v », «найти все элементы со значениями ключей между указанными границами v min и v max ».
В некоторых базах данных значениями ключей могут быть точки в некотором многомерном пространстве . Например, ключом может быть географическое положение ( широта и долгота ) на Земле . В этом случае распространенными типами запросов являются «найти запись с ключом, ближайшим к данной точке v », или «найти все элементы, ключ которых находится на заданном расстоянии от v », или «найти все элементы в указанной области R» . пространства».
Частым частным случаем последнего являются одновременные запросы диапазона по двум или более простым ключам, например «найти все записи о сотрудниках с зарплатой от 50 000 до 100 000, нанятых в период с 1995 по 2007 год».
В этой таблице асимптотическое обозначение O ( f ( n )) означает «непревышение некоторого фиксированного кратного f ( n ) в худшем случае».
Примечание . Вставка в несортированный массив иногда обозначается как O ( n ) из-за предположения, что вставляемый элемент должен быть вставлен в одно конкретное место массива, что потребует сдвига всех последующих элементов на одну позицию. Однако в классическом массиве массив используется для хранения произвольных несортированных элементов, и, следовательно, точное положение любого данного элемента не имеет значения, а вставка осуществляется путем увеличения размера массива на 1 и сохранения элемента в конце. массива, что является операцией O (1). [3] [4] Аналогично, операция удаления иногда обозначается как O ( n ) из-за предположения, что последующие элементы должны быть сдвинуты, но в классическом несортированном массиве порядок неважен (хотя элементы неявно упорядочиваются с помощью вставки- time), поэтому удаление можно выполнить, заменив удаляемый элемент на последний элемент массива и затем уменьшив размер массива на 1, что является операцией O (1). [5]
Эта таблица представляет собой лишь приблизительное резюме; для каждой структуры данных существуют особые ситуации и варианты, которые могут привести к разным затратам. Также можно объединить две или более структуры данных для снижения затрат.
LIST-DELETE выполняется за время O (1), но если удалить элемент с заданным ключом, в худшем случае потребуется время Θ(n), поскольку мы должны сначала вызвать LIST-SEARCH.
Существует два типа двоичных куч: максимальные кучи и минимальные кучи. В обоих типах значения в узлах удовлетворяют свойству кучи ... самый большой элемент в максимальной куче хранится в корне... Наименьший элемент в минимальной куче находится в корне... Операция HEAP -MAXIMUM возвращает максимальный элемент кучи за время Θ(1), просто возвращая значение A [1] в куче.
Вставка элемента в неупорядоченный массив не зависит ни от чего, кроме помещения нового элемента в конец списка. Это дает вставку в неупорядоченный массив O (1).
Поиск элемента с заданным значением является линейным. Поскольку массив все равно не отсортирован, вы можете выполнить само удаление за постоянное время. Сначала поменяйте местами элемент, который хотите удалить, в конец массива, затем уменьшите размер массива на один элемент.