Введение в программирование 13. В-дерево, Декартово дерево, Неявное дерево поиска

Введение в программирование, алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики Лекция прочитана 2 декабря 2021 года Лектор: Степанов Илья Даниилович Оператор: Мария Шкатова Монтаж: Жильцов Игорь 0:00 - Продолжение В-дерева. Повторение 04:47 - find в В-дереве 08:10 - insert в В-дереве 13:32 - "Разъединение вершинок" 23:26 - insert требует только спуск, без подъёма 24:58 - erase в В-дереве, "соединение вершинок" 49:17 - Декартово дерево. Определение 52:50 - Пример 55:18 - Упражнение 56:00 - Теорема (без доказательства): глубина Декартового дерева 57:22 - Чем Декартово дерево нам интересно? 59:12 - merge Декартовых деревьев 1:03:51 - Как удобно генерировать игреки (приоритеты)? 1:06:20 - split Декартового дерева 1:12:34 - insert и erase через split и merge 1:15:42 - Модельная задача, решаемая новой структурой 1:18:00 - Неявное дерево поиска (дерево поиска по неявному ключу) 1:19:58 - merge не меняется 1:20:56 - splitBySize - адаптация split 1:24:05 - Как решать модельную задачу структурой? 1:25:56 - Как мы пересчитываем суммы при вставке? 1:27:08 - Вопросы от студентов