Tekst źródłowy strony Binarne drzewo poszukiwań

[[Plik:Binary search tree.svg|thumb|250px|Binarne drzewo poszukiwań o wielkości równej 9, a wysokości równej 3; wierzchołek '8' jest tu korzeniem, a wierzchołki '1', '4', '7' i '13', to liście]]

'''Binarne drzewo poszukiwań''' ([[język angielski|ang.]] ''Binary Search Tree'', BST) – dynamiczna [[struktura danych]] będąca [[drzewo binarne|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 <math>h,</math> ponieważ operacje wykonywane są wzdłuż drzewa. Fakt ten w [[Asymptotyczne tempo wzrostu|notacji Landaua]] zapisuje się <math>\Omicron(h).</math> Jeżeli drzewo jest zrównoważone, to jego wysokość bliska jest logarytmowi dwójkowemu liczby węzłów <math>(h \approx \log_2(n)),</math> zatem dla drzewa o <math>n</math> węzłach optymistyczny koszt każdej z podstawowych operacji wynosi <math>\Omicron(\log n).</math> 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: <math>h = n</math>), z tego powodu koszt pesymistyczny wzrasta do <math>\Omicron(n).</math>

Przechodząc drzewo metodą [[Przechodzenie drzewa|in-order]], uzyskuje się ciąg wartości kluczy posortowanych niemalejąco<ref name="Cormen1">{{cytuj książkę |autor=Thomas H. Cormen |autor2=Charles E. Leiserson |autor3=Ronald L. Rivest |autor4=Clifford Stein |tytuł=Wprowadzenie do algorytmów |wydawca=[[Wydawnictwa Naukowo-Techniczne]] |miejsce=Warszawa |rok=2007 |strony=253–272 |isbn=978-83-204-3328-9}}</ref>.

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<ref name="Cormen1" />.

== 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 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<ref name="Cormen1" />.

Rekurencyjny algorytm wyszukiwania wygląda następująco:
<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>

Istnieje także efektywniejszy algorytm przeszukiwania drzewa – [[algorytm iteracyjny]]. Przedstawia się on następująco:
<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>
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<ref name="Cormen1" />.

==== 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<ref name="Cormen1" />:
<syntaxhighlight lang="cpp">
define BST_SEARCH_MIN_KEY(Node):
    while (Node->left != NULL)
        Node = Node->left
    return Node
</syntaxhighlight>

Analogicznie, aby znaleźć węzeł z największym kluczem w drzewie należy skierować się w prawy, skrajny dół drzewa<ref name="Cormen1" />.

==== 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 [[Przechodzenie drzewa|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<ref name="Cormen1" /><ref name="Lecture1" />:
* 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<ref name="Cormen1" /><ref name="Lecture1">{{cytuj stronę| url=http://faculty.salisbury.edu/~despickler/personal/Resources/AdvancedDataStructures/Handouts/succ_pred_rules.pdf |tytuł=Successor/Predecessor Rules in Binary Search Trees |autor=Thomas A. Anastasio |data=2003-07-07 |język=en |data dostępu=2010-09-18}}</ref>:
<syntaxhighlight lang="cpp">
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
</syntaxhighlight>

Analogicznie przebiega wyszukiwanie poprzednika:
<syntaxhighlight lang="cpp">
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
</syntaxhighlight>
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<ref name="Cormen1" /><ref name="Lecture1" />:
* 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ł <code>InsertNode</code>, w którym <code>InsertNode->Left == NULL</code>, <code>InsertNode->Right == NULL</code> oraz <code>InsertNode->Key != NULL</code>. Algorytm wstawiania węzła do drzewa jest bardzo podobny do algorytmu wyszukiwania węzła w drzewie i wygląda następująco<ref name="Cormen1" />:
<syntaxhighlight lang="cpp">
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
</syntaxhighlight>
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<ref name="Cormen1" />:
* 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).
<gallery widths="250px" perrow="2">
Plik:Binary search tree delete 13.svg | Usuwanie węzła, który jest liściem
Plik:Binary search tree delete 14.svg | Usuwanie węzła z jednym synem
Plik:Binary search tree delete 3.svg | Usuwanie węzła z kluczem 3 z dwoma synami. Następnikiem węzła jest węzeł z kluczem 4
Plik:Binary search tree delete 8.svg | Usuwanie węzła z kluczem 8 z dwoma synami. Następnikiem węzła jest węzeł z kluczem 10
</gallery>

<syntaxhighlight lang="cpp">
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
</syntaxhighlight>

== Wyważanie drzewa ==
[[Plik:Unbalanced binary tree.svg|thumb|294x294px|Drzewo niezrównoważone (np. lewe poddrzewo węzła 76 ma wysokość 3, a prawe 0)]]

Ś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 <math>\log_2 n,</math> gdzie <math>n</math> 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 [[drzewo AVL|drzewa AVL]] i [[drzewo czerwono-czarne|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 [[tablica (informatyka)|tablicy]], algorytmem analogicznym do [[wyszukiwanie binarne|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 [[Algorytm DSW|algorytmu DSW]], który równoważy drzewo BST poprzez szereg [[rotacja drzewa|rotacji]], co nie wymaga ani sortowania, ani dodatkowej pamięci.
{{clear}}
{{Wikibooks|Kody_źródłowe/Binarne_drzewo_poszukiwań}}

== Optymalne drzewo poszukiwań ==
{{sekcja stub}}

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 [[programowanie dynamiczne|programowaniu dynamicznym]] i charakteryzuje się złożonością czasową <math>\Omicron(n^3)</math> lub przy niewielkich modyfikacjach pokazanych przez Knutha – <math>\Omicron(n^2);</math> złożoność pamięciowa wynosi <math>\Omicron(n^2).</math> 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ć [[drzewo splay|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 ==
{{Przypisy}}

== Linki zewnętrzne ==

* [https://people.ksp.sk/~kuko/gnarley-trees/BST.html Wizualizacja drzewa poszukiwań binarnych]

[[Kategoria:Drzewa (informatyka)]]