Задачник Базовый курс EN

На чём держится

дерево поиска

Статьи

DS Структура данных Двоичное дерево поиска Меньшие налево, большие направо: поиск, порядок и k-й элемент за высоту дерева — от log n до n. O(h): от O(log n) до O(n) 2 задачи DS Структура данных АВЛ-дерево Дерево поиска, где высоты веток у узла различаются не больше чем на 1: высота до ~1,44·log₂ n. O(log n) на поиск, вставку и удаление 2 задачи DS Структура данных Красно-чёрное дерево Дерево поиска с узлами двух цветов: высота до 2·log₂(n + 1), не больше трёх поворотов на операцию. O(log n) на поиск, вставку и удаление 2 задачи DS Структура данных Декартово дерево Ключ и случайный приоритет: глубина O(log n) в среднем, split и merge, массив с разворотом куска за O(log n). O(log n) в среднем на поиск, вставку, удаление, split и merge 1 задача DS Структура данных B-дерево Дерево с сотнями ключей в узле-странице: поиск среди миллиарда ключей читает пять страниц. O(log n) сравнений, O(log_B n) чтений страниц 2 задачи DP Приём Динамика на отрезках Состояние — отрезок [i, j], переход — где его разрезать: дерево поиска, порядок умножения матриц, распил. O(n³) 2 задачи GEO Структура данных k-d дерево Двоичное дерево, которое делит пространство по осям по очереди: ближайшая точка — за десятки шагов вместо перебора. O(n log n) построение; O(log n) на запрос в среднем 1 задача

Задачи

Повороты на конвейере Проверка раскраски Два перепутанных ключа Разрез по меридиану Высота без дерева Загрузка по порядку Сколько раскрасок

Часто рядом

дерево 6 классика 6 поиск 5 запросы на отрезке 5 собеседования 4 базы данных 2 операционные системы 2 в проде 2 геоданные 2 олимпиады 2 k-я статистика 1 скользящее окно 1