21
правка
Изменения
Нет описания правки
=== Удаление ===
Для удаления узла из бинарного дерева поиска нужно рассмотреть три возможные ситуации. Если у узла нет дочерних узлов, то у его родителя нужно просто заменить указатель на null. Если у узла есть только один дочерний узел, то нужно создать новую связь между родителем удаляемого узла и его дочерним узлом. Наконец, если у узла два дочерних узла, то нужно найти следующий за ним элемент(у этого элемента не будет левого потомка) и переместить его на место удаляемого узла.
{| border="1" cellpadding="5" cellspacing="0"
!случай
!Иллюстрация
|-
|'''Удаление листа'''
| [[Файл:Bst_del1.png|250px]]
|-
|'''Удаление узла с одним дочерним узлом'''
| [[Файл:Bst_del2.png|250px]]
|-
|'''Удаление узла с двумя дочерними узлами'''
| [[Файл:Bst_del3.png|250px]]
|-
|'''Удаление корня'''
| [[Файл:Bst_del4.png|250px]]
|}
Tree_delete(root t, root z) // корень дерева, вставляемый элемент
root x, y;
