Funkce Delete se používá k odstranění zadaného uzlu z binárního vyhledávacího stromu. Musíme však odstranit uzel z binárního vyhledávacího stromu tak, aby vlastnost binárního vyhledávacího stromu nenarušila. Existují tři situace odstranění uzlu z binárního vyhledávacího stromu.

Uzel, který má být odstraněn, je listový uzel

Je to nejjednodušší případ, v tomto případě nahraďte listový uzel hodnotou NULL a jednoduše uvolněte přidělené místo.

je prázdná java

Na následujícím obrázku odstraňujeme uzel 85, protože uzel je listový uzel, proto bude uzel nahrazen NULL a přidělené místo bude uvolněno.

Uzel, který má být odstraněn, má pouze jednoho potomka.

V tomto případě nahraďte uzel jeho potomkem a odstraňte dceřiný uzel, který nyní obsahuje hodnotu, která má být odstraněna. Jednoduše jej nahraďte NULL a uvolněte přidělené místo.

Na následujícím obrázku má být uzel 12 vymazán. Má jen jedno dítě. Uzel bude nahrazen svým podřízeným uzlem a nahrazený uzel 12 (který je nyní koncovým uzlem) bude jednoduše odstraněn.

Uzel, který má být odstraněn, má dva potomky.

Ve srovnání s jinými dvěma případy je to trochu komplikovaný případ. Uzel, který má být vymazán, je však rekurzivně nahrazen svým následníkem nebo předchůdcem v pořadí, dokud není na list stromu umístěna hodnota uzlu (který má být vymazán). Po postupu nahraďte uzel hodnotou NULL a uvolněte přidělené místo.

Na následujícím obrázku má být odstraněn uzel 50, který je kořenovým uzlem stromu. Níže uvedené procházení stromu v pořadí.

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

shloka mehta

nahradit 50 jeho následníkem v pořadí 52. Nyní se 50 přesune na list stromu, který bude jednoduše smazán.

Algoritmus

Smazat (TREE, ITEM)

Krok 1:POKUD STROM = NULL
Napište 'položka nebyla nalezena ve stromu' ELSE IF ITEM DATA
Smazat (STROME->LEFT, ITEM)
ELSE IF POLOŽKA > STROM -> DATA
Smazat (STRM -> VPRAVO, POLOŽKA)
ELSE IF STROM -> VLEVO A STROM -> VPRAVO
NASTAVIT TEPLOTU = najít největší uzel (STRM -> VLEVO)
SET STROM -> DATA = TEMP -> DATA
Smazat (STRM -> VLEVO, TEPLOTA -> DATA)
JINÝ
SET TEMP = STROM
POKUD STROM -> VLEVO = NULL A STROM -> VPRAVO = NULL
NASTAVIT STROM = NULL
ELSE IF TREE -> LEFT != NULL
NASTAVIT STROM = STROM -> VLEVO
JINÝ
NASTAVIT STROM = STROM -> VPRAVO
[KONEC POKUD]
TEPLOTA ZDARMA
[KONEC POKUD]Krok 2:KONEC

Funkce:

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