Binarne drzewo poszukiwań (ang. Binary Search Tree (BST)) jest drzewem binarnym, w którym lewe poddrzewo każdego węzła zawiera wyłącznie elementy o kluczach nie większych niż klucz węzła a prawe poddrzewo zawiera elementy o kluczach nie mniejszych niż klucz węzła. Standardowo każdy węzeł drzewa, poza kluczem oraz wartością, przechowuje wskaźniki na lewego i prawego syna.

Dla pełnego drzewa BST o n węzłach pesymistyczny koszt każdej z podstawowych operacji wynosi . Jednak w skrajnym przypadku, gdy drzewo składa się z jednej gałęzi koszt ten wzrasta do . W literaturze często też podaje się koszt wykonania operacji w uzależnieniu od wysokości drzewa - wynosi on . Przechodząc drzewo metodą in-order, uzyskuje się ciąg wartości posortowanych niemalejąco.

Operacje wykonywane na drzewie Operacje wyszukiwania Wyszukiwanie dowolnego klucza w drzewie

Jedną z podstawowych operacji jaką można wykonać działając na drzewie BST jest operacja wyszukiwania. Wyszukiwanie elementu w drzewie rozpoczynane jest poprzez wywołanie procedury BST_TREE_SEARCH z wskaźnikiem na korzeń drzewa oraz wartością poszukiwanego klucza jako jej parametrami. Następnie klucz każdego napotkanego węzła jest porównywany z poszukiwanym kluczem: jeżeli obie wartości są równe, to zwracany jest adres węzła ze znalezionym kluczem; jeżeli wartość poszukiwanego klucza jest mniejsza niż wartość klucza w porównywanym węźle to dalsze poszukiwania prowadzone są tylko w lewy poddrzewie; analogicznie, jeżeli wartość poszukiwanego klucza jest większa niż wartość klucza w porównywanym węźle to dalsze poszukiwania prowadzone są tylko w prawym poddrzewie.

Rekurencyjny algorytm wyszukiwania wygląda następująco: define BST_TREE_SEARCH (Node, Key): if (Node == NULL) or (Node->Key == Key) return Node if Key Key return BST_TREE_SEARCH (Node->Left, Key) return BST_TREE_SEARCH (Node->Right, Key)

Istnieje także efektywniejszy algorytm przeszukiwania drzewa - algorytm iteracyjny. Przedstawia się on następująco: define ITERATIVE_BST_TREE_SEARCH (Node, Key): while ((Node != NULL) and (Node->Key != Key)) if (Key Key) Node = Node->left else Node = Node->right return Node Podobnie jak w przypadku algorytmu rekurencyjnego, także tutaj procedura wywoływana jest z parametrami będącymi wskaźnikiem na korzeń drzewa oraz wartością wyszukiwanego klucza. Także tutaj poruszamy się w dół drzewa, jednak zamiast wywołań rekurencyjnych stosujemy przypisanie adresu odpowiedniego syna węzła do zmiennej Node.

Bibliografia Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. Warszawa: Wydawnictwa Naukowo-Techniczne, 2007, ss. 253-272. ISBN 978-83-204-3328-9.