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