Функцията за изтриване се използва за изтриване на посочения възел от дърво за двоично търсене. Трябва обаче да изтрием възел от дърво за двоично търсене по такъв начин, че свойството на дърво за двоично търсене да не се нарушава. Има три ситуации на изтриване на възел от двоично дърво за търсене.
Възелът, който трябва да бъде изтрит, е листов възел
Това е най-простият случай, в този случай заменете листовия възел с NULL и просто освободете разпределеното пространство.
В следващото изображение изтриваме възел 85, тъй като възелът е листов възел, следователно възелът ще бъде заменен с NULL и разпределеното пространство ще бъде освободено.
Възелът, който трябва да бъде изтрит, има само едно дете.
В този случай заменете възела с неговия дъщерен възел и изтрийте дъщерния възел, който сега съдържа стойността, която трябва да бъде изтрита. Просто го заменете с NULL и освободете разпределеното място.
В следващото изображение възел 12 трябва да бъде изтрит. Има само едно дете. Възелът ще бъде заменен със своя дъщерен възел и замененият възел 12 (който сега е листен възел) просто ще бъде изтрит.
Възелът, който трябва да бъде изтрит, има две деца.
Това е малко сложен случай в сравнение с други два случая. Въпреки това, възелът, който трябва да бъде изтрит, се заменя с неговия наследник или предшественик в реда на реда рекурсивно, докато стойността на възела (за изтриване) бъде поставена на листа на дървото. След процедурата заменете възела с NULL и освободете разпределеното пространство.
В следващото изображение трябва да се изтрие възел 50, който е основният възел на дървото. Обхождането по ред на дървото, дадено по-долу.
6, 25, 30, 50, 52, 60, 70, 75.
замени 50 с неговия наследник по ред 52. Сега 50 ще бъде преместено в листа на дървото, което просто ще бъде изтрито.
Алгоритъм
Изтриване (ДЪРВО, ЕЛЕМЕНТ)
Напишете „елементът не е намерен в дървото“ ELSE IF ITEM DATA
Изтриване (ДЪРВО->НАЛЯВО, ЕЛЕМЕНТ)
ИНАЧЕ, АКО ЕЛЕМЕНТ > ДЪРВО -> ДАННИ
Изтриване (ДЪРВО -> ДЯСНО, ЕЛЕМЕНТ)
ИНАЧЕ АКО ДЪРВО -> ЛЯВО И ДЪРВО -> ДЯСНО
SET TEMP = findLargestNode(TREE -> LEFT)
НАСТРОЙКА ДЪРВО -> ДАННИ = TEMP -> ДАННИ
Изтриване (ДЪРВО -> НАЛЯВО, TEMP -> ДАННИ)
ДРУГО
ЗАДАДЕТЕ ТЕМПЕРАТУРА = ДЪРВО
АКО ДЪРВО -> ЛЯВО = NULL И ДЪРВО -> ДЯСНО = NULL
SET TREE = NULL
ИНАЧЕ АКО ДЪРВО -> НАЛЯВО != NULL
ЗАДАДЕ ДЪРВО = ДЪРВО -> НАЛЯВО
ДРУГО
НАСТРОЙ ДЪРВО = ДЪРВО -> НАДЯСНО
[КРАЙ НА АКО]
СВОБОДНА ТЕМП
[КРАЙ НА АКО]
функция:
void deletion(Node*& root, int item) { Node* parent = NULL; Node* cur = root; search(cur, item, parent); if (cur == NULL) return; if (cur->left == NULL && cur->right == NULL) { if (cur != root) { if (parent->left == cur) parent->left = NULL; else parent->right = NULL; } else root = NULL; free(cur); } else if (cur->left && cur->right) { Node* succ = findMinimum(cur- >right); int val = succ->data; deletion(root, succ->data); cur->data = val; } else { Node* child = (cur->left)? Cur- >left: cur->right; if (cur != root) { if (cur == parent->left) parent->left = child; else parent->right = child; } else root = child; free(cur); } } Node* findMinimum(Node* cur) { while(cur->left != NULL) { cur = cur->left; } return cur; }