Изменения

! colspan="2" | Search

! colspan="2" | Память

! rowspan="2" | Описание

|-

! style="background: #ddffdd;" | Среднее

! style="background: #ffdddd;" | Худшее

|-

| Неотсортированный массив

| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>

| align="center" | Наивная реализация, использующая [[Динамический массив|динамический массив]]. Добавление происходит в конец массива, а для поиска элемента просто проходим по всему массиву.

|-

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>

| align="center" | То же самое, но теперь массив отсортирован. Поиск ускоряется за счёт возможности применить [[Целочисленный двоичный поиск|двоичный поиск]]. Вставка замедляется из-за необходимости поддерживать инвариант отсортированности.

|-

| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(n)</tex>

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>

| align="center" rowspan="2" | Аналогично массиву, но храним данные в [[Список|списке]]. Можно хранить дополнительную информацию о вершинах, что позволит ускорить время работы операции delete.

|-

| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>

| align="center" | Бинарное дерево поиска обладает следующим свойством: если <tex>x</tex> {{---}} узел бинарного дерева с ключом <tex>k</tex>, то все узлы в левом поддереве должны иметь ключи, меньшие <tex>k</tex>, а в правом поддереве большие <tex>k</tex>.

|-

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>

| align="center" | Сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на <tex>1</tex>.

|-

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>

| align="center" | Структура данных, представляющая собой сбалансированное дерево поиска, такое что из каждого узла может выходить две или три ветви и глубина всех листьев одинакова. Является частным случаем [[B-дерево#B.2B-.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D0.BE|B+ дерева]].

|-

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>

| align="center" | Cильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за <tex>O(\log n)</tex>. B-дерево с <tex>n</tex> узлами имеет высоту <tex>O(\log n)</tex>. Количество детей узлов может быть от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время <tex>O(\log n)</tex>

|-

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log n)</tex>

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>

| align="center" | Сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором баланс осуществляется на основе "цвета" узла дерева, который принимает только два значения: "красный" (англ. ''red'') и "чёрный" (англ. ''black''). При этом все листья дерева являются фиктивными и не содержат данных, но относятся к дереву и являются чёрными.

|-

| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>

| align="center" | Бинарное дерево, в узлах которого хранится пары <tex> (x,y) </tex>, где <tex>x</tex> {{---}} это ключ, а <tex>y</tex> {{---}} это приоритет. Также оно является [[Дерево поиска, наивная реализация|двоичным деревом поиска]] по <tex>x</tex> и [[Двоичная куча|пирамидой]] по <tex>y</tex>. Предполагая, что все <tex>x</tex> и все <tex>y</tex> являются различными, получаем, что если некоторый элемент дерева содержит <tex>(x_0,y_0)</tex>, то у всех элементов в левом поддереве <tex>x < x_0</tex>, у всех элементов в правом поддереве <tex> x > x_0</tex>, а также и в левом, и в правом поддереве имеем: <tex> y < y_0</tex>.

|-

| align="center" style="background: #ffdddd;" | <tex>O(n)</tex>

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>

| align="center" | [[Дерево поиска, наивная реализация|Двоичное дерево поиска]]. Оно позволяет находить быстрее те данные, которые использовались недавно, за счёт '''перемещения к корню''' (англ. ''Move to root''). Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в 1983 году.

|-

|[[Дерево ван Эмде Боаса]]

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>

| colspan="2" align="center" style="background: #ffdddd;" | <tex>O(2^w)</tex>

| align="center" | Cтруктура данных, представляющая собой [[Дерево поиска, наивная реализация|дерево поиска]], позволяющее хранить целые неотрицательные числа в интервале <tex>[0;2^w)</tex> и осуществлять над ними все соответствующие дереву поиска операции. Проще говоря, данная структура позволяет хранить <tex>w</tex>-битные числа.

Особенностью этой структуры является то, что все операции выполняются за <tex>O(\log w)</tex>, что асимптотически лучше, чем <tex>O(\log n)</tex> в большинстве других деревьев поиска, где <tex>n</tex> {{---}} количество элементов в дереве.

| align="center" style="background: #ffffdd;" | <tex>O(n)</tex>

| align="center" style="background: #ffdddd;" | <tex>O(n \log n)</tex>

| align="center" | Вероятностная структура данных, основанная на нескольких отсортированных односвязных списках.

Отсортированный связный список является простейшей структурой с временем поиска <tex>\Theta(n)</tex>. Добавление дополнительных уровней, обеспечивающих быстрый доступ через несколько элементов, помогает улучшить асимптотику до <tex>\Theta(\log(n))</tex>

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log_{w} n)</tex>

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>

| align="center" | Дерево поиска, позволяющее хранить <tex>n</tex> <tex>w</tex>-битных чисел, используя <tex>O(n)</tex> памяти, и выполнять операции поиска за время <tex>O(\log_{w} n)</tex>. Эта структура данных была впервые предложена в 1990 году М. Фредманом (M. Fredman) и Д. Уиллардом (D. Willard).

|-

| align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>

| align="center" style="background: #ffdddd;" | <tex>O(w)</tex>

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(\log w)</tex>

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>

|}

*[[:Сортировка|Сортировка]]