===== Co to są i do czego służą drzewa BST =====
{{:algorytmy_i_struktury_danych:drzewa_bst.doc|wersja w formacie .doc}}


**Drzewo poszukiwań binarnych** (skrót BST, z ang. Binary Search Tree) jest dynamiczną strukturą danych w postaci **drzewa binarnego** (rodzaj drzewa, w którym liczba synów każdego wierzchołka wynosi nie więcej niż dwa; wyróżnia się wtedy lewego syna i prawego syna danego wierzchołka; drzewo binarne, w którym liczba synów każdego wierzchołka wynosi albo zero albo dwa, nazywane jest drzewem regularnym).

W każdym z węzłów drzewa przechowywana jest pewna wartość, przy czym: wartość przechowywana w węźle jest większa od wartości przechowywanej w lewym synu i mniejsza od wartości przechowywanej w prawym synu (relacja może być odwrócona, to kwestia umowy).

{{:algorytmy_i_struktury_danych:bst.jpg|Przykładowe drzewo BST}}

Drzewa BST pozwalają na szybkie wyszukiwanie pożądanego elementu. Z możliwości szybkiego wyszukania wynika też możliwość szybkiego wstawiania i usuwania z drzewa.

**Metody przeszukiwania drzewa**:
  * Wzdłużna - preorder: korzeń, lewe poddrzewo, prawe poddrzewo.
  * Poprzeczna - inorder: lewe poddrzewo, korzeń, prawe poddrzewo.
  * Wsteczne - postorder: lewe poddrzewo, prawe poddrzewo, korzeń.
Przechodząc drzewo metodą inorder uzyskuje się ciąg wartości posortowanych rosnąco.

**Wyszukiwanie**: aby znaleźć węzeł drzewa, w którym jest wartość x, porównujemy x z wartością k w korzeniu i w zależności od wyniku porównania:
  * x = k – cieszymy się, że znaleźliśmy
  * x < k – szukamy w lewym poddrzewie
  * x > k – szukamy w prawym poddrzewie
Jeśli dojdziemy w ten sposób do pustego drzewa – to znaczy, że elementu nie ma w drzewie.


**Wstawianie**: nowe elementy wstawiamy w liściach – postępując podobnie jak przy wyszukiwaniu.


**Usuwanie**: tutaj jest nieco gorzej – po znalezieniu węzła x, który chcemy usunąć, należy rozpatrzyć różne przypadki:
  * jeśli x nie ma synów – po prostu usunąć
  * jeśli x ma tylko jednego syna – zastąpić go synem
  * jeśli x ma dwóch synów:
    * znaleźć jego następnik y, (najbardziej lewy element w prawym poddrzewie x)
    * zastąpić zawartość węzła x przez zawartość węzła y
    * wyciąć węzeł y (syn y stanie się synem swojego dziadka)


**Złożoność obliczeniowa**:
Pesymistyczny koszt każdej z tych operacji na drzewie BST o n węzłach zależy od wysokości drzewa i wynosi:
  * log<sub>2</sub>(n) – dla drzewa zrównoważonego, oraz
  * n – dla drzewa, w którym każdy z węzłów oprócz liścia ma tylko jednego syna.


**Wady i zalety drzew BST**:
ujawniają one swoją szybkość dzięki strukturze drzewiastej i symetrycznemu porząkowi. Jeśli jednak będziemy do drzewa wstawiać elementy np. posortowane, drzewo rozrośnie w jedną stronę i będzie zdegenerowane do listy powiązanej. Wtedy oczywiście nie ma z niego żadnego pożytku, bo złożoność przeszukiwania (a więc i wszystkoch innych operacji) jest liniowa. Aby równoważyć drzewa BST wymyślono ich różne odmiany, np drzewa AVL i splay. Są one bardziej zrównoważone i nie dochodzi do sytuacji, kiedy tracimy wszytksie zalety z implementacji naszej struktury jako drzewa.

Więcej informacji pod adresami:
  * http://pl.wikipedia.org/wiki/Drzewo_poszukiwa%C5%84_binarnych
  * http://www.wawrzek.com/asd/bst.html
  * http://www.algorytm.org/index.php?option=com_content&task=view&id=112&Itemid=54



