Алгоритмы и структуры данных (основной поток) 10. Деревья поиска: AVL-дерево, Splay-дерево

Таймкоды:
00:00:00 - Введение
00:00:05 - Анонс предстоящей темы(деревьев поиска)
00:00:46 - Формулировка задачи
00:07:13 - "Наивное дерево поиска"
00:11:48 - Find
00:13:47 - Insert
00:17:28 - Erase
00:24:55 - AVL-дерево
00:29:12 - Утверждение: высота AVL-дерева логарифмическая
00:37:43 - Вращения
00:42:19 - Как с помощью вращений поддерживать инвариант AVL-дерева
01:00:22 - Splay-дерево
01:07:17 - Зачем нам это?
01:09:07 - Зачем нам это? 2.0
01:10:25 - Утверждение: амортизированное время работы
01:11:20 - Напоминание: Метод потенциалов
01:15:06 - Доказательство утверждения
01:17:23 - Лемма: оценка на a(splay(x))

Дата лекции: 08.11.23
Лектор : Степанов Илья Даниилович

Оператор: Карплюк К.
Монтажёр: Зуев Н.

Плейлист :    • [АиСД] Алгоритмы и структуры данных /...