Tekst źródłowy strony Struktury danych/Drzewa/Drzewa wyszukiwań binarnych

'''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 <math>O(log(n))</math>. Jednak w skrajnym przypadku, gdy drzewo składa się z jednej gałęzi koszt ten wzrasta do <math>O(n)</math>. W literaturze 
często też podaje się koszt wykonania operacji w uzależnieniu od wysokości drzewa <math>h</math> - wynosi on <math>O(h)</math>. 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 ====
[[Plik:Binary search tree search 4.svg|thumb|250px|Wyszukiwanie klucza o wartości 4 w binarnym drzewie wyszkukiwań]]
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:
<code>
<syntaxhighlight lang="cpp">
define BST_TREE_SEARCH (Node, Key):
    if (Node == NULL) or (Node->Key == Key)
        return Node
    if Key < Node->Key
        return BST_TREE_SEARCH (Node->Left, Key)
    return BST_TREE_SEARCH (Node->Right, Key)
</syntaxhighlight>
</code>

Istnieje także efektywniejszy algorytm przeszukiwania drzewa - algorytm iteracyjny. Przedstawia się on następująco:
<code>
<syntaxhighlight lang="cpp">
define ITERATIVE_BST_TREE_SEARCH (Node, Key):
    while ((Node != NULL) and (Node->Key != Key))
        if (Key < Node->Key)
            Node = Node->left
        else
            Node = Node->right
    return Node
</syntaxhighlight>
</code>
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.

{{Nawigacja|Struktury danych|[[Struktury danych/Drzewa|Drzewa]]|[[Struktury danych/Drzewa czerwono-czarne|Drzewa czerwono-czarne]]}}