Naikinimo funkcija naudojama nurodytam mazgui ištrinti iš dvejetainio paieškos medžio. Tačiau turime ištrinti mazgą iš dvejetainio paieškos medžio taip, kad nepažeistų dvejetainio paieškos medžio savybių. Yra trys mazgo ištrynimo iš dvejetainės paieškos medžio situacijos.
Mazgas, kurį reikia ištrinti, yra lapo mazgas
Tai paprasčiausias atvejis, šiuo atveju lapo mazgą pakeiskite NULL ir atlaisvinkite paskirtą vietą.
jsp
Toliau pateiktame paveikslėlyje mes ištriname mazgą 85, nes mazgas yra lapinis mazgas, todėl mazgas bus pakeistas NULL ir bus atlaisvinta skirta vieta.
Ištrintinas mazgas turi tik vieną antrinį elementą.
Tokiu atveju pakeiskite mazgą antriniu ir ištrinkite antrinį mazgą, kuriame dabar yra reikšmė, kurią reikia ištrinti. Tiesiog pakeiskite jį NULL ir atlaisvinkite skirtą vietą.
Toliau pateiktame paveikslėlyje 12 mazgas turi būti ištrintas. Turi tik vieną vaiką. Mazgas bus pakeistas antriniu mazgu, o pakeistas mazgas 12 (kuris dabar yra lapo mazgas) bus tiesiog ištrintas.
Trintinas mazgas turi du vaikus.
Tai yra šiek tiek sudėtingas atvejis, palyginti su kitais dviem atvejais. Tačiau mazgas, kuris turi būti panaikintas, pakeičiamas jo eilės įpėdiniu arba pirmtaku rekursyviai, kol mazgo reikšmė (nutrinama) dedama ant medžio lapo. Po procedūros pakeiskite mazgą NULL ir atlaisvinkite skirtą vietą.
Toliau pateiktame paveikslėlyje 50 mazgas turi būti panaikintas, kuris yra šakninis medžio mazgas. Žemiau pateiktas medžio perėjimas pagal eilę.
6, 25, 30, 50, 52, 60, 70, 75.
tvarka
pakeiskite 50 eilės įpėdiniu 52. Dabar 50 bus perkelta į medžio lapą, kuris bus tiesiog ištrintas.
Algoritmas
Ištrinti (TREE, ITEM)
Rašykite „prekė nerasta medyje“ ELSE IF PREKĖS DUOMENYS
Ištrinti (MEDIS -> KAIRĖ, ITEM)
KITA, JEI PREKĖ > MEDIS -> DUOMENYS
Ištrinti (MEDIS -> DEŠINĖ, ITEM)
KITAIP, JEI MEDIS -> KAIRĖ IR MEDIS -> DEŠINĖ
NUSTATYTI TEMP = rasti didžiausią mazgą (MEDIS -> KAIRĖ)
NUSTATYTI MEDĮ -> DUOMENYS = TEMP -> DUOMENYS
Ištrinti (MEDIS -> KAIRĖ, TEMP -> DUOMENYS)
KITAS
NUSTATYTI TEMP = MEDIS
JEI MEDIS -> KAIRĖ = NULIS IR MEDIS -> DEŠINĖ = NULL
NUSTATYTI MEDĮ = NULL
ELSE JEI MEDIS -> KAIRĖS != NULIS
NUSTATYTI MEDĮ = MEDIS -> KAIRĖ
KITAS
NUSTATYTI MEDĮ = MEDIS -> TEISINĖ
[JEI PABAIGA]
NEMOKAMA TEMP
[JEI PABAIGA]
Funkcija:
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; }