Алгоритмизации

• Название: Алгоритмизации
• Дата: 27.09.2022
• Размер: 1.15 Mb.
• Имя файла: 12_100229_1_124427 (1).docx
• Тип: Документы; #700459
• страница: 38 из 67

Удалениеузла

При удалении узла из дерева возможны три ситуации в зависимости от того, сколько сыновей (потомков) имеет удаляемый узел.

1. 
   Удаляемый узел является листом – просто удаляем ссылку на него. Приведем пример схемы удаления листа с ключом key:
   

Получим

5

NULL⁸

2. 
   Удаляемый узел имеет только одного потомка, т.е. из удаляемого узла выходит ровно одна ветвь. Пример схемы удаления узла key, имеющего одного сына:
   

Получим

NULL

3. 
   Удаление узла, имеющего двух сыновей, значительно сложнее рассмотренных выше. Если key– удаляемый узел, то его следует заменить узлом w, который содержит либо наибольший ключ (самый правый, у которого указатель Rightравен NULL) в левом поддереве, либо наименьший ключ (самый левый, у которого указатель Left равен NULL) в правом поддереве.
   

Используя первое условие, находим узел w, который является самым правым узлом поддерева key, у него имеется только левый сын:

key

7

Удалить узел (7)

6

Получим

^{4 9} 4 9

^{2 6 8 10} 2 ⁵ 8 ¹⁰

⁵ NULL

NULL

В построенном ранее дереве удалим узел key(6). Используем второе условие, т.е. ищем самый левый узел в правом поддереве – это узел w (указатель Left равен NULL):

Левое поддерево (Left)
5

17

key

6


9




w

7 12
Правое поддерево (Right)

23

8 11
Функция удаления узла по заданному ключу keyможет иметь вид

Tree* Del(Tree *Root, int key) {

Tree *Del, *Prev_Del, *R, *Prev_R;

// Del, Prev_Del– удаляемый элемент и его предыдущий (родитель);

// R, Prev_R– элемент, на который заменяется удаленный, и его родитель; Del = Root;

Prev_Del = NULL;

// ===== Поиск удаляемого элемента и его родителя по ключу key===== while (Del != NULL && Del -> info != key) {

Prev_Del = Del;

if (Del->info > key) Del = Del->Left; else Del = Del->Right;

}

if (Del == NULL) { // Элемент не найден

puts("\n NO Key!"); return Root;

}

// ============ Поиск элемента Rдля замены ================= if (Del -> Right == NULL) R = Del->Left;

else

if (Del -> Left == NULL) R = Del->Right; else {

// Ищем самый правый узел в левом поддереве

Prev_R = Del; R = Del->Left;

while (R->Right != NULL) { Prev_R = R;

R = R->Right;

}

// Нашли элемент для замены Rи его родителя Prev_R

if( Prev_R == Del)

R->Right = Del->Right;

else {

R->Right = Del->Right; Prev_R->Right = R->Left; R->Left = Prev_R;

}

}

if (Del== Root) Root = R; // Удаляя корень, заменяем его на R

else

// ПоддеревоRприсоединяем к родителю удаляемого узла

if (Del->info < Prev_Del->info) Prev_Del->Left = R; // на левую ветвь

else Prev_Del->Right = R; // на правую ветвь

printf("\n Delete element %d \n", Del->info); free(Del);

return Root;

}

Участок программы с обращением к данной функции будет иметь вид

…

printf("\n Input Del Info : "); scanf(“%d”, &key);

Root = Del(Root, key);

…