Структура данных поиска
В информатике — структура поисковых данных. [ нужна ссылка ] — это любая структура данных , которая позволяет эффективно извлекать определенные элементы из набора элементов, например определенную запись из базы данных .
Самая простая, общая и наименее эффективная структура поиска — это просто неупорядоченный последовательный список всех элементов. Нахождение искомого элемента в таком списке методом линейного поиска неизбежно требует ряда операций, пропорциональных числу n элементов, как в худшем, так и в среднем случае . Полезные структуры данных поиска позволяют ускорить поиск; однако они ограничены запросами определенного типа. Более того, поскольку стоимость построения таких структур как минимум пропорциональна n , они окупаются только в том случае, если необходимо выполнить несколько запросов к одной и той же базе данных (или к базе данных, которая мало меняется между запросами).
Статические структуры поиска предназначены для ответа на множество запросов в фиксированной базе данных; динамические структуры также позволяют вставлять, удалять или изменять элементы между последовательными запросами. В динамическом случае необходимо также учитывать стоимость исправления структуры поиска для учета изменений в базе данных.
Классификация
[ редактировать ]Самый простой вид запроса — найти запись, имеющую определенное поле ( ключ ), равное указанному значению v . Другими распространенными типами запросов являются «найти элемент с наименьшим (или наибольшим) значением ключа», «найти элемент с наибольшим значением ключа, не превышающим v », «найти все элементы со значениями ключей между указанными границами v min и v max ».
В некоторых базах данных значениями ключей могут быть точки в некотором многомерном пространстве . Например, ключом может быть географическое положение ( широта и долгота ) на Земле . В этом случае распространенными типами запросов являются «найти запись с ключом, ближайшим к данной точке v », или «найти все элементы, ключ которых находится на заданном расстоянии от v », или «найти все элементы в указанной области R». пространства».
Частым частным случаем последнего являются одновременные запросы диапазона по двум или более простым ключам, например «найти все записи о сотрудниках с зарплатой от 50 000 до 100 000, нанятых в период с 1995 по 2007 год».
Ключи по одному заказу
[ редактировать ]- Массив, если ключевые значения охватывают умеренно компактный интервал.
- Список с сортировкой по приоритету; см . линейный поиск
- Массив с ключевой сортировкой; см. двоичный поиск
- Самобалансирующееся двоичное дерево поиска
- Хэш-таблица
Нахождение наименьшего элемента
[ редактировать ]Асимптотический анализ наихудшего случая
[ редактировать ]В этой таблице асимптотическое обозначение O ( f ( n )) означает «непревышение некоторого фиксированного кратного f ( n ) в худшем случае».
| Структура данных | Вставлять | Удалить | Баланс | Получить по индексу | Поиск | Найти минимум | Найдите максимум | Использование пространства |
|---|---|---|---|---|---|---|---|---|
| Несортированный массив | О (1) (см. примечание) | О (1) (см. примечание) | Н/Д | О (1) | На ) | На ) | На ) | На ) |
| Сортированный массив | На ) | На ) | Н/Д | О (1) | О (логарифм n ) | О (1) | О (1) | На ) |
| Куча | О (1) | О (1) | На ) | На ) | ||||
| Очередь | О (1) | О (1) | На ) | На ) | ||||
| Несортированный связанный список | О (1) | О (1) [1] | Н/Д | На ) | На ) | На ) | На ) | На ) |
| Сортированный связанный список | На ) | О (1) [1] | Н/Д | На ) | На ) | О (1) | О (1) | На ) |
| Пропустить список | ||||||||
| Самобалансирующееся двоичное дерево поиска | О (логарифм n ) | О (логарифм n ) | О (логарифм n ) | Н/Д | О (логарифм n ) | О (логарифм n ) | О (логарифм n ) | На ) |
| Куча | О (логарифм n ) | О (логарифм n ) | О (логарифм n ) | Н/Д | На ) | O (1) для минимальной кучи O ( n ) для максимальной кучи [2] | O (1) для максимальной кучи O ( n ) для минимальной кучи [2] | На ) |
| Хэш-таблица | О (1) | О (1) | На ) | Н/Д | О (1) | На ) | На ) | На ) |
| Trie ( k = средняя длина ключа) | Хорошо ) | Хорошо ) | Н/Д | Хорошо ) | Хорошо ) | Хорошо ) | Хорошо ) | О ( к н ) |
| Декартово дерево | ||||||||
| B-дерево | О (логарифм n ) | О (логарифм n ) | О (логарифм n ) | Н/Д | О (логарифм n ) | О (логарифм n ) | О (логарифм n ) | На ) |
| Красно-черное дерево | О (логарифм n ) | О (логарифм n ) | О (логарифм n ) | На ) | ||||
| Распространение дерева | ||||||||
| АВЛ-дерево | О (логарифм n ) | |||||||
| кд дерево |
Примечание . Вставка в несортированный массив иногда обозначается как O ( n ) из-за предположения, что вставляемый элемент должен быть вставлен в одно конкретное место массива, что потребует сдвига всех последующих элементов на одну позицию. Однако в классическом массиве массив используется для хранения произвольных неотсортированных элементов, и, следовательно, точное положение любого данного элемента не имеет значения, а вставка осуществляется путем увеличения размера массива на 1 и сохранения элемента в конце. массива, что является операцией O (1). [3] [4] Аналогичным образом, операция удаления иногда обозначается как O ( n ) из-за предположения, что последующие элементы должны быть сдвинуты, но в классическом несортированном массиве порядок неважен (хотя элементы неявно упорядочены по времени вставки), поэтому удаление может выполняться путем замены удаляемого элемента на последний элемент массива и последующего уменьшения размера массива на 1, что является операцией O (1). [5]
Эта таблица представляет собой лишь приблизительное резюме; для каждой структуры данных существуют особые ситуации и варианты, которые могут привести к разным затратам. Также можно объединить две или более структуры данных для снижения затрат.
Сноски
[ редактировать ]- ^ Перейти обратно: а б Томас Х. Кормен; Чарльз Э. Лейзерсон; Рональд Л. Ривест (1990). Введение в алгоритмы . Колледж информационных наук и технологий Пенсильванского университета. ISBN 978-0-262-53091-0 .
LIST-DELETE выполняется за время O (1), но если удалить элемент с заданным ключом, в худшем случае потребуется время Θ(n), поскольку мы должны сначала вызвать LIST-SEARCH.
- ^ Перейти обратно: а б Томас Х. Кормен; Чарльз Э. Лейзерсон; Рональд Л. Ривест (1990). Введение в алгоритмы . Колледж информационных наук и технологий Пенсильванского университета. ISBN 978-0-262-53091-0 .
Существует два типа двоичных куч: максимальные кучи и минимальные кучи. В обоих типах значения в узлах удовлетворяют свойству кучи ... самый большой элемент в максимальной куче хранится в корне... Наименьший элемент в минимальной куче находится в корне... Операция HEAP -MAXIMUM возвращает максимальный элемент кучи за время Θ(1), просто возвращая значение A [1] в куче.
- ^ Аллен Шеррод (2007). Структуры данных и алгоритмы для разработчиков игр . Cengage Обучение. ISBN 978-1-58450-663-8 .
Вставка элемента в неупорядоченный массив не зависит ни от чего, кроме помещения нового элемента в конец списка. Это дает вставку в неупорядоченный массив O (1).
- ^ Томас Х. Кормен; Чарльз Э. Лейзерсон; Рональд Л. Ривест (1990). Введение в алгоритмы . Колледж информационных наук и технологий Пенсильванского университета. ISBN 978-0-262-53091-0 .
- ^ «Алгоритм — временная сложность удаления в несортированном массиве» .
Поиск элемента с заданным значением является линейным. Поскольку массив все равно не отсортирован, вы можете выполнить само удаление за постоянное время. Сначала поменяйте местами элемент, который хотите удалить, в конец массива, затем уменьшите размер массива на один элемент.