Wynikiem delete(e,D) dla ustalonej etykiety e i drzewa binarnych poszukiwań D, jest drzewo binarnych poszukiwań D*, otrzymane z D przez usunięcie etykiety e. Jeśli etykieta e nie występuje w D, to wynikiem jest to samo drzewo D. W przeciwnym przypadku, wynikiem jest drzewo D*, które posiada te same etykiety co drzewo D z wyjątkiem etykiety e, dokładniej

Idea usuwania jest następująca: najpierw znajdujemy wierzchołek v z etykietą e oraz ojca tego wierzchołka, oznaczonego tu przez y. Jeżeli v jest liściem, to wystarczy usunąć w y referencję do v. Jeżeli v ma tylko jednego syna, to usunięcie wierzchołka v polega na zastąpieniu w y referencji do v, referencją do jedynego syna wierzchołka v. Jeżeli v ma dwa następniki, to znajdujemy w prawym jego poddrzewie wierzchołek w o najmniejszej etykiecie (lub dualnie, wierzchołek o największej etykiecie w lewym poddrzewie). Zastępujemy etykietę wierzchołka v znalezioną etykietą, a wierzchołek w usuwamy z drzewa. Takie postępowanie modyfikuje tylko w niewielkim stopniu strukturę drzewa: wierzchołek rzeczywiście usuwany z drzewa znajduje się zawsze na końcu pewnej ścieżki. Operacja delete zwraca w wyniku drzewo, które jest argumentem tej operacji, jeśli e nie należało do drzewa, lub, gdy drzewo było puste.

Proces usuwania elementu z drzewa BST przedstawiono na rysunku 7.6. Jeśli z drzewa na rysunku 7.6(a) usuwamy etykietę 6, to wynikiem jest drzewo na rysunku 7.6(b). Wierzchołek z etykietą 6 jest liściem, zostanie więc usunięty z drzewa wraz z dowiązaniem łączącym go z wierzchołkiem 7. Jeśli z drzewa 7.6(a) usuwamy wierzchołek z etykietą 7, to ponieważ ma on tylko jeden następnik, w wyniku usunięcia etykiety 7, lewym synem wierzchołka 8 będzie wierzchołek z etykietą 6, jak na rysunku 7.6(c). Jeśli z drzewa 7.6(a) usuwamy etykietę 5, to ponieważ wierzchołek z tą etykietą ma dwa następniki, etykieta 5 zostanie zastąpiona najmniejszą etykietą prawego poddrzewa, tzn. szóstką, a wierzchołek z etykietą 6 zostanie usunięty z drzewa. J

W przedstawionym kodzie zakładamy, że root jest korzeniem niepustego drzewa binarnych poszukiwań D. Algorytm usuwania, podobnie jak algorytm wstawiania, jest modyfikacją algorytmu member, ponieważ musimy ustalić, czy, i ewentualnie gdzie, znajduje się usuwana etykieta. Zapamiętujemy dodatkowo ojca (na zmiennej y) aktualnie odwiedzanego wierzchołka v, po to, by umożliwić konieczne modyfikacje związane z usunięciem etykiety e.

node delete(e : Et, root : node) {
	bool := false; y := null; v := root;	1	// y jest ojcem wierzchołka v
	while (not bool) do	2
	if (v.val = e) then	3	// e jest etykietą wierzchołka v
	if (v. left = null or v.right = null) then	4	//v ma co najwyżej jednego syna
	usun(y,v);	5
	else		//(v.left ¹null and v.right ¹null)
	z := v.right; pred := v;	6
	while (z.left ¹ null) do	7	//szukamy minimum w PD(v)
	pred := z; z:= z.left	8
	od;	9
	et := val(z); usun(pred, z);	10	//usuwamy wierzchołek z
	v.val := et; bool := true;	11	//zmieniamy etykietę wierzchołka v
	fi;	12
	else		// v.val ¹ e
	if (v.val <e) then	13
	if (v.right ¹null) then	14	//będziemy przeszukiwać PD(v)
	y := v; v := v.right	15
	else bool := true	16
	fi	17
	else		// v.val > e
	if (v.left ¹null) then	18	//będziemy przeszukiwać drzewo LD(v)
	y := v; v := v.left	19
	else bool := true	20
	fi	21
	fi	22
	fi	23
	od	24
	fi;	25
	return root }	26

Najistotniejsza część prezentowanego algorytmu znajduje się w liniach 3-12. W tych liniach opisane są zmiany, których trzeba dokonać, gdy znajdziemy wierzchołek z etykietą e, zapamiętany w tym algorytmie na zmiennej v. Rozważamy dwa przypadki: gdy v ma co najwyżej jeden następnik i, gdy v na dokładnie dwa następniki. W obu przypadkach musimy z drzewa usunąć jeden wierzchołek. Ponieważ sam proces usuwania jest podobny, chociaż dotyczy różnych wierzchołków, wyodrębniliśmy ten fragment kodu w postaci procedury usun. Treść tej procedury jest dość kłopotliwa, gdyż musimy rozważyć kilka przypadków.

Parametrami procedury są dwa wierzchołki y i v. Zakładamy, że skądinąd wiadomo, że y jest ojcem v, oraz wierzchołek v ma co najwyżej jeden następnik. Ten ew. jedyny następnik ma zastąpić v. W procedurze usuń zapamiętaliśmy ten wierzchołek na zmiennej x. Wyróżniamy przypadek, gdy v jest korzeniem, gdyż wtedy musi być zmieniony korzeń drzewa. Jeśli v nie jest korzeniem drzewa, to ojcu wierzchołka v przekazujemy wierzchołek x na miejsce wierzchołka v.

usuń(y:node, v : node) {
	if (v. left ¹ null ) then x := v.left else x := v.right fi;
	if (y = null) then	//v jest korzeniem drzewa
	root := x
	else
	if (y.left ¹ null) and (y.left.val = v.val) then	//v jest lewym synem y
	y.left := x
	else	//v jest prawym synem y
	y.right:= x
	fi;
	fi}

W liniach 6-12 rozważany jest przypadek, gdy wierzchołek v, dla którego v.val = e, ma dwóch synów. W przedstawionym kodzie, zastępujemy etykietę wierzchołka v, najmniejszą z etykiet jego prawego poddrzewa. W pętli w liniach 7-9 znajdujemy wierzchołek z, którego etykieta ma najmniejszą wartość w PD(v), oraz, na zmiennej pred, ojca tego wierzchołka. Zauważmy, że z albo jest liściem, albo ma tylko prawy następnik. Usuwanie wierzchołka z możemy więc zrealizować za pomocą procedury usun(pred,z).

Koszt algorytmu jest zdeterminowany przez proces wyszukiwania elementu e i jest proporcjonalny do wysokości drzewa. W najgorszym razie jest to koszt O(n), gdzie n jest liczbą wierzchołków w danym drzewie. Koszt średni jest natomiast logarytmiczny O(lg n).

Pytanie 8: Utworzono drzewo BST przez wstawianie kolejno elementów 4, 2, 8, 7, 5, 6, 9, 6 Jaka etykieta znajdzie się w wierzchołku drzewa, jeśli z tego drzewa usunięto etykietę korzenia stosując algorytm delete?