Operacja insert, wstawiania elementu do drzewa BST jest operacją dwuargumentową,

która dla danej etykiety e i drzewa binarnych poszukiwań D daje w wyniku drzewo binarnych poszukiwań D* spełniające warunek wk,

Etykietami w drzewie D* są dokładnie etykiety drzewa D oraz etykieta e. Wynika stąd, że jeśli e była etykietą jakiegoś wierzchołka w drzewie D, to po wykonaniu operacji insert(e,D) zbiór etykiet nie ulegnie zmianie.

Naszym zadaniem w tym punkcie, jest przedstawienie jednorodnego postępowania, które pozwoli zrealizować dołączanie nowej etykiety do dowolnego drzewa binarnych poszukiwań, tak by w wyniku powstało również drzewo binarnych poszukiwań.

Zaczynając od korzenia drzewa D, przeglądamy wierzchołki w poszukiwaniu elementu e. Jeśli e jest etykietą w tym drzewie, to wynikiem jest dane drzewo D. Jeśli e nie występuje w D, znajdujemy wierzchołek v, który mógłby być ojcem wierzchołka z etykietą e. Tworzymy nowy wierzchołek, przypisujemy mu etykietę e i dołączamy go jako lewego syna wierzchołka v, gdy e < v.val, i jako prawego syna v, gdy v.val < e. Oczywiście, jeśli drzewo jest puste, to w wyniku otrzymamy drzewo złożone z jednego tylko wierzchołka z etykietą e.

Algorytm insert jest niewielką modyfikacją algorytmu member. Teraz jednak interesuje nas nie tylko informacja, czy e jest, czy nie jest etykietą drzewa. Chcemy też znać właściwe miejsce, dla etykiety e, jeśli jeszcze nie występowała w tym drzewie. Tym właściwym miejscem jest ostatni wierzchołek na ścieżce poszukiwań etykiety e. W poniższym algorytmie zakładamy, że new node jest instrukcją utworzenia nowego wierzchołka z wszystkimi atrybutami równymi null. Zadaniem zmiennej bool jest przerwanie wykonywania pętli, gdy postępowanie zostanie zakończone.

node insert(e : Et, root : node) {
	if (root = null) then	//jeśli drzewo jest puste, to tworzymy wierzchołek z etykietą e, jako root
	root:= new node; root.val := e;
	else
	bool := false; v := root;
	while (not bool) do
	if (v.val = e) then bool := true	// jeśli e jest etykietą w tym drzewie, to wynikiem jest to samo drzewo
	else
	if (v.val <e) then
	if (v.right ¹null) then v := v.right	//będziemy przeszukiwać prawe poddrzewo
	else
	w := new node; w.val := e;	// dowiązujemy nowy wierzchołek z
	v. right := w; bool := true	etykietą e jako prawego syna v
	fi;
	else
	if (v.left ¹null) then v := v.left	//będziemy przeszukiwać lewe poddrzewo
	else
	w := new node; w.val := e;	// dowiązujemy nowy wierzchołek z
	y.left := w; bool := true	etykietą e jako lewego syna v
	fi
	fi
	fi
	od
	fi;
	return root }

Na rysunku 7.5 przedstawiono drzewa binarnych poszukiwań otrzymane przez kolejne wstawianie etykiet 6, 5, 8, 9, 7 do początkowo pustego drzewa. Zauważmy, że nowe elementy pojawiają się jako etykiety liści.

Pytanie 6: Niech będzie etykietą różną od wszystkich etykiet drzewa D. Czy po wykonaniu instrukcji "D* := insert(e,D);" prawdziwe jest zdanie "Jeśli w jest wierzchołkiem drzewa D* i w.val = e, to w jest liściem w drzewie D*."?

Algorytm insert zatrzymuje się dla dowolnych danych D, e: w każdej iteracji pętli, o ile nie znaleźliśmy jeszcze ani etykiety e, ani właściwego miejsca dla e, schodzimy w głąb drzewa na następny poziom (instrukcje: v:= v.left lub v:= v.right). Proces ten zakończy się po skończonej liczbie kroków, bo wysokość drzewa D jest skończona.

Żadna z instrukcji algorytmu nie zmienia wartości etykiet danego drzewa D, więc drzewo otrzymane w wyniku zawiera wszystkie etykiety drzewa D. Przypuśćmy, że w pewnej iteracji pętli zachodzą warunki e < v.val oraz v.left = null. Z pierwszego warunku wynika, że e musi się znaleźć w lewym poddrzewie wierzchołka v, z drugiego warunku, że to poddrzewo jest puste. Zatem e nie należy do drzewa D i możemy dowiązać nowy wierzchołek z etykietą e, jako lewego syna wierzchołka v. Zmienna bool jest w tym momencie algorytmu ustalona na true, więc proces zostanie zakończony, a w wyniku otrzymamy drzewo binarnych poszukiwań, w którym znajduje się etykieta e. Analogiczna sytuacja zachodzi, gdy v.val<e oraz v.right = null.

Lemat 4.1 Algorytm insert zatrzymuje się dla dowolnego drzewa binarnych poszukiwań D i dowolnej etykiety e, a wynikiem jest drzewo binarnych poszukiwań D* spełniające warunek member(e,D*) Ù ("x, e¹x) (member(x,D) º member(x,D*)).

Koszt algorytmu mierzony liczbą wykonanych porównań jest zdeterminowany przez proces wyszukiwania elementu e lub miejsc, gdzie powinien zostać dowiązany wierzchołek z etykietą e. Pozostałe czynności związane z utworzeniem nowego wierzchołka mają koszt stały. Zatem w najgorszym wypadku koszt wynosi O(n), a średnio O(lg n), gdzie n jest liczbą wierzchołków w drzewie D (por. analizę kosztu algorytmu memebr).

Pytanie 7: Jaka jest wysokość drzewa binarnych poszukiwań, jeśli do początkowo pustego drzewa włożono kolejno etykiety 5, 7, 2, 1, 9, 3, 6, 0?