Где применяется
1. Задача
В прошлом уроке вставка держала дерево сбалансированным: добавь значение, а потом на обратном пути выровняй тот узел, который перекосился. Удаление устроено так же, но с концом сложнее. Сначала делаешь обычное удаление из BST (то самое из шага 70: лист, один ребёнок или два ребёнка через in-order преемника), а потом выравниваешь путь наверх. Трудность в том, что удаление узла может укоротить целое поддерево. Укороченное поддерево может перекосить своего родителя на 2. Починка родителя, в свою очередь, может перекосить его родителя, и так далее. Поэтому вставка останавливается после одной починки, а удаление проверяет и вращает на каждом уровне вплоть до корня.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи, где нужно отсортированное множество с удалением, например брать наименьший свободный элемент или держать только последние k значений. Удаление из AVL-дерева оставляет каждую операцию на O(log n).
Держи свободные места в дереве, reserve удаляет самый левый узел, а unreserve вставляет место обратно.
Храни цены в дереве со счётчиком у каждой, исправление удаляет старую цену и вставляет новую, а минимум и максимум лежат на двух краях.
Держи в дереве последние indexDiff значений, удаляй то, что выходит из окна, и ищи наименьшее значение не меньше nums[i] минус valueDiff.