Удаление узлов

Также как и вставку узла, его удаление удобно задать рекурсивно. Пусть x – удаляемый узел, тогда если x – лист (терминальный узел), то алгоритм удаления сводиться к простому исключению узла x, и подъему к корню с переопределением balance factor’ов узлов. Если же x не является листом, то он либо имеет правое поддерево, либо не имеет его. Во втором случае, из свойства АВЛ-дерева, следует, что левое поддерево имеет высоту 1, и здесь алгоритм удаления сводиться к тем же действиям, что и при терминальном узле. Остается ситуация когда у x есть правое поддерево. В таком случае нужно в правом поддереве отыскать следующий по значению за x узел y, заменить x на y, и рекурсивно вернуться к корню, переопределяя коэффициенты сбалансированности узлов. Из свойства двоичного дерева поиска следует, что узел y имеет наименьшее значение среди всех узлов правого поддерева узла x.

Для программной реализации операции удаления узла опишем функцию Delete:

 

Node *Delete(Node *x, int k)

{

if (!x) return 0;

if (k<x->key) x->left=Delete(x->left, k);

else if (k>x->key) x->right=Delete(x->right, k);

else

{

Node *y=x->left;

Node *z=x->right;

delete x;

if (!z) return y;

Node* min=SearchMin(z);

min->right=DeleteMin(z);

min->left=y;

return Balance(min);

}

return Balance(x);

}

 

Из нее вызываются вспомогательные функции: SearchMin и DeleteMin. Первая ищет минимальный элемент в правом поддереве, вторая удаляет его. Опишем эти вспомогательные функции:

 

Node *SearchMin(Node *x)

{

if (x->left) return SearchMin(x->left);

else return x;

}

 

Node *DeleteMin(Node *x)

{

if (x->left==0) return x->right;

x->left=DeleteMin(x->left);

return Balance(x);

}

 

Операция удаления реализуется определенно сложнее, чем операция добавления. Да и последствия ее выполнения могут потребовать поворота в каждом узле. Но какова вероятность возникновения ситуации, при которой появится потребность в поворотах? Этим вопросом задается Никлаус Вирт в своей книге «Алгоритмы и структуры», и отвечает на него: «Удивительный результат эмпирических проверок показал, что в то время как один поворот вызывается приблизительно каждыми двумя включениями, тем не менее, при удалении мы имеем дело с одним поворотом на целых пять удалений».

Раздел II

АЛГОРИТМЫ