Funcția de ștergere este utilizată pentru a șterge nodul specificat dintr-un arbore de căutare binar. Cu toate acestea, trebuie să ștergem un nod dintr-un arbore de căutare binar în așa fel încât proprietatea arborelui de căutare binar să nu încalce. Există trei situații de ștergere a unui nod din arborele de căutare binar.
Nodul care trebuie șters este un nod frunză
Este cel mai simplu caz, în acest caz, înlocuiți nodul frunză cu NULL și eliberați simplu spațiul alocat.
În imaginea următoare, ștergem nodul 85, deoarece nodul este un nod frunză, prin urmare nodul va fi înlocuit cu NULL și spațiul alocat va fi eliberat.
Nodul de șters are un singur copil.
În acest caz, înlocuiți nodul cu copilul său și ștergeți nodul copil, care conține acum valoarea care urmează să fie șters. Pur și simplu înlocuiți-l cu NULL și eliberați spațiul alocat.
În imaginea următoare, nodul 12 urmează să fie șters. Are un singur copil. Nodul va fi înlocuit cu nodul său copil, iar nodul înlocuit 12 (care este acum nodul frunză) va fi pur și simplu șters.
Nodul de șters are doi copii.
Este un caz puțin complex în comparație cu alte două cazuri. Cu toate acestea, nodul care urmează să fie șters, este înlocuit cu succesorul sau predecesorul său în ordine recursiv până când valoarea nodului (de șters) este plasată pe frunza arborelui. După procedură, înlocuiți nodul cu NULL și eliberați spațiul alocat.
În imaginea următoare, nodul 50 urmează să fie șters, care este nodul rădăcină al arborelui. Parcurgerea în ordine a arborelui prezentată mai jos.
6, 25, 30, 50, 52, 60, 70, 75.
înlocuiți 50 cu succesorul său în ordine 52. Acum, 50 va fi mutat în frunza arborelui, care va fi pur și simplu șters.
Algoritm
Ștergeți (ARBOC, ARTICOL)
Scrieți „articolul nu a fost găsit în arbore” ELSE IF ARTICOL DATE
Șterge (ARBOC->STÂNGA, ARTICOL)
ELSE IF ARTICOL > ARBOR -> DATE
Șterge (ARBOC -> DREAPTA, ARTICOL)
ELSE IF TREE -> STÂNGA ȘI TREE -> DREAPTA
SET TEMP = findLargestNode(TREE -> LEFT)
SET TREE -> DATA = TEMP -> DATA
Șterge (ARBOC -> STÂNGA, TEMP -> DATE)
ALTE
SET TEMP = TREE
IF TREE -> LEFT = NUL ȘI TREE -> RIGHT = NULL
SET TREE = NUL
ELSE IF TREE -> LEFT != NULL
SET TREE = TREE -> LEFT
ALTE
SET TREE = TREE -> DREAPTA
[SFÂRȘITUL IF]
TEMPERATURA GRATUITA
[SFÂRȘITUL IF]
Funcţie:
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; }