Введение в программирование 12. Splay-дерево, В-дерево

Введение в программирование, алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики Лекция прочитана 25 ноября 2021 года Лектор: Степанов Илья Даниилович Оператор: Мария Шкатова Монтаж: Жильцов Игорь 0:00 - Splay-дерево 5:39 - 4 операции поворота. Zig 8:00 - Zigzig и zigzag 11:15 - Процедура поднятия в корень splay 16:20 - Insert в splay-дереве 18:34 - Erase в splay-дереве 20:55 - Find в splay-дереве 21:23 - Кого мы куда поднимаем? 25:29 - Асимптотика 26:26 - Ухудшится ли асимптотика, если не делать splay? 27:00 - Доказываем асимптотику для splay 32:34 - Оценка амортизационной сложности для zig 36:01 - Оценка амортизационной сложности для zigzig 46:24 - Оценка амортизационной сложности для zigzag 52:48 - Оценка амортизационной сложности для splay 1:01:08 - Что произойдёт на вырожденном в линию дереве? 1:02:23 - В чём преимущество splay-дерева? 1:05:03 - В-дерево 1:11:18 - Оценка на глубину В-дерева 1:18:19 - Зачем нужно В-дерево? (+ операция find)