Введение в программирование 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 - Повороты надо делать рекурс