Видалення з дерева бінарного пошуку
При видаленні необхідно розглянути три випадки [3]:
1. Якщо видаляється вузол не має синів, то він видаляється без подальшої настройки дерева (рис. 4.6 (а)).
2. Якщо видаляється вузол має тільки одне піддерево, то його єдиний син може бути поміщений вгору, щоб зайняти його місце (рис. 7.6 (б)).
3. Якщо видаляється вузол p має два піддерева, то його приймач s в симетричному порядку (або його попередник в симетричному порядку) повинен зайняти його місце. Нащадок в симетричному порядку не може мати лівого піддерева (оскільки, якщо б він мав його, лівий нащадок був би приймачем p в симетричному порядку). Таким чином, правий син елемента s може бути переміщений вгору, щоб зайняти місце s (рис. 4.6 (в)).
Мал. 4.6. Видалення вузлів з дерева бінарного пошуку
а - видалення вузла з ключем 15;
б - видалення вузла з ключем 5;
в - видалення вузла з ключем 11
У наводиться нижче алгоритмі дерево залишається незмінним, якщо в ньому не існує вузла з ключем key.
// Пошук вузла з ключем key. Встановити p так, щоб воно вказувало
// на даний вузол, а q - на його батька, якщо він існує
while ((p! = NULL) (P-> k! = Key))
if (key
cout<<”такого ключа нет в дереве. Дерево остается не измененным \n”;
// Установити в змінну v вузол, який замінить p.
// видаляється вузол має максимум одного сина
if (p-> left == NULL) v = p-> right;
else (if p-> right == NULL) v = p-> left;
else // вузол p має двох синів
// Установити в v наступника p в симетричному порядку,
// а в змінну t - батька змінної v
s = v-> left; // s - лівий син v
// У цей момент змінна v є наступником вузла p
// в симетричному порядку
// p є батьком змінної v, і v = t-> left.
// Видалити вузол v з його поточної позиції і замінити його на правого сина вузла v
// налаштувати синів v так, щоб вони були синами p
// вставити вузол v в позицію, яку раніше займав вузол p
if (q == NULL) // вузол p був коренем дерева