Операция удаления из сбалансированного дерева

Удаление элемента из сбалансированного дерева является еще более сложной операцией чем включение, так как может удаляться не только какой-либо из листьев, но и любой узел (в том числе и корень). Поэтому при удалении необходимо правильно изменить структуру связей между элементами, а затем произвести балансировку полученного дерева.

В результате удаления какого-либо узла могут возникнуть ситуации аналогичные тем, что возникают при добавлении элемента:

· 1. Вершина была лево- или правоперевешивающей, а теперь стала сбалансированной.

· 2. Вершина была сбалансированной, а стала лево- или правоперевешивающей.

· 3. Вершина была перевешивающей, а вставка новой вершины в перевешивающее поддерево создала несбалансированное поддерево - привело к появлению критической вершины. Необходимо провести балансировку.

В общем процесс удаления элемента состоит из следующих этапов:

· 1. Следовать по дереву, пока не будет найден удаляемый элемент.

· 2. Удалить найденный элемент, не разрушив структуры связей между элементами.

· 3. Произвести балансировку полученного дерева и откорректировать показатели сбалансированности.

На каждом шаге должна передаваться информация о том, уменьшилась ли высота поддерева (из которого произведено удаление). Поэтому мы введем в список параметров переменную h, означающую "высота поддерева уменьшилась".

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

Для балансировки дерева после удаления используем две (симметричные) операции балансировки: Balance_R используется, когда уменьшается высота правого поддерева, а Balance_L - левого поддерева. Процедуры балансировки используют те же способы (LL- LR- RL- и RR-повороты), что и в процедуре вставки элемента.