Повороты на конвейере
Сервис сейсмических сводок держит толчки последних дней в АВЛ-дереве: ключ — номер события, номера растут со временем. Новое событие вставляется, а событие, которое стало старше окна, удаляется. Дерево переписывают на другой язык, и, чтобы сверить две реализации, нужен эталон: сколько перебалансировок каждого вида сделает дерево на записанном журнале операций и какой высоты оно будет в конце. Реализации должны совпасть до поворота, поэтому правила заданы точно.
- Вставка ключа k — как в обычном дереве поиска: от корня налево, если k меньше ключа узла, иначе направо; новый узел становится листом.
- Удаление ключа k. Узел без детей просто убирают, узел с одним ребёнком заменяют этим ребёнком. У узла с двумя детьми ключ заменяют наименьшим ключом его правого поддерева, а узел, где этот наименьший ключ лежал, убирают (левого ребёнка у него нет, его место занимает правый, если он есть).
- Перебалансировка. После вставки и после удаления все узлы на пути от места изменения до корня, снизу вверх, пересчитывают высоту (у листа высота 1, у пустого поддерева 0). Если у узла высота левого поддерева на 2 больше правого, смотрят на левого ребёнка: если высота его левого поддерева не меньше высоты правого, делают поворот направо вокруг узла — это случай LL; иначе сначала поворот налево вокруг ребёнка, потом направо вокруг узла — случай LR. Если выше правое поддерево — зеркально: RR (поворот налево) или RL (поворот направо вокруг правого ребёнка, потом налево вокруг узла). После поворота подъём продолжается от нового корня этого поддерева. При удалении путь начинается от родителя убранного узла.
Третий и четвёртый тесты — все 19 073 землетрясения силой от 5 за 2015–2025 годы из каталога USGS: событие номер i вставляется, когда происходит, и удаляется, как только очередное событие случается на 7 суток (в третьем тесте) или на 30 суток (в четвёртом) позже него.
Вход
В первой строке q (1 ≤ q ≤ 10⁵) — число операций. Дальше q строк вида + k (вставить ключ k, которого в дереве нет) или - k (удалить ключ k, который в дереве есть), 1 ≤ k ≤ 10⁹. Дерево вначале пустое.
Выход
Пять чисел через пробел: сколько было перебалансировок вида LL, LR, RR и RL за все операции и высоту дерева в конце (0, если оно пустое). Двойной поворот считается одной перебалансировкой своего вида.
Примеры
Пример 1
10 + 1 + 2 + 3 + 4 + 5 + 6 + 7 - 1 - 2 - 3
0 0 5 0 3
Пример 2
12 + 50 + 20 + 30 + 80 + 60 + 10 + 90 + 70 + 40 - 10 - 90 - 30
0 1 1 1 3
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Это прямое применение статьи: АВЛ-дерево с высотами в узлах, вставка и удаление с подъёмом к корню. Вся трудность — в точном соблюдении правил, особенно при удалении.
2Подсказка 2
Разберите первый пример руками. После вставки ключей от 1 до 7 дерево идеальное: корень 4, под ним 2 и 6. Удаление 1 и 2 перекосов не создаёт, а после удаления 3 у корня слева пусто, а справа поддерево высоты 2 — и правый ребёнок 6 ровный: у него ветки 5 и 7 одной высоты. Какой поворот здесь нужен — одиночный или двойной?
3Идея
Рекурсивные вставка и удаление, как в листинге статьи: функция возвращает новый корень поддерева, а на обратном пути каждый узел вызывает перебалансировку. Обратный путь рекурсии — ровно путь от места изменения к корню, которого требует условие. Ровный ребёнок встречается только при удалении, и для него нужен одиночный поворот: правило «высота внешнего поддерева ребёнка не меньше внутреннего» записывается через ≥, а не через >.
4Разбор
Узел хранит ключ, двух детей и высоту. Перебалансировка узла: пересчитать высоту, вычислить разность высот поддеревьев; при +2 сравнить высоты поддеревьев левого ребёнка и сделать LL (поворот направо) или LR (поворот налево у ребёнка, затем направо у узла), при −2 — зеркально. Поворот меняет три ссылки и пересчитывает высоты двух узлов — сначала того, что опустился, потом того, что поднялся.
Удаление спускается к ключу. Узел с одним ребёнком или без детей возвращает этого ребёнка (или пустоту). У узла с двумя детьми ключ заменяется наименьшим ключом правого поддерева, и рекурсивное удаление этого ключа из правого поддерева само пройдёт вниз до его узла и обратно, перебалансируя по дороге. Потом перебалансируется сам узел и всё выше.
Почему при ровном ребёнке нужен одиночный поворот. Пусть у узла x правое поддерево выше на два, его корень y ровный, оба поддерева y высоты h, а левое поддерево x — высоты h − 1. Одиночный поворот налево делает y корнем: слева x с поддеревьями высот h − 1 и h, его высота h + 1, справа поддерево высоты h — всё в порядке. Двойной поворот поднимает наверх левого внука z, а правое поддерево z переезжает к y и встаёт рядом с правым поддеревом y высоты h. Если у z это поддерево было пониже, высоты h − 2, у y выходит перекос в два этажа, и дерево перестаёт быть АВЛ-деревом. А если и не выходит, форма всё равно другая, и ответ другой: в первом примере правильно 0 0 5 0 3, а с двойным поворотом получается 0 0 4 1 3.
На настоящих данных все перебалансировки — RR: каждый новый ключ больше всех, и при вставке перевешивает правая ветка правого ребёнка; удаляется всегда самый маленький ключ, и после него тоже перевешивает правая сторона. В окне 7 суток их 26 937 на 19 073 вставки и 19 047 удалений.
4+Решение
5Сложность
Каждая операция стоит O(log n), где n — число ключей в дереве: высота АВЛ-дерева не больше 1,44·log₂ n. Всего O(q log q) времени и O(q) памяти. Глубина рекурсии — высота дерева, при 10⁵ ключах не больше 24, так что предел рекурсии Python не мешает.
6Типичные ошибки
- Строгое сравнение вместо нестрогого. Правило вставки «если внутреннее поддерево ребёнка выше — двойной поворот, иначе одиночный» верно и для удаления, а вот «если внешнее выше — одиночный, иначе двойной» при ровном ребёнке выбирает двойной поворот: дерево получает другую форму, а иногда и перекос, которого АВЛ-дерево не допускает. На первом примере ответ расходится сразу.
- Предшественник вместо преемника. Если узел с двумя детьми заменять наибольшим ключом левого поддерева, дерево тоже останется деревом поиска, но форма и число поворотов будут другими.
- Нет перебалансировки на пути к преемнику. Узлы между удаляемым и преемником тоже теряют высоту; если перебалансировать только узлы над удаляемым, перекосы ниже останутся.
- Порядок пересчёта высот в повороте. Сначала опустившийся узел, потом поднявшийся: высота нового корня зависит от уже исправленной высоты его ребёнка.