Алгоритмы и структуры данных

Это ужасно! Я попытался собрать всю нужную информацию и ссылки в один файлик. Надеюсь, это будет хоть сколько-нибудь полезно. За точность не отвечаю, хотя я и пытался проверять. Были использованы следующие материалы и инструменты: чей-то украденный конспект (спасибо огромное этому человеку), информация из книги Кормена, старый файлик с ответами, Gemini-1.5-Pro.

Плейлист на YouTube с записями (почти) всех лекций 2024 года: https://www.youtube.com/playlist?list=PL8bFx8PltE4MSAk_SaW_MSnpVO91Cw-a1. Ссылки на видео с лекций ниже приведены с учетом таймкодов (но я это не доделал).

Книга Кормена c поиском: https://disk.yandex.ru/d/6PhppDCEL-5M0g

Задания с ответами в самом конце!!!

Перед использованием просьба провести фактчекинг

:)

PDF-версия: ADS.pdf; исходник на markdown: АСД.md

Программа курса

1. Основы анализа алгоритмов. Асимптотический анализ верхней и средней оценок сложности алгоритмов; сравнение наилучших, средних и наихудших оценок; O-, o-, ω- и θ-нотации; эмпирические измерения эффективности алгоритмов; накладные расходы алгоритмов по времени и памяти.

2. Рекуррентные соотношения и анализ рекурсивных алгоритмов. Определение, методы подстановки, итераций, деревья рекурсии. Основная теорема о рекуррентных соотношениях.

3. Динамические структуры данных. Линейные списки. Деревья: двоичные, деревья поиска, ветвящиеся деревья. Способы представления. Сбалансированные деревья: AVL-деревья, B-деревья, Красно-черные деревья, идеально сбалансированное дерево. Сравнение стоимости операций – асимптотические и эмпирические оценки.

4. Амортизационный анализ. (Помнить, зачем это надо). Учётные стоимости операций, использование при оценке времени работы алгоритмов. Методы группировки, предоплаты, потенциалов. Требования к потенциальной функции. Системы непересекающихся множеств. Основные операции, оценка амортизированной стоимости операций.

5. Графы. Представление графов – матрица смежности, списки смежности. Стратегии поиска в ширину, в глубину. Алгоритмы Дейкстры, Крускала, Прима. Топологическая сортировка. Алгоритм поиска сильно связных компонент.

6. Хэш-функции, хэш-таблицы. Открытая адресация, таблицы на основе цепочек. Базовые виды хеш-функций. Проблемы кластеризации, удаления элементов. Реализация структуры данных «словарь» на основе хэш-таблицы. Хопскотч, Робин-Гуд, двухвыборное (не то же, что и двойное!!), кукушкино хеширование.

7. Кучи. Двоичные кучи, сортировка с помощью двоичной кучи, оценка эффективности.

8. Стратегии переборных алгоритмов. Полный перебор, метод ветвей и границ на примере задачи коммивояжера.

9. Динамическое программирование. Признаки применимости, общая стратегия. Стратегии «сверху вниз» (используя механизм мемоизации) и «снизу вверх». Алгоритм перемножения матриц, поиск наибольшей общей подпоследовательности, задача о рюкзаке.

10. Жадные алгоритмы. Признаки применимости жадных алгоритмов, задача о рюкзаке (непрерывный варианты).

11. Алгоритмы поиска подстрок. «Наивный» алгоритм, алгоритмы РабинаКарпа, Кнута-Морриса-Пратта, Бойера-Мура (общая идея). Поиск подстрок с помощью конечных автоматов.

Примечания: в алгоритмах знать оценки, сильные слабые стороны, при каких сценариях выгоднее; + биноминальные деревья и кучи, фиббоначиевы (представление о них) + сортировка подсчётом.

1. Основы анализа алгоритмов

Анализ алгоритмов — это процесс определения количества ресурсов, необходимых для выполнения алгоритма. Обычно оценивается время выполнения, но также могут быть рассмотрены и другие ресурсы, такие как память, пропускная способность сети или необходимое аппаратное обеспечение.

Асимптотический анализ

Асимптотический анализ фокусируется на поведении алгоритма при увеличении размера входных данных до бесконечности. Он позволяет абстрагироваться от деталей реализации и аппаратного обеспечения, сосредоточившись на порядке роста времени выполнения.

Оценка сложности алгоритмов

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

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

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

Сравнение оценок сложности

• Наилучший случай часто неинформативен, так как редко встречается на практике.

• Наихудший случай гарантирует, что алгоритм не будет работать дольше определенного времени, но может быть пессимистичным.

• Средний случай более реалистичен, но его анализ сложнее и требует знания о распределении входных данных.

Асимптотические обозначения

В лекциях: https://youtu.be/Ju2tp7S-jfc?si=ZrUFi4eUqWcCT_Jd&t=1594

Нотация Бахмана–Ландау:

• O-нотация (О-большое): Дает верхнюю границу времени выполнения. Запись $f(n)=O(g(n))$$f(n) = O(g(n))$ означает, что существует константа $c>0$$c > 0$ и число $n_0$$n_0$, такие, что $0\le f(n)\le cg(n)$$0 ≤ f(n) ≤ cg(n)$ для всех $n\ge n_0$$n ≥ n_0$. Неформально: $f\le g$$f \le g$

• Ω-нотация (Омега-большое): Дает нижнюю границу времени выполнения. Запись $f(n)=\Omega (g(n))$$f(n) = Ω(g(n))$ означает, что существует константа $c>0$$c > 0$ и число $n_0$$n_0$, такие, что $0\le cg(n)\le f(n)$$0 ≤ cg(n) ≤ f(n)$ для всех $n\ge n_0$$n ≥ n_0$. Неформально: $f=g$$f = g$

• Θ-нотация (Тета-большое): Дает асимптотически точную оценку времени выполнения. Запись $f(n)=\Theta (g(n))$$f(n) = Θ(g(n))$ означает, что $f(n)=O(g(n))$$f(n) = O(g(n))$ и $f(n)=\Omega (g(n))$$f(n) = Ω(g(n))$. Неформально: $f\ge g$$f \ge g$

• o-нотация (о-малое): Указывает, что функция $f(n)$$f(n)$ растет строго медленнее, чем $g(n)$$g(n)$. Запись $f(n)=o(g(n))$$f(n) = o(g(n))$ означает, что для любой константы $c>0$$c > 0$ существует число $n_0$$n_0$, такое, что $0\le f(n)<cg(n)$$0 ≤ f(n) < cg(n)$ для всех $n\ge n_0$$n ≥ n_0$. Неформально: $f<g$$f < g$

• ω-нотация (омега-малое): Указывает, что функция $f(n)$$f(n)$ растет строго быстрее, чем $g(n)$$g(n)$. Запись $f(n)=\omega (g(n))$$f(n) = ω(g(n))$ означает, что для любой константы $c>0$$c > 0$ существует число $n_0$$n_0$, такое, что $0\le cg(n)<f(n)$$0 ≤ cg(n) < f(n)$ для всех $n\ge n_0$$n ≥ n_0$. Неформально: $f>g$$f > g$

Замечания!

• Любой логарифм растет медленнее степенной функции

• Любая степенная функция растет медленнее показательной

• Основание логарифмов не важно, т.к. скорость роста одинаковая с точностью до $const$$const$

Эмпирические измерения

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

Накладные расходы

При анализе алгоритма важно учитывать накладные расходы (overhead), связанные с его реализацией. Например, рекурсивный алгоритм может иметь большие накладные расходы, связанные с вызовами функций.

Накладные расходы по времени

Включают в себя время, затрачиваемое на выполнение вспомогательных операций, таких как:

• Вызовы функций

• Выделение и освобождение памяти

• Проверка условий

• Обновление счетчиков

Накладные расходы по памяти

Включают в себя память, используемую для хранения:

• Локальных переменных

• Параметров функций

• Вспомогательных структур данных

Пример: Сортировка вставкой

Время работы алгоритма.

$T(n)=c_{1}n+c_2(n-1)+c_4(n-1)+c_5\sum _{j=2}^n{t}_j+c_6\sum _{j=2}^n{t}_j-1+c_7\sum _{j=2}^n{t}_j-1+c_8(n-1)$$T(n) = c_1n + c_2(n-1) + c_4(n-1) + c_5 \sum_{j=2}^{n}{t_j} + c_6 \sum_{j=2}^{n}{t_j - 1} + c_7\sum_{j=2}^{n}{t_j - 1} + c_8(n-1)$

В лучшем случае:

$\begin{array}{c}T(n)=c_{1}n+c_2(n-1)+c_4(n-1)+c_5(n-1)+c_8(n-1)=\\ =(c_1+c_2+c_4+c_5+c_8)n-(c_2+c_4+c_5+c_8)\end{array}$$T(n) = c_1n + c_2(n-1) + c_4(n-1) + c_5(n-1) +c_8(n-1)= \newline = (c_1 + c_2 + c_4 + c_5 + c_8)n - (c_2 + c_4 + c_5 + c_8)$​

В худшем случае:

$\begin{array}{c}T(n)=c_{1}n+c_2(n-1)+c_4(n-1)+c_5(\frac{n(n+1)}{2}-1)+\\ +c_6\left(\frac{n(n+1)}{2}\right)+c_7\left(\frac{n(n+1)}{2}\right)+c_8(n-1)=\\ =(\frac{c_5}{2}+\frac{c_6}{2}+\frac{c_7}{2})n^2+(c_1+c_2+c_4+\frac{c_5}{2}-\frac{c_6}{2}-\frac{c_7}{2}+c_8)n-(c_2+c_4+c_5+c_8)\end{array}$$T(n) = c_1n +c_2(n-1) + c_4(n-1) + c_5 \left( \frac{n(n+1)}{2} - 1 \right) + \newline + c_6\left( \frac{n(n+1)}{2} \right) + c_7\left( \frac{n(n+1)}{2} \right) + c_8(n-1) = \newline = \left(\frac {c_5}{2} + \frac {c_6}{2} + \frac {c_7}{2}\right)n^2 + \left(c_1+c_2+c_4+\frac {c_5}{2} - \frac {c_6}{2} - \frac {c_7}{2} + c_8\right)n - (c_2+c_4+c_5+c_8)$

2. Рекуррентные соотношения и анализ рекурсивных алгоритмов

Рекуррентные соотношения (recurrence relations) — это уравнения, определяющие последовательность чисел, в которых каждый член последовательности выражается через предыдущие члены. Они часто используются для анализа времени работы рекурсивных алгоритмов, поскольку естественным образом описывают, как время работы задачи размером $n$$n$ зависит от времени работы подзадач меньшего размера.

Определение

Рекуррентное соотношение — это соотношение вида:

$\begin{array}{c}T(n)=\{\begin{array}{ll}aT(\frac{n}{b})+f(n),& n>1\\ \mathrm{\Theta }(1),& n=1\end{array}\end{array}$$T(n) = \begin{cases} aT(\frac{n}{b}) + f(n), & n > 1 \\ \Theta(1), & n = 1 \end{cases}$ , где $a\ge 1$$a \ge 1$ и $b\ge 1$$b \ge 1$

$f(n)$$f(n)$ — функция, асимптотически положительная.

Например, рекуррентное соотношение для времени работы алгоритма сортировки слиянием имеет вид:

• $T(1)=\mathrm{\Theta }(1)$$T(1) = \Theta(1)$ (базовый случай)

• $T(n)=2T\left(\frac{n}{2}\right)+\mathrm{\Theta }(n)$$T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n)$ (рекуррентное уравнение)

Методы решения рекуррентных соотношений

Существует несколько методов решения рекуррентных соотношений, т.е. получения асимптотических границ для $T(n)$$T(n)$.

Метод подстановки

В методе подстановки (substitution method) мы делаем предположение о виде решения, а затем используем математическую индукцию для доказательства его корректности.

Метод итераций

В методе итераций (iteration method) мы многократно подставляем рекуррентное уравнение в само себя, раскрывая рекурсию до тех пор, пока не получим выражение, не содержащее рекурсивных вызовов.

1. Раскрытие рекурсии: Подставляем рекуррентное уравнение в само себя, заменяя $T(n_i)$$T(n_i)$ на $f(T(n_{i1}),T(n_{i2}),\dots ,T(n_{ik}))$$f(T(n_{i1}), T(n_{i2}), \ldots, T(n_{ik}))$.

2. Упрощение: Упрощаем полученное выражение, объединяя подобные члены.

3. Поиск закономерности: Ищем закономерность в полученных выражениях и обобщаем её для произвольного уровня рекурсии.

4. Вычисление суммы: Вычисляем сумму, полученную в результате раскрытия рекурсии.

тут скорее всего должно быть что-то еще

Деревья рекурсии

Дерево рекурсии (recursion tree) — это графическое представление рекурсивных вызовов алгоритма. Каждый узел дерева представляет один рекурсивный вызов, а ребра соединяют вызовы, связанные отношением "родитель-потомок". Стоимость каждого узла — это время работы соответствующего рекурсивного вызова, не включая время, затрачиваемое на рекурсивные вызовы, которые он выполняет.

1. Построение дерева: Строим дерево рекурсии, начиная с корня, представляющего исходный вызов алгоритма.

2. Оценка стоимости уровней: Оцениваем стоимость каждого уровня дерева, суммируя стоимости всех узлов на этом уровне.

3. Вычисление общей стоимости: Суммируем стоимости всех уровней дерева, чтобы получить общую стоимость вычисления.

Основная теорема о рекуррентных соотношениях

Основная теорема (master theorem) предоставляет "кулинарную книгу" для решения рекуррентных соотношений вида:

$T(n)=aT\left(\frac{n}{b}\right)+f(n)$$T(n) = aT\left(\frac{n}{b}\right) + f(n)$

где $a\ge 1$$a \geq 1$ и $b>1$$b > 1$ — константы, а $f(n)$$f(n)$ — асимптотическая функция.

Основная теорема гласит следующее:

1. Если $f(n)=O(n^{{\log }_{b}a-ϵ})$$f(n) = O(n^{\log_b{a-\epsilon}})$ для некоторого $ϵ>0$$\epsilon > 0$, то $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a})$$T(n) = \Theta(n^{\log_b a})$

2. Если $f(n)=\mathrm{\Theta }(n^{{\log }_{b}a})$$f(n) = \Theta(n^{\log_ba})$, то $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a}\lg n)$$T(n) = \Theta(n^{\log_ba} \lg n)$

3. Если $f(n)=\mathrm{\Omega }(n^{{\log }_{b}a+ϵ})$$f(n) = \Omega(n^{\log_b{a+\epsilon}})$ для некоторого $ϵ>0$$\epsilon > 0$, и если $af\left(\frac{n}{b}\right)\le cf(n)$$af \left( \frac{n}{b} \right) \leq cf(n)$ для некоторого $c<1$$c < 1$ и достаточно больших $n$$n$, то $T(n)=\mathrm{\Theta }(f(n))$$T(n) = \Theta(f(n))$

Замечание!

$n^2<n^2\log n$$n^2 < n^2\log{n}$, но $\begin{array}{c}{n}^2\log n<\{\begin{array}{l}{n}^{2+1}\\ n^{2+0.00001}\\ n^{2+ϵ}\end{array}\end{array}$$n^2\log{n} < \begin{cases} n^{2+1} \\ n^{2+0.00001} \\ n^{2+\epsilon} \end{cases}$

Примеры решения рекуррентных соотношений с использованием основной теоремы

Пример 1

Рассмотрим рекуррентное соотношение для сортировки слиянием:

$T(n)=2T\left(\frac{n}{2}\right)+n$$T(n) = 2T \left( \frac{n}{2} \right) + n$

Здесь $a=2$$a = 2$, $b=2$$b = 2$, и $f(n)=n$$f(n) = n$.

• Вычислим ${\log }_{b}a={\log }_{2}2=1$$\log_b a = \log_2 2 = 1$.

• Поскольку $f(n)=n$$f(n) = n$, то $c=1$$c = 1$.

Следовательно, $c={\log }_{b}a$$c = \log_b a$, и по второй части основной теоремы имеем:

$T(n)=\mathrm{\Theta }(n\lg n)$$T(n) = \Theta(n \lg n)$

Пример 2

Рассмотрим рекуррентное соотношение:

$T(n)=3T\left(\frac{n}{4}\right)+n^2$$T(n) = 3T \left( \frac{n}{4} \right) + n^2$

Здесь $a=3$$a = 3$, $b=4$$b = 4$, и $f(n)=n^2$$f(n) = n^2$.

• Вычислим ${\log }_{b}a={\log }_{4}3\approx 0.792$$\log_b a = \log_4 3 \approx 0.792$.

• Поскольку $f(n)=n^2$$f(n) = n^2$, то $c=2$$c = 2$.

Поскольку $c>{\log }_{b}a$$c > \log_b a$, по третьей части основной теоремы имеем:

$T(n)=\mathrm{\Theta }(n^2)$$T(n) = \Theta(n^2)$

3. Динамические структуры данных

Динамические структуры данных — это структуры данных, которые могут изменяться во время выполнения программы: элементы могут добавляться, удаляться или изменяться. Это отличает их от статических структур данных, таких как массивы, размер которых фиксирован.

Линейные списки

Линейные списки — это структуры данных, в которых элементы упорядочены линейно. Каждый элемент содержит данные и ссылку на следующий элемент списка.

Способы представления

• Односвязный список: Каждый элемент содержит ссылку только на следующий элемент.

• Двусвязный список: Каждый элемент содержит ссылки на предыдущий и следующий элементы.

• Циклический список: Последний элемент списка ссылается на первый.

Стоимость операций

Алгоритм поиска

xxxxxxxxxx
4
1
x = L.head
2
while x != NIL and x.key != k
3
    x = x.next
4
return x

Вставка в двусвязный список (в начало)

xxxxxxxxxx
5
1
x.next = L.head
2
if L.head != NIL:
3
    L.head.prev = x
4
L.head = x
5
x.prev = NIL

Вставка в односвязный список (в начало)

xxxxxxxxxx
2
1
x.next = L.head
2
L.head = x

Вставка в конец односвязного списка

xxxxxxxxxx
10
1
function appendToEnd(L, x):
2
  if L.head == null:
3
    L.head = x
4
    x.next = null
5
  else:
6
    current = L.head
7
    while current.next != null:
8
      current = current.next
9
    current.next = x
10
    x.next = null

Вставка в конец двусвязного списка

xxxxxxxxxx
12
1
function appendToEnd(L, x):
2
  if L.head == null:
3
    L.head = x
4
    x.next = null
5
    x.prev = null
6
  else:
7
    current = L.head
8
    while current.next != null:
9
      current = current.next
10
    current.next = x
11
    x.prev = current
12
    x.next = null

Удаление из односвязного списка

xxxxxxxxxx
11
1
function deleteNode(L, value):
2
  if L.head == null:
3
    return // список пуст
4
  if L.head.value == value:
5
    L.head = L.head.next
6
    return
7
  current = L.head
8
  while current.next != null and current.next.value != value:
9
    current = current.next
10
  if current.next != null:
11
    current.next = current.next.next

Удаление из двусвязного списка

xxxxxxxxxx
16
1
function deleteNode(L, value):
2
  if L.head == null:
3
    return // список пуст
4
  if L.head.value == value:
5
    L.head = L.head.next
6
    if L.head != null:
7
      L.head.prev = null
8
    return
9
  current = L.head
10
  while current != null and current.value != value:
11
    current = current.next
12
  if current != null:
13
    if current.next != null:
14
      current.next.prev = current.prev
15
    if current.prev != null:
16
      current.prev.next = current.next

Деревья

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

Способы хранения деревьев (!дубль)

1. В deque: каждый элемент знает только своего родителя.

2. В обычном массиве. Родитель $\leftrightarrow$$\leftrightarrow$ ребёнок, восстанавливаются по индексам. НО! Только когда дерево заполнено полностью, за исключением, быть может, нижнего уровня. Формула для родителя: $\frac{i-1}{2}$${i-1}\over2$ Левый дочерний: $2i+1$$2i+1$ Правый дочерний: $2i+2$$2i+2$

3. С помощью узлов. Стоимость доступа $O(1)$$O(1)$.

    

Двоичные деревья

Двоичное дерево — это дерево, в котором каждый узел имеет не более двух дочерних узлов.

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

Дерево поиска — это двоичное дерево, в котором для каждого узла x выполняется следующее свойство: все ключи в левом поддереве x меньше x.key, а все ключи в правом поддереве x больше x.key.

Замечания!

• В std используется операция «меньше», элементы должны определять ее.

• Если дерево может содержать дубликаты, обычно не используется поиск по значению. Можно использовать инфиксный обход:

Элементы по порядку записи в массиве:

xxxxxxxxxx
2
1
[--] [--] [17] [17] [17] [17] [20]
2
           ^ lower             ^ upper

lower_bound — первый элемент, больший либо равный x

upper_bound — первый элемент, больший x

Тогда в диапазоне от lower_bound до upper_bound будут располагаться все дубликаты.

Операции БДП

• Вставка

• Извлечение (поиск)

• Следующий

• Предыдущий

• Минимальный

• Максимальный

Полный и слабый порядок

Введем на произвольном множестве бинарное отношение:

• Если это отношение позволяет различать все элементы множества, то это полный порядок.

• Weak ordering (слабый порядок) – бинарное отношение на элементах множества, при котором некоторые элементы множества не различаются между собой. Пример: «количество цифр в x, больше, чем в y».

Strict weak ordering (отношение строго частичного порядка) — бинарное отношение на элементах множества со следующими свойствами:

1. Irreflexivity: $\mathrm{\forall }x\in Scmp(x,x)=false$$\forall x \in S \ \ cmp(x, x) = false$

2. Assymetry: $\mathrm{\forall }x,y\in Scmp(x,y)=true\Rightarrow cmp(y,x)=false$$\forall x, y \in S \ \ cmp(x, y) = true \ \Rightarrow \ cmp(y, x) = false$

3. Transitivity: $\mathrm{\forall }x,y,z\in Scmp(x,y)\wedge cmp(y,z)=true\Rightarrow cmp(x,z)=true$$\forall x, y, z \in S \ \ cmp(x, y) \and cmp(y, z) = true \ \Rightarrow \ cmp(x, z) = true$

4. Несравнимость: $\mathrm{\forall }x,y,z\in S$$\forall x, y, z \in S$ $\begin{array}{c}cmp(x,y)\vee cmp(y,z)=true;\\ cmp(y,z)\vee cmp(z,y)=false;\\ cmp(x,z)\vee cmp(z,x)=false\end{array}$$cmp(x, y) \or cmp(y, z) = true; \newline cmp(y, z) \or cmp(z, y) = false; \newline cmp(x, z) \or cmp(z, x) = false$

Замечание. $true$$true$ и $false$$false$ здесь заменяют «элементы связаны / не связаны отношением».

Ветвящиеся деревья

Ветвящееся дерево — это дерево, в котором каждый узел может иметь произвольное количество дочерних узлов.

Способы представления

1. Массив

Этот способ часто используется для представления полных бинарных деревьев, таких как пирамиды (heaps). В таком представлении:

• Корень дерева находится в позиции 0.

• Для узла на позиции $i$$i$:

  • Левый потомок находится на позиции $2i+1$$2i + 1$.

  • Правый потомок находится на позиции $2i+2$$2i + 2$.

  • Родительский узел находится на позиции $\lfloor \frac{i-1}{2}\rfloor$$\left\lfloor \frac{i - 1}{2} \right\rfloor$ (если $i>0$$i > 0$).

Пример

Рассмотрим полное бинарное дерево:

Его представление в массиве будет:

xxxxxxxxxx
1
1
[10, 15, 30, 40, 50, 100, 40]

2. Указатели

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

Пример

Рассмотрим бинарное дерево:

Каждый узел будет представляться структурой:

xxxxxxxxxx
5
1
Node {
2
  value: int
3
  left: Node
4
  right: Node
5
}

И представление дерева будет выглядеть так:

xxxxxxxxxx
4
1
root = Node(10)
2
root.left = Node(15)
3
root.right = Node(30)
4
root.left.left = Node(40)

3. Левый потомок, правый брат

Этот способ используется для представления ветвящихся деревьев, где узлы могут иметь произвольное количество потомков. Каждый узел имеет два указателя: на своего первого (левого) потомка и на следующего (правого) брата.

Пример

Рассмотрим дерево:

Каждый узел будет представляться структурой:

xxxxxxxxxx
5
1
Node {
2
  value: int
3
  leftChild: Node
4
  rightSibling: Node
5
}

И представление дерева будет выглядеть так:

xxxxxxxxxx
6
1
root = Node(1)
2
root.leftChild = Node(2)
3
root.leftChild.rightSibling = Node(3)
4
root.leftChild.rightSibling.rightSibling = Node(4)
5
root.leftChild.leftChild = Node(5)
6
root.leftChild.leftChild.rightSibling = Node(6)

В этом представлении:

• Узел 1 имеет левого потомка 2 и правого брата 3.

• Узел 2 имеет левого потомка 5 и правого брата 6.

• Узел 3 является правым братом узла 2.

• Узел 4 является правым братом узла 3.

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

Сбалансированные деревья

[Более строгое определение] Сбалансированное дерево — это дерево поиска, в котором для любого узла количество элементов в левом и правом поддереве различается не более, чем на 1.

[Менее строгое определение] Дерево называется сбалансированным, если для любого узла $x$$x$ верно, что $|height(x.left)-height(x.right)|\le 1$$|height(x.left) - height(x.right)| \le 1$

При вставке или удалении требуется перестроение дерева. Таким образом, $O(1)$$O(1)$. Чтобы сохранить $O(\log n)$$O(\log n)$, ослабим требование сбалансированности дерева.

Красно-черные деревья

RB-tree — частный случай B-tree.

Красно-черное дерево представляет собой бинарное дерево поиска с одним дополнительным битом цвета в каждом узле. Цвет узла может быть либо красным ($RED$$RED$), либо черным ($BLACK$$BLACK$). В соответствии с накладываемыми на узлы дерева ограничениями ни один простой путь от корня в красно-черном дереве не отличается от другого по длине более чем в два раза, так что красно-черные деревья являются приближенно сбалансированными.

Каждый узел дерева содержит атрибуты $color$$color$, $key$$key$, $left$$left$, $right$$right$ и $р$$р$. Если не существует дочернего или родительского узла по отношению к данному, соответствующий указатель принимает значение NIL. Мы будем рассматривать эти значения МП. как указатели на внешние узлы (листья) бинарного дерева поиска. При этом все «нормальные» узлы, содержащие поле ключа, становятся внутренними узлами дерева.

Бинарное дерево поиска является красно-черным деревом, если оно удовлетворяет следующим красно-черным свойствам.

Замечание. Можно обойтись без затрат на цвет, но обычно это не окупается. В худшем случае возможно не более, чем 2-кратное различие по высотам поддеревьев.

Повороты

О вставке ниже.

Правое вращение.

xxxxxxxxxx
14
1
Right-Rotate(T, x)
2
    y = x.left
3
    x.left = y.right
4
    if y.right != T.nil
5
        y.right.p = x
6
    y.p = x.p
7
    if x.p == T.nil
8
        T.root = y
9
    elseif x == x.p.left
10
        x.p.left = y
11
    else
12
        x.p.right = y
13
    y. right = x
14
    x.p = y

Вставка

Вставляем всегда красный элемент (для сохранения баланса). Но можем получить тогда «локальную проблему» – 2 подряд идущих красных узла. В таком случае, нужно восстановить красно-черные свойства.

В RB-tree вводится вспомогательная операция вращения (выше).

Удаление

Оценка стоимости операций

Черная высота узла (black height) — количество черных вершин в пути от узла к листу, не считая сам лист (цвет вершины, от которой идем, нас не интересует).

Лемма 1. В пути от вершины с черной высотой $bh(node)$$bh(node)$ к листу не более $bh(node)$$bh(node)$ красных вершин $\Rightarrow$$\Rightarrow$ высота вершины $\le 2bh(node)$$\le 2bh(node)$.

Лемма 2. КЧД с $n$$n$ внутренними узлами ($n$$n$ узлов без листьев) имеет высоту $\le 2\log (n+1)$$\le 2\log (n+1)$.

Получается, что высота КЧД превосходит высоту идеально сбалансированного дерева не более, чем в 2 раза. Причем при больших $n$$n$ значение высоты КЧД будет стремиться в $\log n$$\log n$.

Таким образом, получили, что у всех операций АС $O(\log n)$$O(\log n)$.

AVL-деревья

AVL-деревья, названные в честь своих создателей, Адельсона-Вельского и Ландиса, представляют собой самобалансирующиеся бинарные деревья поиска. Они гарантируют логарифмическую сложность основных операций (вставка, удаление, поиск) даже в худшем случае, предотвращая вырождение дерева в линейный список.

Основные свойства

1. Свойство бинарного дерева поиска: Для каждого узла все ключи в левом поддереве меньше ключа узла, а все ключи в правом поддереве больше.

2. Свойство балансировки: Для каждого узла разница высот его левого и правого поддеревьев (называемая баланс-фактором) не превышает 1 (может быть -1, 0 или 1).

Высота дерева $\le 1.4405\log (n+2)-0.3277$$\le 1.4405 \log(n+2)-0.3277$. Доказывается через Фиббоначиевы деревья. По сравнению с КЧД превосходит ИСД на $45\mathrm{\%}$$45\%$. Для больших $n$$n$ стремится к $\log n$$\log n$.

Балансировка

При вставке или удалении узла баланс дерева может нарушиться. Для восстановления баланса AVL-деревья используют повороты:

• Левый поворот: применяется, когда баланс-фактор узла становится равным -2, а баланс-фактор его правого потомка -1 или 0.

• Правый поворот: применяется, когда баланс-фактор узла становится равным 2, а баланс-фактор его левого потомка 1 или 0.

• Двойной поворот (лево-правый или право-левый): применяется в остальных случаях нарушения баланса.

Основные операции

Для реализации каждая вершина имеет дополнительное поле — высота данного узла.

1. Вставка $O(\log n)$$O(\log n)$

   • Вставка нового узла происходит как в обычном бинарном дереве поиска.

   • После вставки проверяется баланс-фактор каждого узла на пути от нового узла до корня.

   • При нарушении баланса выполняется соответствующий поворот.

   • Требует 2 вращения.

2. Удаление

   • Удаление узла происходит как в обычном бинарном дереве поиска.

   • После удаления проверяется баланс-фактор каждого узла на пути от родителя удаленного узла до корня.

   • При нарушении баланса выполняется соответствующий поворот.

   • Может потребовать вращений в количестве высоты дерева (медленнее, чем КЧД).

3. Поиск $O(\log n)$$O(\log n)$

   • Поиск ключа происходит как в обычном бинарном дереве поиска.

   • Быстрее поиска в КЧД.

При построении случайных AVL-деревьев, наиболее велика вероятность получить идеальное.

Сравнение с другими деревьями

Преимущества AVL-деревьев

• Гарантированная логарифмическая сложность операций.

• Простота реализации поворотов.

Недостатки AVL-деревьев

• Большое количество поворотов при частых вставках и удалениях.

• Небольшая разница в производительности по сравнению с красно-черными деревьями, которые требуют меньше поворотов.

Замечания по реализации в C++

• set, multiset, map, multimap – обычно КЧД

• Технически, неважно, какой элемент, главное – наличие сравнения

• Итератор – bidirectional и совпадает с константным

• Операции не перемещают элементы в памяти

Allocator – некий объект, сущность которого используется для выделения и освобождения памяти. Allocator = распределитель памяти.

Сложность при создании map / set из диапазона:

• $O(N)$$O(N)$, если последовательность отсортирована

• иначе $O(N\log N)$$O(N\log N)$

B-деревья

B-деревья, в отличие от AVL-деревьев и красно-черных деревьев, оптимизированы для хранения данных на внешних носителях, таких как жесткие диски. Они отличаются от бинарных деревьев поиска тем, что каждый узел может содержать несколько ключей и указателей на дочерние узлы.

Основные свойства

1. Упорядоченность ключей: Ключи в каждом узле хранятся в отсортированном (неубывающем) порядке.

2. Количество ключей: Каждый узел, кроме корня, содержит от $t$$t$ до $2t-1$$2t - 1$ ключей, где $t$$t$ - минимальная степень B-дерева. Корень может содержать от $1$$1$ до $2t-1$$2t - 1$ ключей.

3. Количество потомков: Каждый узел имеет на один потомок больше, чем ключей.

4. Сбалансированность: Все листья находятся на одной глубине.

Высота. Для любого дерева с $n(n>0)$$n \ (n>0)$ ключами, высотой $h$$h$ и минимальной степенью $t>1$$t > 1$ верно: $h\le lo{g}_t\frac{n+1}{2}$$h \le log_t {{n+1} \over 2}$.

Асимптотика $O(\log N)$$O(\log N)$.

Операции

1. Поиск:

   • Поиск ключа начинается с корня.

   • В каждом узле выполняется поиск ключа среди ключей узла.

   • Если ключ найден, поиск завершается.

   • Если ключ не найден, поиск продолжается в соответствующем поддереве.

2. Вставка:

   • Новый ключ вставляется в соответствующий лист.

   • Если лист переполнен (содержит $2t$$2t$ ключей), он разбивается на два узла, содержащих по $t$$t$ ключей.

   • Средний ключ из переполненного листа перемещается в родительский узел.

   • Если родительский узел переполнен, он также разбивается, и этот процесс продолжается вверх по дереву до корня.

   • Если корень переполнен, создается новый корень, и высота дерева увеличивается на 1.

3. Удаление:

   • Удаление ключа происходит из соответствующего узла.

   • Если узел становится недополненным (содержит меньше t ключей), он объединяется с соседним узлом.

   • Если соседний узел также не дополнен, объединение происходит с родительским узлом, и этот процесс продолжается вниз по дереву до листьев.

Преимущества

• Оптимизация для дискового хранения: B-деревья минимизируют количество операций чтения с диска, поскольку каждый узел содержит много ключей.

• Сбалансированность: B-деревья гарантируют логарифмическую сложность операций.

Недостатки

• Сложность реализации: B-деревья сложнее в реализации, чем бинарные деревья поиска.

Сравнение с другими деревьями

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

Применение

• Базы данных: B-деревья широко используются в системах управления базами данных для индексирования данных.

• Файловые системы: B-деревья используются в некоторых файловых системах для организации данных на диске.

Пример

Идеально сбалансированное дерево

Идеально сбалансированное дерево — это дерево, в котором все листья находятся на одной глубине.

Сравнение стоимости операций

Асимптотические оценки

И еще неплохая табличка, украденная из чьего-то конспекта.

Замечание. Издержки – на хранение одного элемента.

Эмпирические оценки

На практике сбалансированные деревья поиска (например, красно-черные деревья) обычно работают быстрее, чем несбалансированные деревья поиска, даже для небольших наборов данных.

4. Амортизационный анализ

Амортизационный анализ — это метод анализа алгоритмов, который позволяет оценить среднее время выполнения операции в последовательности операций. Он особенно полезен, когда в последовательности встречаются как "дешевые", так и "дорогие" операции, и важно понять, как "дорогие" операции влияют на общую производительность.

Зачем нужен амортизационный анализ?

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

• Учет редких операций: Он позволяет учесть влияние редких, но "дорогих" операций, которые могут существенно исказить оценку времени работы в наихудшем случае.

• Анализ структур данных: Амортизационный анализ широко используется для анализа эффективности операций в динамических структурах данных, таких как динамические массивы, деревья поиска и системы непересекающихся множеств.

Учетные стоимости операций

В амортизационном анализе каждой операции присваивается учетная стоимость (amortized cost), которая может отличаться от её фактической стоимости. Учетные стоимости выбираются таким образом, чтобы сумма учетных стоимостей для любой последовательности операций была не меньше суммы фактических стоимостей этих операций.

Методы амортизационного анализа

1. Метод группировки (aggregate method)

В методе группировки мы определяем верхнюю границу $T(n)$$T(n)$ для общей стоимости $n$$n$ операций, а затем делим $T(n)$$T(n)$ на $n$$n$, чтобы получить амортизированную стоимость каждой операции.

Пример. Рассмотрим динамический массив, который увеличивает свой размер в два раза, когда он заполнен. Операция вставки элемента в массив имеет две возможные стоимости:

• $O(1)$$O(1)$: Если в массиве есть свободное место.

• $O(n)$$O(n)$: Если массив заполнен, и его нужно увеличить.

Анализ:

• В худшем случае каждая вставка может потребовать $O(n)$$O(n)$ времени.

• Однако, если мы рассмотрим последовательность $n$$n$ вставок, то увидим, что увеличение размера массива происходит только ${\log }_{2}n$$\log_2n$ раз.

• Общая стоимость $n$$n$ вставок составляет $O(n+n/2+n/4+...+1)=O(n)$$O(n+n/2+n/4+...+1)=O(n)$.

• Амортизированная стоимость каждой вставки, полученная методом группировки, равна $O(n)/n=O(1)$$O(n)/n=O(1)$.

Еще пример (multistack). Операции push, pop, multipop(k). Пусть сделано $n$$n$ операций, значит всего multipop может вытолкнуть $n$$n$ элементов. Тогда худшая оценка $O(n^2)$$O(n^2)$.

• $c_1\cdot Pop+c_2\cdot Push+c_3\cdot MultiPop$$c_1 \cdot Pop + c_2 \cdot Push + c_3 \cdot MultiPop$

• MultiPop не может быть больше Push, тогда получаем: $c_1\cdot Pop+2c_2\cdot Push\approx O(n)$$c_1 \cdot Pop + 2 c_2\cdot Push \approx O(n)$

• Среднее: $\frac{O(n)}{n}\approx O(1)$$\frac {O(n)} {n} \approx O(1)$

2. Метод предоплаты (accounting method)

В методе предоплаты мы "предоплачиваем" за "дорогие" операции, выполняя "дешевые" операции. "Предоплата" накапливается в виде "кредита", который затем используется для оплаты "дорогих" операций.

Основная идея. $c_i$$c_i$ – фактическая стоимость $i$$i$-й операции. $\widehat{c_i}$$\widehat {c_i}$ – учетная стоимость $i$$i$-й операции, она может быть больше или меньше фактической. Но $\sum _{i=1}^n\widehat{c_i}\ge \sum _{i=1}^n{c}_i$$\sum_{i=1}^{n} {\widehat {c_i}} \ge \sum_{i=1}^{n} {c_i}$ для любой последовательности. Значит нужно оценивать сверху $\sum _{i=1}^n\widehat{c_i}$$\sum_{i=1}^{n} {\widehat {c_i}}$.

Пример: мультистек с операцией multipop

Рассмотрим стек с операциями push, pop и multipop(k), которая удаляет $k$$k$ элементов из стека. Если [c_i^; c_i] – credit. Credit – для того, чтобы, если $c_i$$c_i$ оказалось больше $\widehat{c_i}$$\widehat {c_i}$.

Учетные стоимости:

• push: 2

• pop: 0

• multipop(k): 0

Анализ:

• При каждом push мы "предоплачиваем" 1 единицу "кредита" за будущий pop этого элемента.

• Операции pop и multipop оплачиваются за счет накопленного "кредита".

• Поскольку каждый элемент может быть удален из стека только один раз, "кредита" всегда достаточно для оплаты всех операций.

• Получаем $\sum _{i=1}^n\widehat{c_i}=2n$$\sum_{i=1}^{n} {\widehat {c_i}} = 2n$. Значит $O(n)$$O(n)$.

3. Метод потенциалов (potential method)

В методе потенциалов мы вводим потенциальную функцию Φ, которая отображает состояние структуры данных в неотрицательное число. Амортизированная стоимость операции определяется как сумма её фактической стоимости и изменения потенциальной функции.

Требования к потенциальной функции:

• Φ(начальное состояние) = 0

• Φ(любое состояние) ≥ 0

• Анализ амортизированной стоимости операций: $\widehat{c_i}=c_i+\mathrm{\Phi }(D_i)-\mathrm{\Phi }(D_{i-1})$${\widehat {c_i}} = c_i + \Phi(D_i) - \Phi(D_{i-1})$

Ограничения:

• Потенциальная функция должна адекватно отражать "запас энергии" или "накопленную стоимость" в структуре данных.

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

• Потенциальная функция должна быть консервативной, то есть не должна искусственно занижать амортизированные затраты.

Замечание. Метод потенциалов является обобщением метода предоплаты.

Сумма разности потенциалов: $\sum _{i=1}^n\widehat{c_i}=\sum _{i=1}^n{c}_i+(\mathrm{\Phi }(D_n)-\mathrm{\Phi }(D_0))/\ge 0/\ge \sum _{i=1}^n{c}_i$$\sum_{i=1}^{n} {\widehat {c_i}} = \sum_{i=1}^{n} {c_i} + \left( \Phi(D_n) - \Phi(D_0) \right) \ \left/\ge0\right/ \ge \sum_{i=1}^{n} {c_i}$

Пример: Бинарный счетчик

Рассмотрим бинарный счетчик, который хранит число в двоичном виде. Операция "increment" увеличивает число на 1.

Потенциальная функция: Φ(счетчик) = количество единиц в двоичном представлении числа.

Анализ:

• Фактическая стоимость операции "increment" равна количеству битов, которые нужно перевернуть.

• Изменение потенциальной функции равно разности между количеством единиц после и до операции "increment".

• В худшем случае нужно перевернуть все биты, но при этом Φ уменьшается на $O(\log n)$$O(\log⁡n)$.

• Амортизированная стоимость "increment" равна $O(1)+O(-\log n)=O(1)$$O(1)+O(−\log⁡n)=O(1)$.

Пример: multistack

$\mathrm{\Phi }(D_i)$$\Phi(D_i)$ – количество элементов в multistack. Условие на функцию выполняется.

• Push: $\widehat{c_i}=1+\mathrm{\Phi }(D_i)-\mathrm{\Phi }(D_{i-1})=2$$\widehat{c_i} = 1 + \Phi(D_i) - \Phi(D_{i-1}) = 2$

• Pop: $\widehat{c_i}=1+\mathrm{\Phi }(D_1)-\mathrm{\Phi }(D_{i-1})=0$$\widehat{c_i} = 1 + \Phi(D_1) - \Phi(D_{i-1}) = 0$

• MultiPop: $\widehat{c_i}=k\cdot Pop=0$$\widehat{c_i} = k \cdot Pop = 0$

Получаем $O(n)$$O(n)$, усредненная $O(1)$$O(1)$.

Системы непересекающихся множеств

Система непересекающихся множеств (disjoint-set data structure) - это структура данных, которая поддерживает операции над коллекцией непересекающихся множеств.

Основные операции:

• MakeSet(x): Создает новое множество, содержащее только элемент x.

• Union(x, y): Объединяет множества, содержащие элементы x и y.

• FindSet(x): Возвращает представителя множества, содержащего элемент x.

Оценка амортизированной стоимости операций:

С помощью амортизационного анализа можно показать, что амортизированная стоимость операций $MakeSet$$MakeSet$, $Union$$Union$ и $FindSet$$FindSet$ в системе непересекающихся множеств с использованием объединения по рангу и сжатия пути составляет $O(\alpha (n))$$O(\alpha(n))$, где $\alpha (n)$$\alpha(n)$ - обратная функция Аккермана, которая растет очень медленно.

Для достижения высокой эффективности операций Union и FindSet применяются две эвристики:

1. Объединение по рангу (Union by Rank): При объединении двух множеств дерево с меньшим рангом присоединяется к дереву с большим рангом. Ранг - это верхняя граница высоты дерева.

2. Сжатие пути (Path Compression): Во время операции FindSet все узлы на пути от x до корня переподключаются непосредственно к корню.

Для анализа амортизированной стоимости операций над disjoint-set data structure с использованием объединения по рангу и сжатия пути применим метод потенциалов.

Определим потенциальную функцию $\Phi$$Φ$ для леса непересекающихся множеств как сумму потенциалов всех узлов в лесу. Потенциал узла x определяется как:

• $\Phi (x)=\alpha (rank(parent(x)))$$Φ(x) = α(rank(parent(x)))$, если $x$$x$ не является корнем и $rank(x)<rank(parent(x))$$rank(x) < rank(parent(x))$,

• $\Phi (x)=0$$Φ(x) = 0$, в противном случае,

где $\alpha (n)$$α(n)$ - обратная функция Аккермана, которая растет очень медленно.

1. MakeSet(x):

   • Фактическая стоимость: $O(1)$$O(1)$

   • Изменение потенциала: $\Phi (x)=0$$Φ(x) = 0$ (т.к. $x$$x$ - корень)

   • Амортизированная стоимость: $O(1)+0=O(1)$$O(1) + 0 = O(1)$

2. Union(x, y):

   • Фактическая стоимость: $O(1)$$O(1)$ (с учетом объединения по рангу)

   • Изменение потенциала:

     • Если ранги корней равны, то ранг одного из корней увеличивается на 1, что приводит к увеличению потенциала на $\alpha (n)$$α(n)$ в худшем случае.

     • Если ранги корней различны, то потенциал не изменяется.

   • Амортизированная стоимость: $O(1)+\alpha (n)=O(\alpha (n))$$O(1) + α(n) = O(α(n))$

3. FindSet(x):

   • Фактическая стоимость: $O(k)$$O(k)$, где $k$$k$ - длина пути от x до корня.

   • Изменение потенциала:

     • Сжатие пути уменьшает потенциал каждого узла на пути от $x$$x$ до корня, кроме корня самого.

     • Суммарное уменьшение потенциала может быть оценено как $O(k\alpha (n))$$O(kα(n))$.

   • Амортизированная стоимость: $O(k)-O(k\alpha (n))=O(\alpha (n))$$O(k) - O(kα(n)) = O(α(n))$

Итог:

Амортизированная стоимость операций $MakeSet$$MakeSet$, $Union$$Union$ и $FindSet$$FindSet$ в системе непересекающихся множеств с использованием объединения по рангу и сжатия пути составляет $O(\alpha (n))$$O(α(n))$.

Замечания:

• Функция α(n) растет настолько медленно, что на практике её можно считать константой.

• Амортизированный анализ показывает, что в среднем операции над disjoint-set data structure выполняются очень быстро, несмотря на то, что некоторые отдельные операции могут быть "дорогими".

5. Графы

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