Удаление узла из авл‑дерева

В 6 главе было показано, что удалить элемент из упорядоченного дерева сложнее, чем вставить его. Если удаляемый элемент имеет всего одного потомка, можно заменить его этим потомком, сохранив при этом порядок дерева. Если у дерева два дочерних узла, то он заменяется на самый правый узел в левой ветви дерева. Если у этого узла существует левый потомок, то этот левый потомок также занимает его место.

======166

Так как АВЛ‑деревья являются особым типом упорядоченных деревьев, то для них нужно выполнить те же самые шаги. Тем не менее, после их завершения необходимо вернуться назад по дереву, чтобы убедиться в том, что оно осталось сбалансированным. Если найдется узел, для которого не выполняется свойство АВЛ‑деревьев, то нужно выполнить для балансировки дерева соответствующее вращение. Хотя это те же самые вращения, которые использовались раньше для вставки узла в дерево, они применяются в других случаях.

Левое вращение

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

Нижний уровень поддерева T₂ закрашен серым цветом, чтобы показать, что поддерево T_B либо уравновешено (T₂ и T₃ имеют одинаковую высоту), либо его правая половина выше (T₃ выше, чем T₂). Другими словами, закрашенный уровень может существовать в поддереве T₂ или отсутствовать.

Если T₂ и T₃ имеют одинаковую высоту, то высота поддерева T_X с корнем в узле X не меняется после удаления узла. Высота T_X при этом остается равной высоте поддерева T₂ плюс 2. Так как эта высота не меняется, то дерево выше этого узла остается сбалансированным.

Если T₃ выше, чем T₂, то поддерево T_X становится ниже на единицу. В этом случае, дерево может быть несбалансированным выше узла X, поэтому необходимо продолжить проверку дерева, чтобы определить, выполняется ли свойство АВЛ‑деревьев для предков узла X.

Вращение вправо‑влево

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

Если левое или правое поддеревья T₂ или T₃ выше, то вращение вправо‑влево приведет к балансировке поддерева T_X, и уменьшит при этом высоту T_X на единицу. Это значит, что дерево выше узла X может быть несбалансированным, поэтому необходимо продолжить проверку выполнения свойства АВЛ‑деревьев для предков узла X.

@Рис. 7.12. Левое вращение при удалении узла

========167

@Рис. 7.13. Вращение вправо‑влево при удалении узла

Другие вращения

Остальные вращения выполняются аналогично. В этом случае удаляемый узел находится в правом поддереве узла X. Эти четыре вращения — те же самые, которые использовались для балансировки дерева при вставке узла, за одним исключением.

Если новый узел вставляется в дерево, то первое выполняемое вращение осуществляет балансировку поддерева T_X, не изменяя его высоту. Это значит, что дерево выше узла T_X будет при этом оставаться сбалансированным. Если же эти вращения используются после удаления узла из дерева, то вращение может уменьшить высоту поддерева T_X на единицу. В этом случае, нельзя быть уверенным, что дерево выше узла X осталось сбалансированным. Нужно продолжить проверку выполнения свойства АВЛ‑деревьев вверх по дереву.