Поисковые структуры данных

Поисковая структура данных — любая структура данных реализующая эффективный поиск конкретных элементов множества, например, конкретной записи в базе данных.

Простейший, наиболее общий, но менее эффективный поисковой структурой является простая неупорядоченный последовательная всех элементов. Расположив элементы в такой список, неизбежно возникнет ряд операций, которые потребуют линейного времени, в худшем случае, а также в средней случае. Используемые в реальной жизни поисковые структуры данных позволяют совершать операции более быстро, однако они ограничены запросами некоторого конкретного вида. Кроме того, поскольку стоимость построение таких структур пропорциональна [math]n[/math], их построение окупится, даже если поступает лишь несколько запросов.

Тип

Статические поисковые структуры данных (англ. Online search structures) предназначены для ответа на запросы на фиксированной базе данных; Динамические поисковые структуры (англ. Offline search structures) также позволяют вставки, удаления или модификации элементов между последовательными запросами. В динамическом случае, необходимо также учитывать стоимость изменения структуры данных. Любую динамическую структуру данных можно сделать статической, если запретить вставку и удаление. Также если множество ключей известно, то можно его заранее упорядочить так, чтобы избежать худших случаев в поисках в структурах данных.

Время работы

Эту классификацию обычно считают самой важной. Оценивают худшее время алгоритма, среднее и лучшее для каждой операции. Лучшее время — минимальное время работы алгоритма на каком-либо наборе. Худшее время — наибольшее время.

Используемая память

Параметр структуры данных, показывающий, сколько памяти ей требуется. Обычно затраты составляют [math]O(n)[/math].

Сравнение структур данных

Сравним эффективность поисковых структур данных для реализации интерфейса упорядоченного множества. Время работы методов [math]Predecessor[/math] и [math]Successor[/math] совпадает с временем работы [math]Search[/math].

[math]n[/math] — количество хранимых чисел, каждое из которых представляется с помощью [math]w[/math] битов.

	Insert		Delete		Search		Память		Описание
	Среднее	Худшее	Среднее	Худшее	Среднее	Худшее	Среднее	Худшее
	Динамические структуры данных
Неотсортированный массив	[math]O(1)[/math]	[math]O(n)[/math]	[math]O(1)[/math]	[math]O(n)[/math]	[math]O(n)[/math]		[math]O(n)[/math]		Наивная реализация, использующая динамический массив. Добавление происходит в конец массива, а для поиска элемента просто проходим по всему массиву.
Отсортированный массив	[math]O(n)[/math]		[math]O(n)[/math]		[math]O(\log n)[/math]		[math]O(n)[/math]		То же самое, но теперь массив отсортирован. Поиск ускоряется за счёт возможности применить двоичный поиск. Вставка замедляется из-за необходимости поддерживать инвариант отсортированности.
Неотсортированный список	[math]O(1)[/math]		[math]O(1)[/math]		[math]O(n)[/math]		[math]O(n)[/math]		Аналогично массиву, но храним данные в списке. Можно хранить дополнительную информацию о вершинах, что позволит ускорить время работы операции delete.
Отсортированный список	[math]O(n)[/math]		[math]O(1)[/math]		[math]O(n)[/math]		[math]O(n)[/math]
Дерево поиска, наивная реализация	[math]O(\log n)[/math]	[math]O(n)[/math]	[math]O(\log n)[/math]	[math]O(n)[/math]	[math]O(\log n)[/math]	[math]O(n)[/math]	[math]O(n)[/math]		Бинарное дерево поиска обладает следующим свойством: если [math]x[/math] — узел бинарного дерева с ключом [math]k[/math], то все узлы в левом поддереве должны иметь ключи, меньшие [math]k[/math], а в правом поддереве большие [math]k[/math].
Рандомизированное бинарное дерево поиска	[math]O(\log n)[/math]	[math]O(n)[/math]	[math]O(\log n)[/math]	[math]O(n)[/math]	[math]O(\log n)[/math]	[math]O(n)[/math]	[math]O(n)[/math]		Вариант двоисного дерево поиска с добавлением инвариата "случайности". Что дает возможность того, что математическое ожидание глубины дерева будет небольшим.
АВЛ-дерево	[math]O(\log n)[/math]		[math]O(\log n)[/math]		[math]O(\log n)[/math]		[math]O(n)[/math]		Сбалансированное двоичное дерево поиска, в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на [math]1[/math].
2-3 дерево	[math]O(\log n)[/math]		[math]O(\log n)[/math]		[math]O(\log n)[/math]		[math]O(n)[/math]		Структура данных, представляющая собой сбалансированное дерево поиска, такое что из каждого узла может выходить две или три ветви и глубина всех листьев одинакова. Является частным случаем B+ дерева.
B-дерево	[math]O(\log n)[/math]		[math]O(\log n)[/math]		[math]O(\log n)[/math]		[math]O(n)[/math]		Cильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за [math]O(\log n)[/math]. B-дерево с [math]n[/math] узлами имеет высоту [math]O(\log n)[/math]. Количество детей узлов может быть от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время [math]O(\log n)[/math]
Красно-черное дерево	[math]O(\log n)[/math]		[math]O(\log n)[/math]		[math]O(\log n)[/math]		[math]O(n)[/math]		Сбалансированное двоичное дерево поиска, в котором баланс осуществляется на основе "цвета" узла дерева, который принимает только два значения: "красный" (англ. red) и "чёрный" (англ. black). При этом все листья дерева являются фиктивными и не содержат данных, но относятся к дереву и являются чёрными.
Декартово дерево	[math]O(\log n)[/math]	[math]O(n)[/math]	[math]O(\log n)[/math]	[math]O(n)[/math]	[math]O(\log n)[/math]	[math]O(n)[/math]	[math]O(n)[/math]		Бинарное дерево, в узлах которого хранится пары [math] (x,y) [/math], где [math]x[/math] — это ключ, а [math]y[/math] — это приоритет. Также оно является двоичным деревом поиска по [math]x[/math] и пирамидой по [math]y[/math]. Предполагая, что все [math]x[/math] и все [math]y[/math] являются различными, получаем, что если некоторый элемент дерева содержит [math](x_0,y_0)[/math], то у всех элементов в левом поддереве [math]x \lt x_0[/math], у всех элементов в правом поддереве [math] x \gt x_0[/math], а также и в левом, и в правом поддереве имеем: [math] y \lt y_0[/math].
Splay-дерево	[math]O(\log n)[/math]	[math]O(n)[/math]	[math]O(\log n)[/math]	[math]O(n)[/math]	[math]O(\log n)[/math]	[math]O(n)[/math]	[math]O(n)[/math]		Двоичное дерево поиска. Оно позволяет находить быстрее те данные, которые использовались недавно, за счёт перемещения к корню (англ. Move to root). Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в 1983 году.
Дерево ван Эмде Боаса	[math]O(\log w)[/math]		[math]O(\log w)[/math]		[math]O(\log w)[/math]		[math]O(2^w)[/math]		Cтруктура данных, представляющая собой дерево поиска, позволяющее хранить целые неотрицательные числа в интервале [math][0;2^w)[/math] и осуществлять над ними все соответствующие дереву поиска операции. Проще говоря, данная структура позволяет хранить [math]w[/math]-битные числа. Особенностью этой структуры является то, что все операции выполняются за [math]O(\log w)[/math], что асимптотически лучше, чем [math]O(\log n)[/math] в большинстве других деревьев поиска, где [math]n[/math] — количество элементов в дереве.
Список с пропусками	[math]O(\log n)[/math]	[math]O(n)[/math]	[math]O(\log n)[/math]	[math]O(n)[/math]	[math]O(\log n)[/math]	[math]O(n)[/math]	[math]O(n)[/math]		Вероятностная структура данных, основанная на нескольких отсортированных односвязных списках. Отсортированный связный список является простейшей структурой с временем поиска [math]\Theta(n)[/math]. Добавление дополнительных уровней, обеспечивающих быстрый доступ через несколько элементов, помогает улучшить асимптотику до [math]\Theta(\log(n))[/math]
Fusion tree	[math]O(\log_{w} n)[/math]		[math]O(\log_{w} n)[/math]		[math]O(\log_{w} n)[/math]		[math]O(n)[/math]		Дерево поиска, позволяющее хранить [math]n[/math] [math]w[/math]-битных чисел, используя [math]O(n)[/math] памяти, и выполнять операции поиска за время [math]O(\log_{w} n)[/math]. Эта структура данных была впервые предложена в 1990 году М. Фредманом (M. Fredman) и Д. Уиллардом (D. Willard).
Цифровой бор	[math]O(w)[/math]		[math]O(w)[/math]		[math]O(w)[/math]		[math]O(n \cdot w)[/math]		Бор, в котором в качестве строк используются двоичные записи чисел, включая ведущие нули. Таким образом он имеет глубину [math]w[/math].
Быстрый цифровой бор	[math]O(w)[/math]		[math]O(w)[/math]		[math]O(\log w)[/math]		[math]O(n \cdot w)[/math]		Улучшеная версия структуры цифрового бора.
Сверхбыстрый цифровой бор	[math]O(\log w)[/math]	[math]O(w)[/math]	[math]O(\log w)[/math]	[math]O(w)[/math]	[math]O(\log w)[/math]		[math]O(n)[/math]		Улучшеная версия структуры быстрого цифрового бора.
	Статические структуры данных
Tango-дерево	-		-		[math]O(\log \log n)[/math]		[math]O(n)[/math]		Двоичное дерево поиска, которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и Михаи Патраску в 2004 году. Не поддерживает операции вставки и удаления, но перестраивается по ходу поисковых запросов, чтобы отвечать на них как можно оптимальней. Это лучшая известная реализация на данный момент.

См. также

• Сортировка
• Поиск подстроки в строке
• Приоритетные кучи

Источники информации

• Wikidedia — Search data structure
• Habrahabr — Знай сложности алгоритмов