Funkcija brisanja koristi se za brisanje navedenog čvora iz stabla binarnog pretraživanja. Međutim, moramo izbrisati čvor iz stabla binarnog pretraživanja na takav način da se svojstvo stabla binarnog pretraživanja ne krši. Postoje tri situacije brisanja čvora iz stabla binarnog pretraživanja.
java char u string
Čvor koji se briše je listni čvor
To je najjednostavniji slučaj, u ovom slučaju, zamijenite list čvor s NULL i jednostavno oslobodite dodijeljeni prostor.
Na sljedećoj slici brišemo čvor 85, budući da je čvor lisnati čvor, stoga će čvor biti zamijenjen s NULL i dodijeljeni prostor će biti oslobođen.
Čvor koji se briše ima samo jedno dijete.
U tom slučaju zamijenite čvor njegovim podređenim čvorom i izbrišite podređeni čvor koji sada sadrži vrijednost koju treba izbrisati. Jednostavno ga zamijenite s NULL i oslobodite dodijeljeni prostor.
Sridevi
Na sljedećoj slici, čvor 12 treba izbrisati. Ima samo jedno dijete. Čvor će biti zamijenjen svojim podređenim čvorom, a zamijenjeni čvor 12 (koji je sada lisni čvor) jednostavno će se izbrisati.
Čvor koji se briše ima dva djeteta.
To je malo složen slučaj u usporedbi s druga dva slučaja. Međutim, čvor koji treba obrisati se rekurzivno zamjenjuje svojim nasljednikom ili prethodnikom po redu dok se vrijednost čvora (koja se želi obrisati) ne postavi na list stabla. Nakon postupka zamijenite čvor s NULL i oslobodite dodijeljeni prostor.
Na sljedećoj slici treba izbrisati čvor 50 koji je korijenski čvor stabla. Redoslijed obilaska stabla dat u nastavku.
što java
6, 25, 30, 50, 52, 60, 70, 75.
zamijeniti 50 s njegovim nasljednikom po redu 52. Sada će 50 biti premješteno na list stabla, koji će jednostavno biti izbrisan.
Algoritam
Izbriši (STABLO, STAVKA)
Napišite 'stavka nije pronađena u stablu' ALSE IF ITEM DATA
Izbriši (STABLO->LIJEVO, STAVKA)
INAČE AKO STAVKA > STABLO -> PODACI
Izbriši (STABLO -> DESNO, STAVKA)
U DRUGOM AKO STABLO -> LIJEVO I STABLO -> DESNO
POSTAVITE TEMP = findLargestNode(STABLO -> LIJEVO)
POSTAVITE STABLO -> PODACI = TEMP -> PODACI
Izbriši (STABLO -> LIJEVO, TEMP -> PODACI)
DRUGO
POSTAVITE TEMP = STABLO
AKO STABLO -> LIJEVO = NULL I STABLO -> DESNO = NULL
POSTAVITE STABLO = NULL
INAČE AKO STABLO -> LIJEVO != NULL
POSTAVITE STABLO = STABLO -> LIJEVO
DRUGO
POSTAVITE STABLO = STABLO -> DESNO
[KRAJ AKO]
SLOBODNA TEMP
[KRAJ AKO]
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; }