Binarne drzewo poszukiwań

Binarne drzewo poszukiwań (ang. Binary Search Tree, BST) – dynamiczna struktura danych będąca drzewem binarnym, w którym lewe poddrzewo każdego węzła zawiera wyłącznie elementy o kluczach mniejszych niż klucz węzła, a prawe poddrzewo zawiera wyłącznie elementy o kluczach nie mniejszych niż klucz węzła. Węzły, oprócz klucza, przechowują wskaźniki na swojego lewego i prawego syna oraz na swojego ojca.

Koszt wykonania podstawowych operacji w drzewie BST (wstawienie, wyszukanie, usunięcie węzła) jest proporcjonalny do wysokości drzewa  ponieważ operacje wykonywane są wzdłuż drzewa. Fakt ten w notacji Landaua zapisuje się  Jeżeli drzewo jest zrównoważone, to jego wysokość bliska jest logarytmowi dwójkowemu liczby węzłów  zatem dla drzewa o  węzłach optymistyczny koszt każdej z podstawowych operacji wynosi  Z drugiej strony drzewo skrajnie niezrównoważone ma wysokość porównywalną z liczbą węzłów (w skrajnym przypadku drzewa zdegenerowanego do listy wartości te są równe: ), z tego powodu koszt pesymistyczny wzrasta do 

Przechodząc drzewo metodą in-order, uzyskuje się ciąg wartości kluczy posortowanych niemalejąco.

Binarne drzewa wyszukiwań często stosuje się w zadaniach, w których wymagane jest względnie szybkie sortowanie lub wyszukiwanie elementów, na przykład różnego rodzaju słowniki, kolejki priorytetowe.

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 ze 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 lewym 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.

Wyszukiwanie najmniejszego i największego klucza w drzewie 
Aby wyszukać w drzewie klucz o najmniejszej wartości, wystarczy kierować się w lewy, skrajny dół drzewa. Ostatni napotkany element, niebędący węzłem pustym, jest węzłem zawierającym najmniejszy klucz. Algorytm iteracyjny jest następujący:
define BST_SEARCH_MIN_KEY(Node):
    while (Node->left != NULL)
        Node = Node->left
    return Node

Analogicznie, aby znaleźć węzeł z największym kluczem w drzewie należy skierować się w prawy, skrajny dół drzewa.

Wyszukiwanie następnika i poprzednika w drzewie 
Następnik danego węzła jest węzłem, który jest odwiedzany jako następny w przypadku przechodzenia drzewa metodą in-order. W drzewie BST w celu wyznaczenia następnika węzła nie trzeba przeprowadzać żadnych porównań kluczy. Podczas wyszukiwania mogą zaistnieć dwie sytuacje:
 istnieje prawe poddrzewo węzła odniesienia – wtedy znalezienie jego następnika ogranicza się do znalezienia najmniejszego klucza w tym poddrzewie,
 nie istnieje prawe poddrzewo węzła odniesienia – wtedy następnikiem jest węzeł będący najniższym (w sensie wysokości w drzewie) przodkiem węzła odniesienia, dla którego węzeł odniesienia leży w lewym poddrzewie.

Algorytm wyznaczania następnika jest następujący:
define BST_FIND_SUCCESSOR(Node):
    if (Node->right != NULL)
        return BST_SEARCH_MIN_KEY(Node->right)
    Node_tmp = Node->parent
    while (Node_tmp != NULL and Node_tmp->left != Node)
        Node = Node_tmp
        Node_tmp = Node_tmp->parent
    return Node_tmp

Analogicznie przebiega wyszukiwanie poprzednika:
define BST_FIND_PREDECESSOR(Node):
    if (Node->left != NULL)
        return BST_SEARCH_MAX_KEY(Node->left)
    Node_tmp = Node->parent
    while (Node_tmp != NULL and Node_tmp->right != Node)
        Node = Node_tmp
        Node_tmp = Node_tmp->parent
    return Node_tmp
Podobnie jak w poprzednim przypadku wyszukiwanie rozpoczynamy od wywołania procedury BST_FIND_PREDECESSOR z adresem węzła, którego poprzednik chcemy znaleźć. Podczas przeszukiwania mogą zaistnieć dwie sytuacje:
 istnieje lewe poddrzewo danego węzła – wtedy znalezienie jego poprzednika ogranicza się do znalezienia największego klucza w tym poddrzewie
 nie istnieje lewe poddrzewo danego węzła – wtedy poprzednikiem jest węzeł będący jednocześnie najniższym przodkiem węzła (którego chcemy znaleźć) oraz mającym prawego syna, który także jest przodkiem danego węzła.

Wstawianie klucza 
Nowe elementy wstawiane są jako liście w odpowiednim miejscu. Do procedury przekazujemy jako argument węzeł InsertNode, w którym InsertNode->Left == NULL, InsertNode->Right == NULL oraz InsertNode->Key != NULL. Algorytm wstawiania węzła do drzewa jest bardzo podobny do algorytmu wyszukiwania węzła w drzewie i wygląda następująco:
define BST_TREE_INSERT_NODE(Tree, InsertNode)
    y = NULL
    x = Tree->Root
    while (x != NULL)
        y = x
        if (InsertNode->Key < x->Key)
            x = x->left
        else
            x = x->right

    InsertNode->Parent = y

    if (y == NULL) //drzewo jest puste
        Tree->Root = InsertNode
    else
        if (InsertNode->Key < y->key)
            y->Left = InsertNode
        else
            y->Right = InsertNode
Wstawianie rozpoczyna się przeglądaniem węzła od korzenia w celu znalezienia miejsca przyłączenia wstawianego węzła.

Usuwanie klucza 
Usuwanie węzła jest procedurą bardziej skomplikowaną niż jego wstawianie. Podczas wykonywania procedury należy rozważyć trzy przypadki:
 w przypadku, gdy usuwany węzeł nie ma synów (jest liściem) usunięcie przebiega bez reorganizacji drzewa – wskaźnik do węzła w jego ojcu zastępowany jest wskaźnikiem do węzła pustego
 w przypadku, gdy usuwany węzeł ma jednego syna to dany węzeł usuwamy a jego syna podstawiamy w miejsce usuniętego węzła
 w przypadku, gdy usuwany węzeł ma dwóch synów to po jego usunięciu wstawiamy w jego miejsce węzeł, który jest jego następnikiem (który nie ma lewego syna).

define BST_TREE_DELETE (Tree, DeleteNode):
        if (DeleteNode->Left==NULL) or (DeleteNode->Right==NULL)
                y=DeleteNode
        else
                y=BST_FIND_SUCCESSOR(DeleteNode)
        if (y->Left != NULL)
                x=y->Left
        else
                x=y->Right
        if (x!=NULL)
                x->parent = y->parent
        if (y->parent == NULL)
                Tree->root = x
        else
                if (y == y->parent->Left)
                        y->parent->Left = x
                else
                        y->parent->Right = x
        if (y != DeleteNode)
                DeleteNode->Key = y->Key
                // Jeśli y ma inne pola, to je także należy skopiować
        return y

Wyważanie drzewa 

Średni czas wykonywania operacji na drzewach poszukiwań binarnych zależy od średniej wysokości drzewa. Podobnie pesymistyczny czas wykonania operacji zależy od wysokości drzewa (tj. długości najdłuższej ścieżki od korzenia do liści). Najlepiej, gdy wynosi ona w przybliżeniu  gdzie  to liczba węzłów w drzewie. Powoduje to że zarówno w lewym i prawym poddrzewie jest mniej więcej tyle samo węzłów, a tym samym dojście do każdego liścia zajmuje mniej więcej tyle samo kroków. Jest tak w przypadku, gdy drzewo jest zrównoważone, wówczas różnica wysokości lewego i prawego poddrzewa każdego z węzłów wynosi co najwyżej 1. Drzewo jest doskonale zrównoważone, gdy liczby elementów prawego i lewego poddrzewa każdego węzła różnią się najwyżej o jeden.

Powszechnie używane struktury gwarantujące zrównoważenie to drzewa AVL i drzewa czerwono-czarne. Posiadają one bardziej skomplikowane reguły wstawiania i usuwania, jak również przechowują dodatkowe wartości pomocnicze w węzłach drzewa.

Wyważone drzewo można łatwo zbudować na bazie posortowanej tablicy, algorytmem analogicznym do wyszukiwania binarnego. Jednak to podejście jest nie najlepsze jeśli drzewo już istnieje – wymaga bowiem skopiowania wszystkich danych do dodatkowej pamięci i całkowitej przebudowy drzewa. Lepszym rozwiązaniem jest użycie algorytmu DSW, który równoważy drzewo BST poprzez szereg rotacji, co nie wymaga ani sortowania, ani dodatkowej pamięci.

Optymalne drzewo poszukiwań 

Jeśli wiadomo, że dane w drzewie nie będą zmieniane, a ponadto znane są prawdopodobieństwa (częstotliwości) dostępu do poszczególnych kluczy, można utworzyć optymalne BST, w którym oczekiwany czas wyszukiwania będzie minimalny. Przy konstrukcji drzewa optymalnego bierze się pod uwagę dwa czynniki: prawdopodobieństwo wyszukiwania zakończonego powodzeniem (klucz jest w drzewie) oraz niepowodzeniem (klucza nie ma w drzewie).

Algorytm tworzący optymalne BST opiera swoje działanie na programowaniu dynamicznym i charakteryzuje się złożonością czasową  lub przy niewielkich modyfikacjach pokazanych przez Knutha –  złożoność pamięciowa wynosi  Knuth pokazuje także metody przybliżone, o mniejszej złożoności czasowej, które dają BST gorsze o 2–5% od optymalnego rozwiązania.

W przypadku nieznanej statystyki dostępu do kluczy można stosować drzewa samoorganizujące się, które na bieżąco korygują położenie kluczy w drzewie.

Zobacz też 
 algorytm DSW
 drzewo AVL
 drzewo czerwono-czarne
 drzewo o ograniczonym zrównoważeniu
 drzewo splay
 przechodzenie drzewa
 rotacja drzewa

Przypisy

Linki zewnętrzne 

 Wizualizacja drzewa poszukiwań binarnych

Drzewa (informatyka)