Структура данных поиска
В информатике поисковая структура данных [ требуется ссылка ] — это любая структура данных , которая позволяет эффективно извлекать определенные элементы из набора элементов, например, определенную запись из базы данных .
Самая простая, самая общая и наименее эффективная структура поиска — это просто неупорядоченный последовательный список всех элементов. Поиск нужного элемента в таком списке методом линейного поиска неизбежно требует ряда операций, пропорциональных числу 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]
Эта таблица является лишь приблизительным резюме; для каждой структуры данных существуют особые ситуации и варианты, которые могут привести к различным затратам. Также две или более структур данных могут быть объединены для получения более низких затрат.
Сноски
- ^ ab Томас Х. Кормен; Чарльз Э. Лейзерсон; Рональд Л. Ривест (1990). Введение в алгоритмы . Колледж информационных наук и технологий в Пенсильванском государственном университете. ISBN 978-0-262-53091-0.
LIST-DELETE выполняется за время O (1), но если удалить элемент с заданным ключом, в худшем случае потребуется Θ(n) времени, поскольку сначала мы должны вызвать LIST-SEARCH.
- ^ ab Томас Х. Кормен; Чарльз Э. Лейзерсон; Рональд Л. Ривест (1990). Введение в алгоритмы . Колледж информационных наук и технологий в Пенсильванском государственном университете. ISBN 978-0-262-53091-0.
Существует два вида двоичных куч: max-heaps и min-heaps. В обоих видах значения в узлах удовлетворяют свойству кучи ... наибольший элемент в max-heap хранится в корне... Наименьший элемент в min-heap находится в корне... Операция HEAP-MAXIMUM возвращает максимальный элемент кучи за время Θ(1), просто возвращая значение A [1] в куче.
- ^ Аллен Шеррод (2007). Структуры данных и алгоритмы для разработчиков игр . Cengage Learning. ISBN 978-1-58450-663-8.
Вставка элемента в неупорядоченный массив не зависит ни от чего, кроме помещения нового элемента в конец списка. Это дает вставку в неупорядоченный массив O (1).
- ^ Томас Х. Кормен; Чарльз Э. Лейзерсон; Рональд Л. Ривест (1990). Введение в алгоритмы . Колледж информационных наук и технологий в Пенсильванском государственном университете. ISBN 978-0-262-53091-0.
- ^ "Алгоритм - временная сложность удаления в несортированном массиве".
Поиск элемента с заданным значением линейный. Поскольку массив в любом случае не сортируется, вы можете выполнить само удаление за константное время. Сначала переместите элемент, который вы хотите удалить, в конец массива, затем уменьшите размер массива на один элемент.
Смотрите также
