Линейный массив

• возможно, простейшая нетривиальная структура данных
• представляет из себя непрерывный участок памяти размера \(N\cdot |x|\), где \(N\) – число элементов массива, \(|x|\) – объём памяти, используемый для хранения одного элемента.

• Доступ к элементу – \(\mathcal O(1).\)
• Добавление элемента – \(\mathcal O(N).\)
• Удаление элемента – в общем случае \(\mathcal O(N).\)
• Поиск элемента – \(\mathcal O(N).\)

Односвязный список

• набор элементов, каждый из которых имеет указатель на следующий элемент
• Последний элемент указывает на некорректный адрес памяти (обычно NULL)
• Элементы могут быть расположены в памяти произвольным образом.
• В качестве “списка” хранится указатель на первый элемент.

Операции:

• Доступ – \(\mathcal O(N).\)
• Добавление после данного или в начало – \(\mathcal O(1),\)
• Удаление элемента – \(\mathcal O(1),\) если известен предыдущий элемент. В противном случае – \(\mathcal O(N).\)
• Поиск – \(\mathcal O(N).\)

Двусвязный список

• Каждый элемент содержит также указатель на предыдущий элемент
• удаление данного элемента безусловно имеет сложность \(\mathcal O(1),\) и возможен проход по списку как в прямом, так и в обратном направлении.

Дерево

• древовидная структура – набор связанных узлов
• Можно рассматривать как обобщение идеи связанного списка
• у одного элемента (узла), может быть несколько “следующих” (дочерних)
• дерево является ациклическим направленным графом

• у узла дерева может быть произвольное число дочерних. Такие деревья иногда называют “розовыми”.
• Выделяют также бинарные/двоичные деревья
• Узлы, не имеющие дочерних, называют “листьями”. Узел, не имеющий родительских называют корневым.
• может быть представлено различным образом
  • элементы с указателями на дочерние
  • в виде массива

Стек

• магазинная память
• реализует дисциплину доступа к данным “LIFO” (“последний на входе – первый на выходе”)
• элементы в стеке ведут себя как патроны в магазине – их можно добавлять “на вершину”, можно удалять “с вершины”, можно читать элемент “на вершине”.
• может быть реализован как на основе массива, так и на основе односвязного списка.
• Добавление, удаление, чтение элемента на вершине стека имеет сложность \(\mathcal O(1).\)

Очередь

• реализует дисциплину доступа к данным “FIFO” (“первый на входе – первый на выходе”)
• может быть реализована на основе массива (в варианте кольцевого буфера) или на основе односвязного списка

• на основе односвязного списка, новые элементы добавляются в конец списка, а удаляются из начала.
• на основе массива, используется два указателя на начало и конец очереди. Добавление элемента смещает указатель на конец очереди, удаление элемента смещает указатель на начало очереди. Таким образом оба указателя смещаются в направлении конца массива. Если один из указателей выходит за границы массива, он перемещается в начало. Такой вариант имеет жёстко ограниченную максимальную длину очереди.

• Добавление, удаление, чтение текущего элемента имеет сложность \(\mathcal O(1).\)
• очередь можно реализовать при помощи двух стеков, однако удаление элемента при такой реализации в худшем случае имеет сложность \(\mathcal O(N).\)

Куча

• дерево, удовлетворяющее свойству кучи: дочерние узлы в каком-то смысле не больше родительских
• Наибольший элемент всегда является корневым узлом, поэтому такие кучи называют max-кучами. Также есть симметричное понятие min-кучи.

Операции:

• найти максимум или найти минимум: найти максимальный элемент в max-куче или минимальный элемент в min-куче, соответственно
• удалить максимум или удалить минимум: удалить корневой узел в max- или min-куче, соответственно
• добавить: добавление нового узла в кучу.
• слияние: соединение двух куч с целью создания новой кучи, содержащей все элементы обеих исходных.

• существуют различные варианты с различной сложностью

• рассмотрим двоичную кучу

• является двоичным деревом, обладающим свойством кучи, и дополнительно обладает свойствами:

  1. Глубина всех листьев (расстояние до корня) отличается не более чем на 1.
  2. Последний слой заполняется слева направо без пропусков.

• часто представляется массивом, в котором корень находится на позиции с индексом \(i\), а дочерние узлы (при нумерации с \(0\)) – на позициях \(2i+1\) и \(2i+2.\) В таком случае дополнительные свойства соблюдаются “автоматически”.

• найти корень: \(\mathcal O(1)\)
• удалить корень: \(\mathcal O(\log N)\)
• добавить: \(\mathcal O(\log N)\)
• слияние: \(\mathcal O(N)\)

Очередь с приоритетом

• вариация на тему очереди
• у элементов есть “приоритет”
• сперва из очереди выходят элементы с более высоким приоритетом
• можно реализовать на основе массива или списка
• тогда добавление/удаление элементов за \(\mathcal O(N)\)
• Обычно – на основе кучи, операции за \(\mathcal O(\log N)\) или даже \(\mathcal O(1)\) в среднем (в зависимости от типа кучи)

Ассоциативный массив (словарь)

• map, таблица символов, словарь
• набор пар ключ-значение, где ключ и значение – произвольные типы данных
• обобщение обычного массива
• “индексом” могут выступать любые данные
• два основных подхода к реализации словарей:
  • на основе упорядоченных двоичных деревьев (деревьев поиска)
  • на основе хэш-таблиц

Хэш-таблица

• Добавление/удаление элементов за \(\mathcal O(1),\)
• поиск по ключу в среднем при достаточно большом \(K\) – \(\mathcal O(1),\) в худшем случае \(\mathcal O(N).\)
• эффективность чувствительна к выбору функции \(h:\) хорошая функция \(h\) имеет равномерное распределение значений по пространству возможных ключей (аргументов).
• хэш-функция каким-то образом “перемешивает” данные ключа для получения равномерного распределения

• совпадение \(h(k_1)\) и \(h(k_2)\) при \(k_1\neq k_2\) называется коллизией. Коллизий стараются избежать.
• Метрика – фактор загрузки \(α=\frac{N}{K}\).
• С ростом фактора загрузки, работа замедляется.
• Практические реализации часто перестраивают хэш-таблицу с увеличенным \(K\) при достижении некоторого заранее определённого \(α.\)

Дерево поиска

• двоичное дерево
• у каждого элемента “левые” потомки строго меньше данного, “правые” – не меньше данного.

• Поиск элемента за \(O(D),\)
• \(D\) – глубина дерева

• \(D = \mathcal O(\log N),\) в лучшем случае, если дерево “сбалансировано”, т.е. дочерних элементов “слева” от каждого элемента примерно столько же, сколько “справа”, в худшем – \(D = O(N),\) если дерево по сути развёрнуто в список.

• Практически, обычно используют самобалансирующиеся алгоритмы деревьев поиска, в частности АВЛ-дерево, красно-чёрное дерево.