Алгоритм витирання вузла у бінарному дереві пошуку

Алгоритм витирання вузла повинен передбачати обробку трьох ситуацій:

1) вузол для витирання – лист;

2) вузол для витирання має одного нащадка;

3) вузол для витирання має двох нащадків.

В кожному з цих випадків програмне витирання вузла здійснюється через створення на нього тимчасового вказівника, а потім – звільнення пам’яті, на яку вказує тимчасовий вказівник.

В першому випадку вузол витирається, а вказівник на нього у батьківському по відношенню до витираємого вузлі встановлюємо у NULL.

В другому випадку вказівник на витираємий вузол у його батьківському вузлі встановлюється на нащадка витираємого, а сам вузол витирається.

В третьому випадку на місце витираємого вузла треба вибрати інший вузол. Це буде вузол з найбільшим значенням, але меншим за витираємий. Або навпаки – найменший вузол, але більший за витираємий. Зрозуміло, що ці випадки є симетричними відносно понять “лівий” – “правий” та “менше” – “більше”. Тому розглянемо тільки, наприклад, перший випадок, а алгоритм другого утвориться з першого заміною термінів “лівий” на “правий”, а “менше” на “більше”.

Отже, найбільший вузол, але менший за витираємий, знаходитиметься, згідно означення бінарного дерева пошуку, у самому правому вузлі лівого піддерева витираємого вузла. Тобто здійснюватимемо спуск по лівому піддереву вправо, поки не зустрінемо вузол, у якого вказівник на праве піддерево rPtr == NULL. Цей вузол буде або листом або матиме тільки лівого нащадка.

Якщо вузол лист, то:

1) зберігаємо в тимчасовому вказівнику адресу витираємого вузла;

2) вказівник у батьківському по відношенню до витираємого вузла встановити на заміщаючий вузол;

3) вказівник у батьківському по відношенню до заміщаючого вузла встановити в NULL;

4) вказівник на праве піддерево в заміщаючому вузлі встановити на праве піддерево витираємого;

5) вказівник на ліве піддерево в заміщаючому вузлі встановити на ліве піддерево витираємого;

6) звільнити пам’ять (витерти тимчасовий вказівник).

Якщо вузол має лівого нащадка, то:

1) зберігаємо в тимчасовому вказівнику адресу витираємого вузла;

2) вказівник у батьківському по відношенню до витираємого вузла встановити на заміщаючий вузол;

3) вказівник у батьківському по відношенню до заміщаючого вузла встановити в налівого нащадка заміщаючого;

4) вказівник на праве піддерево в заміщаючому вузлі встановити на праве піддерево витираємого;

5) вказівник на ліве піддерево в заміщаючому вузлі встановити на ліве піддерево витираємого;

6) звільнити пам’ять (витерти тимчасовий вказівник).