Где применяется
1. Задача
У тебя набор чисел, который меняется весь день: приходят новые числа. Ты всё время спрашиваешь «есть ли там 42?» и «дай все числа от 10 до 20 по порядку». Отсортированный массив быстро ищет делением пополам. Но при каждой вставке ему приходится сдвигать все элементы после нового, чтобы освободить место. Хеш-множество быстро вставляет и ищет, но порядка в нём нет вообще, поэтому на вопрос про диапазон оно не ответит.
Нужно всё сразу: быстрый поиск, быстрая вставка и порядок, и всё это на наборе, который постоянно меняется.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитinsert(root, 4), insert(root, 13), insert(root, 6) // root = [8, 3, 10, 1, 6, null, 14]Каждый узел делит своё поддерево: меньшие значения уходят влево, большие вправо. Вставляем [4, 13, 6] по очереди.
Столбики: числа по возрастанию. В дереве лежат те же числа, поэтому подсвеченный столбик показывает значение, с которым поиск только что сравнил ключ.
Одна операция: одно сравнение. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.
O(n)O(log n)
Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.
Как узнать
Эти слова в условии значат этот паттерн
- двоичное дерево поиска: left < node < right в каждом узле
- вставка/удаление/поиск с сохранением порядка данных
- проверить BST / k-й наименьший / симметричный обход даёт отсортированную последовательность
- ближайшее значение или запрос по диапазону на множестве, которое меняется со временем
- массив заранее не дан, значения приходят по одному
Похоже, но не то
- Бинарный поиск (массив) (Binary search (array))
Массив делится пополам по индексу, но вставка в него дорога. Дерево делится по указателю и вставку берёт.
- Хеш-множество / словарь (Hash set / map)
Словарь быстрее для точного поиска. Дерево ещё отвечает про диапазоны и даёт порядок.
- Бинарная куча / очередь с приоритетом (Binary heap / priority queue)
Куча обещает только минимум в корне. Дерево поиска упорядочивает каждую пару узлов.
- Обход дерева (Tree traversal)
Та страница про обход всего дерева. Эта про правило упорядочивания.
Сбалансированное дерево при n до 1e6 даёт O(log n) на операцию. Несбалансированное вырождается в O(n).
На LeetCode
Задачи на двоичное дерево поиска, где одно сравнение в узле говорит, в какую сторону идти. Поиск, вставка и вопросы о диапазоне идут по одному пути, около log n шагов, если дерево сбалансировано.
search из урока, только возвращаешь узел вместо true.
insert из урока под тем же именем.
Обходи дерево и пропускай левую сторону, когда узел меньше low, и правую, когда он больше high.