Drzewa wyszukiwań binarnych

Drzewo poszukiwań binarnych (skrót BST, z ang. Binary Search Tree) jest dynamiczną strukturą danych w postaci drzewa binarnego. 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). Przechodząc drzewo metodą inorder uzyskuje się ciąg wartości posortowanych rosnąco.

Z reguły w węźle przechowuje się więcej informacji, a wartość węzła ma jedynie posłużyć do ich wyszukiwania – dlatego bywa nazywana kluczem. 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. Nowe elementy wstawiamy w liściach – postępując podobnie jak przy wyszukiwaniu. Nieco gorzej jest z usuwaniem – 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)

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.

Dlatego w praktyce często lepiej zastosować drzewo poszukiwań binarnych o dodatkowych właściwościach – np. drzewo AVL lub drzewo czerwono-czarne – które pozwalają wykonywać operacje wstawiania i usuwania węzłów z zachowaniem zrównoważenia.

Drzewo AVL, nazywane również drzewem dopuszczalnym, to drzewo poszukiwań binarnych (BST), w którym wysokość lewego i prawego poddrzewa każdego węzła różni się co najwyżej o jeden. Skrót AVL pochodzi od nazwisk twórców: Adelson-Velskii oraz Landis.

Zrównoważenie drzewa osiąga się przypisując każdemu węzłowi współczynnik wyważenia, który jest równy różnicy wysokości lewego i prawego poddrzewa. Może wynosić 0, +1 lub -1. Wstawiając lub usuwając elementy drzewa (tak aby zachować własności drzewa BST) modyfikuje się też współczynik wyważenia, a gdy przyjmie on niedozwoloną wartość wykonuje specjalną operację rotacji węzłów, która przywraca zrównoważenie.
Koszt modyfikacji drzewa jest nieco większy niż dla zwykłego drzewa BST, ale za to własności drzewa AVL gwarantują, że pesymistyczny czas wyszukiwania elementu w drzewie o n węzłach wynosi (log2n)/2, podczas gdy dla niezrównoważonego BST (w postaci listy) czas ten wynosi n.
W wielu praktycznych zastosowaniach zdarza się, że do części obiektów sięga się częściej niż do pozostałych, przykładem może być słownik. Wówczas lepszym rozwiązaniem jest zastosowanie optymalnego drzewa poszukiwań.

• każdy węzeł jest czerwony lub czarny
• każdy liść (NULL) jest czarny
• każdy czerwony węzeł ma czarne dzieci
• każda prosta ścieżka z ustalonego węzła do liścia (w dół drzewa) ma tyle samo czarnych węzłów.

DCC musi w każdym węzle przechowywać informację o kolorze (wystarczy 1 bit). W DCC definiujemy czarną głebokość: liczbę czarnych węzłów na prostej ścieżce z danego węzła x do liścia (bez tego węzła). Jak wynika z własności czwartej, możemy wybrać dowolną ścieżkę. Czarną głębokość oznaczymy dalej przez b(x).