Введение в программирование 11. Дерево Фенвика деревьев Фенвиков, наивное дерево поиска, AVL-дерево

Введение в программирование, алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики

Лекция прочитана 18 ноября 2021 года
Лектор: Степанов Илья Даниилович
Оператор: Мария Шкатова
Монтаж: Жильцов Игорь

0:00 - Фенвик Фенвиков
15:25 - Время построения Фенвика Фенвиков
19:21 - Ответ на запрос в Фенвике Фенвиков
22:55 - Асимптотика ответа на запрос
30:17 - Чем Фенвик Фенвиков лучше двумерного Фенвика?
30:40 - Деревья поиска
38:05 - Наивная реализация. Операция find
39:40 - Наивный insert
42:50 - В чём проблема этой реализации?
43:38 - Наивный erase
51:51 - Сбалансированное дерево поиска. АВЛ-дерево
55:20 - Глубина АВЛ-дерева из N вершин
1:09:05 - Балансировка дерева после одного insert'а
1:12:11 - Разбор случаев: Δ(a) = -2, Δ(b) = 0
1:16:43 - Δ(a) = -2, Δ(b) = -1
1:18:20 - Δ(a) = -2, Δ(b) = 1
1:25:17 - Идея балансировки в случае Δ(a) = 2
1:26:15 - Повороты надо делать рекурсивно, вопросы из зала