Funkcia Delete sa používa na vymazanie zadaného uzla z binárneho vyhľadávacieho stromu. Musíme však vymazať uzol z binárneho vyhľadávacieho stromu takým spôsobom, aby sa neporušila vlastnosť binárneho vyhľadávacieho stromu. Existujú tri situácie vymazania uzla z binárneho vyhľadávacieho stromu.
Uzol, ktorý sa má odstrániť, je listový uzol
Je to najjednoduchší prípad, v tomto prípade nahraďte listový uzol NULL a jednoducho uvoľnite pridelené miesto.
Na nasledujúcom obrázku odstraňujeme uzol 85, keďže uzol je listový uzol, preto bude uzol nahradený NULL a uvoľní sa pridelené miesto.
Uzol, ktorý sa má odstrániť, má iba jedného potomka.
V tomto prípade nahraďte uzol jeho potomkom a vymažte dcérsky uzol, ktorý teraz obsahuje hodnotu, ktorá sa má vymazať. Jednoducho ho nahraďte NULL a uvoľnite pridelené miesto.
Na nasledujúcom obrázku má byť uzol 12 vymazaný. Má len jedno dieťa. Uzol bude nahradený svojim dcérskym uzlom a nahradený uzol 12 (ktorý je teraz koncovým uzlom) bude jednoducho vymazaný.
Uzol, ktorý sa má odstrániť, má dve deti.
V porovnaní s ďalšími dvoma prípadmi je to trochu zložitý prípad. Avšak uzol, ktorý sa má vymazať, je nahradený svojim následníkom alebo predchodcom v poradí rekurzívne, kým sa hodnota uzla (ktorá sa má vymazať) umiestni na list stromu. Po vykonaní procedúry nahraďte uzol NULL a uvoľnite pridelený priestor.
Na nasledujúcom obrázku sa má vymazať uzol 50, ktorý je koreňovým uzlom stromu. Prechod stromu v poradí uvedený nižšie.
6, 25, 30, 50, 52, 60, 70, 75.
nahraďte 50 jeho následníkom v poradí 52. Teraz sa 50 presunie na list stromu, ktorý sa jednoducho vymaže.
Algoritmus
Odstrániť (TREE, ITEM)
Napíšte 'položka sa nenašla v strome' INAK, AK ÚDAJE O položke
Odstrániť (STROME->LEFT, ITEM)
ELSE IF POLOŽKA > STROM -> ÚDAJE
Odstrániť (STROMEČ -> VPRAVO, POLOŽKA)
ELSE IF STROM -> ĽAVÝ A STROM -> PRAVÝ
SET TEMP = nájdi najväčší uzol(STROMEČ -> VĽAVO)
SET STROM -> DATA = TEMP -> DATA
Odstrániť (STRM -> VĽAVO, TEPLOTA -> ÚDAJE)
ELSE
SET TEMP = STROM
AK STROM -> LEFT = NULL A STROM -> RIGHT = NULL
SET STROM = NULL
ELSE IF STROM -> LEFT != NULL
SET STROM = STROM -> LEFT
ELSE
NASTAVIŤ STROM = STROM -> VPRAVO
[KONIEC AK]
VOĽNÁ TEPLOTA
[KONIEC AK]
Funkcia:
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; }