Структура данных поиска - Search data structure
В Информатика, а структура данных поиска[нужна цитата ] есть ли структура данных что позволяет эффективно извлекать определенные элементы из набор элементов, например, конкретный записывать из база данных.
Самая простая, самая общая и наименее эффективная структура поиска - это просто неупорядоченный последовательный список всех предметов. Находя нужный элемент в таком списке, линейный поиск метод, неизбежно требует количества операций, пропорциональных количеству п пунктов, в худший случай а также в средний случай. Полезные структуры данных поиска позволяют более быстрый поиск; однако они ограничены запросами определенного типа. Причем, поскольку стоимость строительства таких конструкций как минимум пропорциональна п, они окупаются только в том случае, если несколько запросов должны выполняться в одной и той же базе данных (или в базе данных, которая мало меняется между запросами).
Статический поисковые структуры предназначены для ответа на многие запросы по фиксированной базе данных; динамичный структуры также позволяют вставлять, удалять или изменять элементы между последовательными запросами. В динамическом случае необходимо также учитывать стоимость исправления структуры поиска для учета изменений в базе данных.
Классификация
Самый простой тип запроса - найти запись с определенным полем ( ключ) равный указанному значению v. Другие распространенные виды запросов: «найти элемент с наименьшим (или наибольшим) значением ключа», «найти элемент с наибольшим значением ключа, не превышающим v"," найти все элементы со значениями ключей между указанными границами vмин и vМаксимум".
В некоторых базах данных ключевые значения могут быть точками в некоторых многомерное пространство. Например, ключом может быть географическое положение (широта и долгота ) на земной шар. В этом случае общие типы запросов: найти запись с ключом, ближайшим к заданной точке v"или" найти все элементы, ключ которых находится на заданном расстоянии от v"или" найти все элементы в указанном регионе р пространства ».
Частым частным случаем последнего являются одновременные запросы диапазона по двум или более простым ключам, например «найти все записи о сотрудниках с зарплатой от 50 000 до 100 000, нанятых в период с 1995 по 2007 год».
Одноразовые ключи
- Множество если ключевые значения охватывают умеренно компактный интервал.
- Список с сортировкой по приоритету; видеть линейный поиск
- Массив с сортировкой по ключам; видеть бинарный поиск
- Самобалансирующееся двоичное дерево поиска
- Хеш-таблица
Поиск самого маленького элемента
Асимптотический амортизированный анализ наихудшего случая
В этой таблице асимптотический обозначение О(ж(п)) означает "не превышение некоторого фиксированного кратного ж(п) в худшем случае ".
| Структура данных | Вставлять | Удалить | Баланс | Получить по индексу | Поиск | Найдите минимум | Найдите максимум | Использование пространства |
|---|---|---|---|---|---|---|---|---|
| Несортированный множество | О(1) (смотрите примечание) | О(1) (смотрите примечание) | Нет данных | О(1) | О(п) | О(п) | О(п) | О(п) |
| Отсортированный массив | О(п) | О(п) | Нет данных | О(1) | О(бревноп) | О(1) | О(1) | О(п) |
| Куча | О(1) | О(1) | О(п) | О(п) | ||||
| Очередь | О(1) | О(1) | О(п) | О(п) | ||||
| Несортированный связанный список | О(1) | О(1)[1] | Нет данных | О(п) | О(п) | О(п) | О(п) | О(п) |
| Отсортированный связанный список | О(п) | О(1)[1] | Нет данных | О(п) | О(п) | О(1) | О(1) | О(п) |
| Пропустить список | ||||||||
| Самобалансирующееся двоичное дерево поиска | О(бревноп) | О(бревноп) | О(бревноп) | Нет данных | О(бревноп) | О(бревноп) | О(бревноп) | О(п) |
| Куча | О(бревноп) | О(бревноп) | О(бревноп) | Нет данных | О(п) | О(1) для мин-куча О(п) для max-heap[2] | О(1) для max-heap О(п) для мин-куча[2] | О(п) |
| Хеш-таблица | О(1) | О(1) | О(п) | Нет данных | О(1) | О(п) | О(п) | О(п) |
| Trie (k = средняя длина ключа) | О(k) | О(k) | Нет данных | О(k) | О(k) | О(k) | О(k) | О(k п) |
| Декартово дерево | ||||||||
| B-дерево | О(бревноп) | О(бревноп) | О(бревноп) | Нет данных | О(бревноп) | О(бревноп) | О(бревноп) | О(п) |
| Красно-черное дерево | ||||||||
| Splay tree | ||||||||
| AVL дерево | О(бревноп) | |||||||
| k-d дерево |
Примечание: Вставка в несортированный массив иногда цитируется как О(п) из-за предположения, что вставляемый элемент должен быть вставлен в одно конкретное место массива, что потребовало бы смещения всех последующих элементов на одну позицию. Однако в классическом массиве массив используется для хранения произвольных несортированных элементов, и, следовательно, точное положение любого заданного элемента не имеет значения, а вставка выполняется путем увеличения размера массива на 1 и сохранения элемента в конце массива, который является О(1) операция.[3][4] Аналогичным образом, операция удаления иногда цитируется как О(п) из-за предположения, что последующие элементы должны быть сдвинуты, но в классическом несортированном массиве порядок не важен (хотя элементы неявно упорядочиваются по времени вставки), поэтому удаление может быть выполнено путем замены удаляемого элемента последним элемент в массиве, а затем уменьшает размер массива на 1, что является О(1) операция.[5]
Эта таблица представляет собой лишь приблизительную сводку; для каждой структуры данных существуют особые ситуации и варианты, которые могут привести к разным затратам. Также можно объединить две или более структуры данных для снижения затрат.
Сноски
- ^ а б Кормен, Лейзерсон, Ривест. Введение в алгоритмы. Колледж информационных наук и технологий Пенсильванского университета. ISBN 9780262530910.
LIST-DELETE выполняется в О(1) время, но если удалить элемент с заданным ключом, в худшем случае потребуется Θ (n) времени, потому что мы должны сначала вызвать LIST-SEARCH.
CS1 maint: использует параметр авторов (связь) - ^ а б Кормен, Лейзерсон, Ривест. Введение в алгоритмы. Колледж информационных наук и технологий Пенсильванского университета. ISBN 9780262530910.
Есть два типа двоичных куч: max-heaps и min-heaps. В обоих случаях значения в узлах удовлетворяют куча собственности... самый большой элемент в максимальной куче хранится в корне ... Наименьший элемент в минимальной куче находится в корне ... Операция HEAP-MAXIMUM возвращает максимальный элемент кучи за Θ (1) раз просто вернув значение А[1] в куче.
CS1 maint: использует параметр авторов (связь) - ^ Аллен Шеррод (2007). Структуры данных и алгоритмы для разработчиков игр. Cengage Learning. ISBN 9781584506638.
Вставка элемента в неупорядоченный массив не зависит ни от чего, кроме помещения нового элемента в конец списка. Это дает вставку в неупорядоченный массив О(1).
- ^ Кормен, Лейзерсон, Ривест. Введение в алгоритмы. Колледж информационных наук и технологий Пенсильванского университета. ISBN 9780262530910.CS1 maint: использует параметр авторов (связь)
- ^ «Алгоритм - временная сложность удаления в несортированном массиве».
Поиск элемента с заданным значением является линейным. Поскольку массив все равно не сортируется, вы можете выполнить само удаление за постоянное время. Сначала переместите элемент, который вы хотите удалить, в конец массива, затем уменьшите размер массива на один элемент.