Модели и структуры данных





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



ОПЕРАЦИЯ УДАЛЕНИЯ ИЗ СБАЛАНСИРОВАННОГО ДЕРЕВА.

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

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

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

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

  • 1. Следовать по дереву, пока не будет найден удаляемый элемент.
  • 2. Удалить найденный элемент, не разрушив структуры связей между элементами.
  • 3. Произвести балансировку полученного дерева и откорректировать показатели сбалансированности.

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

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

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









Содержание    Назад    Вперед