Сбалансированные деревья поиска. Исключение: балансировка после удаления

Модуль "Деревья поиска" • урок 5 из 8 • ~7 минут

Суть урока. Удаление узла из АВЛ-дерева сначала выполняется как удаление из обычного дерева поиска. Затем производится ребалансировка. В отличие от включения, одного поворота может не хватить - может возникнуть "эффект домино", из-за которого придется выполнять балансировку, поднимаясь по всему пути вплоть до корня (до O(log N) поворотов в худшем случае).

Нарушение баланса при исключении

Удаление (исключение) узла из АВЛ-дерева технически является более сложной задачей, чем вставка. Сначала узел удаляется по правилам обычного двоичного дерева поиска (если у узла два потомка, он заменяется на самый правый узел левого поддерева или самый левый правого).

Удаление узла приводит к уменьшению высоты той ветви, из которой он был изъят. Это может нарушить критерий АВЛ-баланса (разность высот становится +2 или -2) для родительского узла. Как и при вставке, для восстановления структуры применяются те же четыре типа поворотов.

Сбалансированные деревья поиска. Исключение: эффект домино

Принципиальное отличие удаления от вставки заключается в том, что одного поворота может оказаться недостаточно. При вставке один поворот возвращал поддереву его первоначальную высоту, предотвращая нарушение баланса у узлов, расположенных выше.

При удалении же балансирующий поворот может еще больше уменьшить общую высоту текущего поддерева. Из-за этого может нарушиться баланс у его родительского узла. Возникает эффект домино.

Поэтому алгоритм балансировки при исключении должен последовательно возвращаться от точки удаления вверх, к корню дерева, проверяя балансы узлов и выполняя повороты на каждом шаге, где это необходимо. В худшем случае потребуется выполнить O(log N) поворотов вплоть до самого корня дерева.

Разница между включением и исключением: после включения высота поддерева возвращается к прежней, а после исключения падает, и проверку приходится вести до корня
Вся разница в одной строке: вернулась высота поддерева или нет

Визуализация: удаление, после которого нужен поворот

На схеме удаляют один-единственный лист 90. Правая ветвь становится короче, баланс корня 50 уходит в -2, и вернуть дерево в норму удается только большим поворотом. Обратите внимание на высоту: она была равна 4, а стала 3 - именно из-за этого проверку приходится продолжать выше.

Сбалансированные деревья поиска. Исключение: после удаления листа 90 баланс корня 50 стал -2, а большой поворот уменьшил высоту дерева с 4 до 3
Удален один лист - а перестроилось все дерево, и высота упала на единицу
А как в Python? В C++ рекурсивный "подъем" вверх к корню при удалении элемента в std::map или std::set обрабатывается итеративно. Для этого в каждом узле хранится указатель на родительский узел (parent pointer). Это позволяет избежать накладных расходов на рекурсию и делает откат по пути поиска быстрым и эффективным. В Python, если мы реализуем исключение из АВЛ-дерева через рекурсивную функцию, возврат из рекурсии (команды return) автоматически обеспечивает нам "обратный путь" к корню. На каждом шаге возврата мы пересчитываем высоты и вызываем балансировку.

Коротко: главное

  • Исключение узла в АВЛ-дереве сначала выполняется как обычное удаление из двоичного дерева поиска.
  • Удаление узла уменьшает высоту ветви, что может нарушить АВЛ-баланс родительских узлов.
  • В отличие от включения, после выполнения балансирующего поворота общая высота поддерева может уменьшиться. Поэтому одного поворота может не хватить: необходимо проследовать по всему пути до корня и выполнить балансировку везде, где она нарушена.

Проверьте себя

Почему при удалении элемента из АВЛ-дерева может потребоваться больше одного поворота (каскадная балансировка), тогда как при вставке достаточно лишь одного?

Как вам урок? Спасибо за отзыв!