algorytmy_i_struktury_danych:drzewa_bst

## Co to są i do czego służą drzewa BST

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

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:

- log2(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