Funkcija brisanja se uporablja za brisanje določenega vozlišča iz binarnega iskalnega drevesa. Vendar pa moramo vozlišče izbrisati iz binarnega iskalnega drevesa na tak način, da lastnost binarnega iskalnega drevesa ne bo kršena. Obstajajo trije primeri brisanja vozlišča iz binarnega iskalnega drevesa.

Vozlišče, ki ga želite izbrisati, je listno vozlišče

To je najpreprostejši primer, v tem primeru zamenjajte listno vozlišče z NULL in preprosto sprostite dodeljeni prostor.

primerjava nizov c#

Na naslednji sliki brišemo vozlišče 85, ker je vozlišče listno vozlišče, zato bo vozlišče zamenjano z NULL in dodeljeni prostor bo sproščen.

Vozlišče, ki ga želite izbrisati, ima samo enega podrejenega.

V tem primeru zamenjajte vozlišče z njegovim podrejenim in izbrišite podrejeno vozlišče, ki zdaj vsebuje vrednost, ki jo želite izbrisati. Preprosto ga zamenjajte z NULL in sprostite dodeljeni prostor.

java volatile ključna beseda

Na naslednji sliki je treba vozlišče 12 izbrisati. Ima samo enega otroka. Vozlišče bo zamenjano s podrejenim vozliščem, zamenjano vozlišče 12 (ki je zdaj listno vozlišče) pa bo preprosto izbrisano.

Vozlišče, ki ga želite izbrisati, ima dva otroka.

To je nekoliko zapleten primer v primerjavi z drugima dvema primeroma. Vendar se vozlišče, ki ga je treba izbrisati, rekurzivno nadomesti z njegovim naslednikom ali predhodnikom po vrstnem redu, dokler se vrednost vozlišča (ki ga je treba izbrisati) ne postavi na list drevesa. Po postopku zamenjajte vozlišče z NULL in sprostite dodeljeni prostor.

Na naslednji sliki je treba izbrisati vozlišče 50, ki je korensko vozlišče drevesa. Spodaj podano prečkanje drevesa po vrstnem redu.

int v niz v Javi

6, 25, 30, 50, 52, 60, 70, 75.

zamenjajte 50 z njegovim naslednikom po vrstnem redu 52. Zdaj bo 50 premaknjeno na list drevesa, ki bo preprosto izbrisan.

Algoritem

Izbriši (DREVO, ELEMENT)

Korak 1:ČE DREVO = NULL
Napišite 'element ni bil najden v drevesu' ELSE IF ITEM DATA
Izbriši (DREVO->LEVO, ELEMENT)
ALSE IF ITEM > TREE -> DATA
Izbriši (DREVO -> DESNO, ELEMENT)
DRUGE ČE JE DREVO -> LEVO IN DREVO -> DESNO
NASTAVI TEMP = najdi največje vozlišče (DREVO -> LEVO)
NASTAVI DREVO -> PODATKI = TEMP -> PODATKI
Izbriši (DREVO -> LEVO, TEMP -> PODATKI)
DRUGEGA
NASTAVI TEMP = DREVO
ČE DREVO -> LEVO = NIČ IN DREVO -> DESNO = NIČ
NASTAVI DREVO = NULL
ALSE IF TREE -> LEFT != NULL
NASTAVI DREVO = DREVO -> LEVO
DRUGEGA
NASTAVI DREVO = DREVO -> PRAV
[KONEC ČE]
PROSTA TEMP
[KONEC ČE]2. korak:KONEC

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; }