Где применяется
1. Задача
Шаги 72-75 дали тебе все детали. Шаг 72 смотрит на узел, перекошенный на 2, и называет, какая из четырёх форм перед тобой (LL, LR, RL, RR). Шаги 73 и 74 это два одиночных вращения, которые чинят узел, перекошенный в одну сторону. Шаг 75 это двойное вращение для двух зигзагов, с которыми одно вращение не справляется. Осталось собрать всё это в операцию, которую ты и правда вызываешь: insert. Вставка в AVL-дерево это обычная вставка в BST плюс один шаг. На обратном пути ты проверяешь каждый узел, через который прошёл, и вращаешь, как только какой-то узел перекошен на 2. Тогда дерево никогда не превратится в длинную цепочку, о которой предупреждал шаг 71, в каком бы порядке ни приходили данные.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи, где нужно держать отсортированное множество, пока значения прибывают, и быстро искать значение или его ближайшего соседа. В JavaScript нет встроенного отсортированного множества, а AVL-дерево даёт вставку и поиск за O(log n) даже на отсортированных данных.
Вставь каждое значение в своё AVL-дерево, и при любом порядке вставок результат будет сбалансирован.
Храни брони в дереве по времени начала, а перед вставкой спустись как при поиске, запоминая ближайшее начало с каждой стороны, и проверь пересечение.
Вставляй каждое новое число и пропускай повторы, а getIntervals идёт обходом in-order и склеивает подряд идущие значения.