Удаление элементов из AVL-дерева

Удаление элементов считается более трудоёмкой процедурой по сравнению с включением. При удалении выделяют три случая:

ü удаляемый элемент – лист;

ü удаляемый элемент – вершина с одним поддеревом;

ü удаляемый элемент – вершина с двумя поддеревьями.

Наибольший интерес представляет третий случай, т.к. при этом имеется трудность – нельзя указать одной ссылкой на два направления. В этом случае удаляемый элемент необходимо заменить: либо на самый левый элемент правого поддерева либо на самый правый элемент левого поддерева (другими словами, на максимальный элемент левого поддерева или на минимальный элемент правого поддерева). При удалении также осуществляется изменение указателей, пересчёт баланса и, в случае необходимости, балансировка.