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 $O(log(n))$. Jednak w skrajnym przypadku, gdy drzewo składa się z jednej gałęzi koszt ten wzrasta do $O(n)$. W literaturze często też podaje się koszt wykonania operacji w uzależnieniu od wysokości drzewa $h$ - wynosi on $O(h)$. 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

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:

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)

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 < Node->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.