#compsci 

**Структуры данных** - способы расположения информации в адресном пространстве оперативной памяти или жёсткого диска, которые помогают составлять более эффективные [[алгоритм|алгоритмы]]

Речь идет о наборах элементов одинаковой природы

Основные примеры: вектор (массив), список, деревья, хеш-таблицы.

### Работа памяти
У данных в памяти есть адрес, по которому их можно найти.
Структуры данных описывают правила размещения набора однотипных данных в адресном пространстве и задают алгоритмы элементарных операций над этими наборами (например поиск по значению, добавление элемента, удаление элемента, замена элемента, и тд)

## Массив
**Массив** (или вектор, или [[Python Lists|список в Python]]) - простейшая структура данных.

Пусть надо разметить набор X из N объектов, требующих s байт памяти для каждого. Разместим их в памяти последовательно.
Зная адрес нулевого элемента (назовем его адрес массива) $\LARGE a_0$ , можно получить доступ к любому из элементов при знании индекса $\LARGE i$ этого элемента. Тогда адрес $\LARGE a_i$:
$$\LARGE a_i=a_0+is$$
Чтение или запись $\LARGE i$-го элемента массива имеет [[Вычислительная сложность|сложность]] O(1).

Поиск по значению в массиве в худшем случае имеет сложность O(N).

Операции вставки или удаления элемента из позиции $\LARGE i$ имеют сложность O(N) (при добавлении надо переписать все значения на соседнее положение вправо, а при удалении нужно переместить на освободившуюся следующий элемент и тд)

Добавление нового элемента перед нулевым элементом невозможно по соглашению, а добавление элемента после последнего тоже имеет сложность O(N) (адресное пространство перед первым элементом или после последнего может быть уже занято другими данными, т.е. надо переместить весь массив в новое, более просторное место)

Если мы отказываемся от необходимости хранить элементы в некотором заданном порядке, мы могли бы отсортировать такой массив, тогда поиск по значению в отсортированном массиве можно осуществлять за $\LARGE O(\log{N})$ операций методом [[Метод двоичного поиска|двоичного поиска]] (binary search) (похож на [[Метод половинного деления]])

## Список
**Список** (в Python - collections,deque) может быть **односвязным** или **двусвязным**

Общий принцип:
для каждого из N объектов в адресном пространстве выбирается своё индивидуальное местёо, достаточное для хранения этого объекта и адреса следующего объекта (односвязный), либо пары адресов, указывающий на предыдущий и следующий элементы

Адрес нулевого элемента начинается **адресом списка**.

Отличия от массива:
1) больше памяти нужно для хранения тех же данных
2) чтение или запись i-го элемента имеет сложность O(N)
3) поиск по значению в списке тоже имеет сложность O(N)
4) удаление элемента, а также вставка нового элемента до и после него, имеют сложность O(1)
5) пункт 4 верен для начала и конца списка

![[Pasted image 20260224125240.png]]

## Деревья
Дерево - односвязный ациклический [[Граф|граф]], одна из вершин которого назначена **корнем** (т.е. зафиксирована)

После фиксации корня некоторые вершины становятся **листьями** - тупиковыми вершинами при обходе от корня. 
Для каждого листа есть **глубина (высота) листа** - число вершин на пути от корня до этого листа
Максимальная глубина листа среди всех листьев - **глубина (высота) дерева**

Двоичные деревья - у каждого из узлов не более двух потомков.

Двоичные деревья просто представить в линейном адресном пространстве:
- каждый узел соответствует области памяти, где хранятся данные, приписанные к этому узлу, и дополнительно два адреса для поддеревьев
- адресом дерева считается адрес корня

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

Также есть двоичные деревья поиска:
![[Pasted image 20260228104342.png]]
![[Pasted image 20260228104419.png]]

В отличие от списков и массивов, в двоичным дереве любая коллекция хранится в определенном порядке, навязанном структурой данных (значение элемента определяет его порядок), т.е.:
операция чтения или записи $\LARGE i$-го элемента не существует для дерева поиска, так как не имеет смысла

Однако существует поиск элемента $\LARGE x'$ по значению в двоичном дереве поиска:
1) начинаем с корня $\LARGE x$
2) если $\LARGE x'=x$, то элемент найден
3) если $\LARGE x'<x$, то применяем поиск к левому поддереву
4) если $\LARGE x'>x$, то применяем поиск к правому поддереву

В худшем случае, когда элемент отсутсвует, сложность алгоритма поиска составит O(h), где $\LARGE h$ глубина дерева.

Вставка нового элемента осуществляется аналогичным образом: выполняется неудачный поиск и дописывание нового листа в качестве потомка финального листа. Сложность опять O(h)
Операция удаления в большинстве случаев также имеет сложность O(h)

### Сбалансированные деревья
Для сбалансированных деревьев глубина дерева $\LARGE h$ пропорциональна $\LARGE \log{N}$, где $\LARGE N$ число узлов дерева.

Для таких деревьев операция поиска имеет сложность $\LARGE O(\log{N})$

Сбалансированное двоичное дерево - такое двоичное дерево, у которого глубины левого и права поддеревьев для каждого узла различаются не более чем на единицу
![[Pasted image 20260228105859.png]]
НО: операции вставки и удаления портят балансировку дерева. Тогда либо нужно отказаться от модификации дерева, либо изменить эти деревья так, чтобы сохранить сбалансированность.

Пример последнего подхода являются **АВЛ-деревья** (Адельсон-Вельский и Ландис, 1962).

Метод такой:
1) в каждый узел дополнительно записываются **показатели сбалансированности** - разницу между высотами левого и правого поддеревьев, три значения (-1, 0, +1)
2) после вставки или удаления элемента выполняется обратный проход от листа к корню по ранее запомненному маршруту. В момент этого прохода для каждого узла последовательно определяется, как изменился показатель сбалансированности, и если он стал -2 или +2, то выполнить одну из четырех описанных операций балансировки, называемых **вращениями** и требующих константного времени.
Пример:
![[Pasted image 20260228110736.png]]

Таким образом, вставки и удаления в АВЛ-дереве, включая последующую перебалансировку, требуют O(h) операций

НО: можно ослабить требования балансировки, сохранив сложность в $\LARGE O(\log{N})$ операций удаления, вставки и поиска.
Пример: **красно-чёрные деревья** Гибаса и Седжвика, которые аналогичны АВЛ-деревьям, только вместо показателя сбалансированности цвет (красное или черное), с определенным требованиями

Для случайного двоичного дерева поиска средняя глубина тоже пропорциональна $\LARGE \log{N}$
Случайное дерево - дерево, в котором корень выбирается равновероятно, затем коллекция элементов разделяется на элементы, оказаывшиеся меньше коня (левое поддерево) и больше (правое поддерево), для которых операция повторяется.

Деревья часто используются в качестве **ассоциативного массива**, где данные $\LARGE x$ представляются в виде пары $\LARGE (k,v)$, где k - ключ, а v - значение. Для k определяется операция сравнения, и с помощью них строится дерева, а значения v просто дополнительно приписываются узлам.

Результат: зная ключ, можно отыскать значение легко, но зная лишь значение, отыскать ключ можно только полным перебором

Пример (ассоциативного массива!!): [[Python Dictionaries]]

### k-мерные деревья

Для элементов многомерного пространства используют $\LARGE k$-мерные деревья

Один из подходов (Бентли)
1) $\LARGE k$-мерное дерево двоичное
2) для заданной размерности пространства $\LARGE k$ все существующие уровни двоичного дерева пронумерованы циклически от 1 до $\LARGE k$ 
3) на каждом уровне сравнивается только компонента векторов, соответствующая циклическому номеру уровня: в случае плоскости в левом поддереве окажутся точки, которые находятся левее корневой точки, а в правом поддереве - правее. На следующем уровне два поддерева будут сформированы из точек, которые лежат выше или ниже точки корня.

В многомерном пространстве $\LARGE k$-мерные деревья позволяют эффективно выполнять операцию поиска элемента и операцию поиска ближайших соседей (сложность $\LARGE O(\log{N})$ в среднем)

Балансировка:
![[Pasted image 20260228123551.png]]
![[Pasted image 20260228123653.png]]

## Хеш-таблицы
Можно ли осуществить поиск по значению, вставку или удаление элемента за O(1)?

Есть только чтение и запись элемента массива по его индексу с O(1)


Упрощенный вариант: **таблица прямой адресации**
Пусть мы хотим хранить $\LARGE X \subset \mathbf{Z}_{\geq 0}$, тогда можно организовать массив, значениями которых являются 0 и 1 по принципу 0 если не в X, 1 если в X
Тогда для поиска элемента по значению $\LARGE x$ достаточно было бы обратиться к памяти по адресу $\LARGE a_0+i*1$, что есть O(1)
Аналогично с ассоциативным массивом: в элементе i таблицы прямой адресации будем хранить либо адрес строки с имененем абонента с номером телефона $\LARGE i$, либо признак отсутствия номера в телефонной книге

Недостатки таблицы прямой адресации:
1) неочевидно, как этот подход адаптировать для хранения, например, строк
2) способ может потребовать огромного количества памяти, порядка max{i}-min{i}, $\LARGE i \in X$


Эти недостатки можно преодолеть с помощью **[[Хеш-функции|хеш-функции]]**:
**Хеш-функция** - детерминированная функция $\LARGE i=h(x)$, которая любому $\LARGE x$ любой требуемой природы (целому числу, вектор, действительному числу, строке, тд) сопоставляет целочисленный индекс $\LARGE i$ в разумном интервале значений.
При  том для любого распрделения $\LARGE x$ соответствующее распределение $\LARGE i=h(x)$ должно быть как можно ближе к равномерному

Примеры хеш-функций:
![[Pasted image 20260228124646.png]]

Улучшаем таблицу прямой адресации - **хеш-таблица**:
1) зафиксируем некоторую хеш-функцию $\LARGE h(x)$ для интересующего нас типа элементов
2) зафиксируем заранее таблицу из $\LARGE M$ одинаковых по размеру ячеек, в которых хранитлся либо некоторый элемент $\LARGE x$, либо признак его отсутствия
3) договоримся, что будем хранить элемент со значением $\LARGE x$ только в ячейке с номером $\LARGE i'=h(x)$

Если хеш-функция $\LARGE h(x)$ принимает значения в интервале $\LARGE [0, 2^\omega]$, то удобно выбирать размер таблицы как степень двойки, тогда эффективность использования памяти будет выше всего

Сложность операции поиска, удаления и вставки элемента в хэш-таблицу по-прежнему составляет O(1)

Однако чаще всего хеш-функция неинъективна, и могут быть два варианта с одинаковым хешем - **коллизия**

Разрешение коллизицй методом цепочек:
![[Pasted image 20260228130751.png]]

Вероятность того, что из $\LARGE N$ чисел, равномерно распределенных от 0 до M невключительно хотя бы два совпадают:

![[Pasted image 20260228130900.png]]

Если мы выбираем количество ячеек таким образом, что $\LARGE M >> N$, то вероятность коллизии пренебрежимо мала, однако хеш-функция хоть и будет обеспечивать быстрый доступ, но с низкой эффективностью использования памяти, так как доля использованных ячеек составит $\LARGE \frac{N}{M} \rightarrow 0$.

На практике в результате вставок и удалений элементов количество хранимых записей M постоянно меняется, поэтому часто M подбирается динамически, чтобы обеспечить оптимальный баланс между скоростью работы и использованием памяти: в моменты, когда заполненность хеш-таблицы сильно меняется в ту или иную  сторону, происходит перебалансировка таблицы: создается новая таблица размером 2M или 0.5M с новой хеш-фукнцией. в которую перекладываются все элементы

Идеальная хеш-функция (таблица) взаимооднозначно отображает допустимое множество ключей в множество индексов