Иерархические структуры, дающие логарифмические операции: двоичное дерево поиска для упорядоченных запросов, — для быстрого минимума.
Ключевые тезисы
- Несбалансированное дерево поиска вырождается в список — отсюда AVL, красно-чёрные и .
- даёт минимум за константу и вставку за логарифм — основа с приоритетом.
- оптимизированы под диск: узел равен странице, и это стандарт индексов баз данных.
Видеолекции
Записи университетских курсов, где эта тема звучит. Тайм-кодов у них нет, поэтому открываются они с начала.
Связанные темы
Структуры данных
Hash Tables85%
Хеш-таблицы · Алгоритмы и структуры данныхДоступ по ключу за константу в среднем. Основа словарей и множеств — и структура, на которой держится большая часть повседневного кода.
Arrays, Lists, Stacks and Queues85%
Массивы, списки, стеки и очереди · Алгоритмы и структуры данныхЧетыре базовых способа хранить последовательность. Отличаются не тем, что умеют, а тем, что у них дёшево, а что дорого.
Sorting Algorithms85%
Сортировки · Алгоритмы и структуры данныхБыстрая, слиянием, пирамидальная — три способа упорядочить данные за O(n log n) с разными свойствами по памяти, устойчивости и худшему случаю.
Order Statistics85%
Порядковые статистики · Алгоритмы и структуры данныхНайти k-й по величине элемент, не сортируя весь массив. Quickselect делает это в среднем за линию.
Caching85%
Кеширование · Системный дизайн ML-сервисовНе считать то, что уже посчитано: кеш предсказаний, признаков и эмбеддингов.
Тема встречается в тесте по направлениям — ошибки приведут обратно на эту страницу.
Глава «Алгоритмы и структуры данных» последний раз правилась . Нашли ошибку — напишите.