008. Деревья поиска (окончание). Декартовы деревья. - М. А. Бабенко

YOUTUBE · 18.11.2025 19:32

Ключевые темы и таймкоды

Анализ спел-деревьев

0:09

В видео обсуждается анализ спел-деревьев, которые являются универсальными ускорителями для алгоритмов, проходящих по дереву.
Спел-деревья обладают тремя свойствами: вершина становится корнем, фактическая сложность работы пропорциональна глубине вершины, и учетная стоимость логарифмическая.

Доказательство сложности спел-деревьев

4:08

Доказывается, что для выполнения сплея достаточно запросить монеты, один плюс три помножить на увеличение ранга.
Рассматриваются отдельные шаги сплея, такие как зиг-шаг, зиг-зиг и зигзаг шаги.
Доказывается, что стоимость зиг-зиг и зигзаг шагов равна три помножить на изменение ранга.

Анализ зиг-зиг и зигзаг шагов

11:50

Зиг-зиг и зигзаг шаги анализируются, и показывается, что их стоимость равна три помножить на изменение ранга.
Обсуждается, почему нельзя заменить тройки на другие числа и почему они необходимы для анализа.

Анализ сплея

15:00

В видео обсуждается анализ сплея, который является быстрым способом изменения структуры дерева.
Для оценки стоимости сплея используется учетная оценка, которая показывает, что стоимость сплея логарифмическая.

Оценка изменения структуры дерева

25:45

В видео объясняется, что учетная оценка не учитывает изменение структуры дерева при вставке вершины.
Для учета этого изменения используется логарифмическая оценка, которая показывает, что лишь логарифмическое число рангов изменяется.

Ремув и слияние деревьев

30:07

В видео обсуждаются операции ремув и слияние деревьев, которые также имеют логарифмическую стоимость.
При слиянии деревьев происходит увеличение веса корня, но за это нужно заплатить еще одним логарифмом.

Введение в деревья

32:15

Видео начинается с обсуждения различных типов деревьев, включая детерминированные и амортизированные деревья, а также трандомизированные деревья.
Затем автор переходит к описанию декартовых деревьев, которые являются гибридом бинарного дерева поиска и кучи.

Рандомизированные деревья

36:10

В этой части автор объясняет, что рандомизированные деревья обладают логарифмическим ожиданием высоты.
Он также упоминает, что рандомизированные деревья могут быть использованы для решения задач, связанных с рандомизацией.

Сливаемо-разделяемые деревья

46:37

В этой части автор рассказывает о том, что декартовые деревья являются сливаемо-разделяемыми, что позволяет легко выполнять операции вставки и удаления.
Он также объясняет, как эти операции могут быть реализованы с использованием мерч и сплит операций.

Сплит и мерч

50:00

В видео объясняется, как выполнять операции сплит и мерч в декартовом дереве.
Сплит и мерч работают за логарифмическое время и позволяют объединять и разделять деревья.

Построение декартового дерева

1:00:30

В видео рассказывается о построении декартового дерева за линейное время.
Построение дерева основано на сортировке пар ключ-значение и использовании алгоритма, эквивалентного сортировке.

Вставка новой пары в декартово дерево

1:03:09

Процедура перестройки дерева работает следующим образом:
В новой паре ключ должен быть больше, чем все уже вставленные ключи.
После вставки новая пара должна быть расположена в специальной точке, выделенной вершине.

Поиск подходящей точки вставки

1:10:44

Вместо поиска сверху вниз, можно использовать линейный поиск снизу вверх.
Учетная стоимость каждого шага - константа.

Глубина дерева и монетки

1:12:27

Глубина дерева каждый раз повышается на один при операции.
Монетки кладутся на каждую вершину правого пути.

Вопросы и ответы

1:13:07

Если приоритет новой вершины больше всех старых, правый путь просто наращивается.
Если приоритет новой вершины меньше всех старых, правый путь сокращается до единицы.