Удаление из дерева бинарного поиска

При удалении необходимо рассмотреть три случая [3]:

1. Если удаляемый узел не имеет сыновей, то он удаляется без дальнейшей настройки дерева (рис. 4.6 (а)).

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

3. Если удаляемый узел p имеет два поддерева, то его приемник sв симметричном порядке (или его предшественник в симметричном порядке) должен занять его место. Потомок в симметричном порядке не может иметь левого поддерева (поскольку, если бы он имел его, левый потомок был бы приемником pв симметричном порядке). Таким образом, правый сын элемента sможет быть перемещен вверх, чтобы занять место s (рис. 4.6 (в)).

Рис. 4.6. Удаление узлов из дерева бинарного поиска

а — удаление узла с ключом 15;

б — удаление узла с ключом 5;

в — удаление узла с ключом 11

В приводимом ниже алгоритме дерево остается неизменным, если в нем не существует узла с ключом key.

…

p=tree;

q=NULL;

// Поиск узла с ключом key. Установить p так, чтобы оно указывало

// на данный узел, а q — на его отца, если он существует

while( (p!=NULL) && (p->k!=key))

{

q=p;

if( key<p->k) p=p->left;

else p=p->right;

}

if (p==NULL)

{

cout<<”такого ключа нет в дереве. Дерево остается не измененным \n”;

return;

}

// Установить в переменную v узел, который заменит p.

// Удаляемый узел имеет максимум одного сына

if (p->left==NULL) v=p->right;

else (if p->right==NULL) v=p->left;

else // узел p имеет двух сыновей

// Установить в v преемника p в симметричном порядке,

// а в переменную t — отца переменной v

t=p;

v=p->right;

s=v->left; // s — левый сын v

while (s!=NULL)

{

t=v;

v=s;

s=v->left;

}

// В этот момент переменная v является преемником узла p

// в симметричном порядке

if (t!=p)

// p является отцом переменной v, и v=t->left.

// Удалить узел v из его текущей позиции и заменить его на правого сына узла v

t->left=v->right;

// настроить сыновей v так, чтобы они были сыновьями p

v->right=p->right;

v->left=p->left;

// вставить узел v в позицию, которую ранее занимал узел p

if (q==NULL) // узел p был корнем дерева

tree=v;

else if( p==q->left) q->left=v;

else q->right=v;

delete v;

…