Niech v będzie wierzchołkiem drzewa binarnego i niech LD(v) oznacza jego lewe poddrzewo (tzn. drzewo, którego korzeniem jest lewy syn wierzchołka v), a PD(v) - jego prawe poddrzewo.

Definicja 2.1 Niech <Et, £> będzie niepustym zbiorem etykiet, liniowo uporządkowanym przez relację £. Drzewem binarnych poszukiwań nazywamy etykietowane drzewo binarne z wyróżnionym korzeniem D = <V, E, et > takie, że et jest funkcją różnowartościową przyporządkowującą wierzchołkom drzewa etykiety w taki sposób, że dla dowolnego v ÎV,

(1) jeśli x ÎLD(v), to et(x) £ et(v),

(2) jeśli x ÎPD(v), to et(v) £ et(x).

Drzewo binarne przedstawione na rysunku 7.1(a) jest etykietowanym drzewem binarnym, ale nie jest drzewem binarnych poszukiwań, ponieważ porządek etykiet nie został zachowany. Drzewa na rysunku 7.3(a) i 7.3(b) są drzewami binarnych poszukiwań. Dla każdego wierzchołka, etykiety wierzchołków należących do lewego poddrzewa są mniejsze, a etykiety wierzchołków należących do prawego poddrzewa są większe od etykiety tego wierzchołka.

Uwaga. Zauważmy, że warunki (1), (2) definicji 2.1 nie mogą być zastąpione warunkiem

(*) dla dowolnego wierzchołka v, etykieta lewego syna jest mniejsza, a etykieta prawego syna jest większa niż etykieta wierzchołka v.

Zamieniając w drzewie 7.3(b) etykiety 8 i 9 miejscami, otrzymamy drzewo, dla którego warunek (*) jest spełniony, a które mimo to nie jest drzewem binarnych poszukiwań, bo nie spełnia warunków (1) i (2) definicji 2.1.

Drzewa BST, będziemy implementowali tak jak inne drzewa binarne, jako obiekty klasy node (por. wykład VI p4.). Dostęp do innych wierzchołków będzie umożliwiony zawsze przez korzeń drzewa i jego atrybuty left i right. Wartości funkcji etykietującej będą zapamiętane jako parametr val, tzn. jeśli et(v) = e, to v.val = e.

W dalszych punktach tego wykładu omówimy podstawowe operacje na drzewach BST, których wykonanie prowadzi znów do drzew BST. Teraz zauważmy tylko, że, jeśli zbiór X jest reprezentowany przez drzewo BST, to wyszukanie w tym zbiorze elementu najmniejszego lub największego jest niezwykle proste. Aby ustalić wartość elementu najmniejszego musimy "przejść" po lewej skrajnej gałęzi tego drzewa. Element na końcu tej ścieżki jest elementem najmniejszym. Element na końcu skrajnej, prawej ścieżki jest elementem największym w X. Algorytmy znajdowania minimum i maksimum są zamieszczone poniżej.

minBST(d : node) {		\|	maxBST(d : node) {
	v := d;	\|	v := d;
	while (v.left ¹ null) do	\|	while (v.right ¹ null) do
	v := v.left;	\|	v := v.right
	od;	\|	od;
	return v.val	\|	return v.val
}		\|

Koszt wyszukiwania minimum i maksimum jest proporcjonalny do długości przeglądanej ścieżki. Zatem dla drzewa o wysokości h wynosi O(h). Nie musimy wykonywać operacji porównywania elementów, a tylko instrukcje przypisania. Dla drzewa o n wierzchołkach, w najgorszym razie wykonamy ich n, a w najlepszym tylko jedną. Interesujący jest też koszt średni, który wynosi O(lg n), ale o tym będzie mowa w dalszej części wykładu.

Pytanie 4: Jaka jest minimalna i maksymalna liczba etykiet, które mogą być przechowywane w drzewie BST o wysokości h?