Удаление вершин из СДП

Если удаляемая вершина не имеет поддеревьев:
Если на удаляемой вершине одно поддерево:
Если вершина имеет два поддерева:

Из этого дерева нужно удалить вершину 5, на её место можно поставить либо 4, либо 6.

Правила удаления:
а) На место удаляемой вершины ставится наибольшая вершина из её левого поддерева, т.е. самая правая вершина из левого поддерева, не имеющая правого поддерева.
б) На место удаляемой вершины ставится наименьшая вершина из её правого поддерева, т.е. самая левая вершина из её правого поддерева, не имеющая левого поддерева.
Будем строить алгоритмы на правиле «а»

B 9 2 4 1 7 E F A D C 3 5 8 6

B 9 2 4 1 7 E F A D C 3 5 8 6

B 9 2 4 1 7 E F A D C 3 5 8 6

B 9 2 4 1 7 E F A D C 3 5 8 6

B 9 2 4 1 7 E F A D C 3 5 8 6

B 9 2 4 1 7 E F A D C 3 5 8 6

B 9 2 4 1 7 E F A D C 3 5 8 6

B 9 2 4 1 7 E F A D C 3 5 8 6

B 9 2 4 1 7 E F A D C 3 5 8 6

B 9 2 4 1 7 E F A D C 3 5 8 6

B 9 2 4 1 7 E F A D C 3 5 8 6

B 9 2 4 1 7 E F A D C 3 5 8 6

B 9 2 4 1 7 E F A D C 3 5 8 6

p - адрес адреса удаляемой вершины
q - адрес удаляемой вершины
p
q
S
r
1
2
3
4

Удаление ( D, *Root)
p=&Root
DO (*p ≠ NULL) // поиск элемента
IF (D<(*p)-->Data) p:=&((*p)-->Left)
ELSE IF (D>((*p)-->Data) p:=&((*p)-->Right)
ELSE OD {данные есть в дереве}
FI
OD
IF (*p ≠ NULL)
q:=*p
IF (q-->Left=NULL ) *p:=q-->Right;
ELSE IF (q-->Right=NULL ) *p:=q-->Left;
ELSE /*2 поддерева*/
r:=q-->Left ; S:=q;