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[1].
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[1].
Operacje wykonywane na drzewie
[edytuj | edytuj kod]Operacje wyszukiwania
[edytuj | edytuj kod]Wyszukiwanie dowolnego klucza w drzewie
[edytuj | edytuj kod]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[1].
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[1].
Wyszukiwanie najmniejszego i największego klucza w drzewie
[edytuj | edytuj kod]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[1]:
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[1].
Wyszukiwanie następnika i poprzednika w drzewie
[edytuj | edytuj kod]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[1][2]:
- 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[1][2]:
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[1][2]:
- 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
[edytuj | edytuj kod]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[1]:
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
[edytuj | edytuj kod]Usuwanie węzła jest procedurą bardziej skomplikowaną niż jego wstawianie. Podczas wykonywania procedury należy rozważyć trzy przypadki[1]:
- 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).
-
Usuwanie węzła, który jest liściem
-
Usuwanie węzła z jednym synem
-
Usuwanie węzła z kluczem 3 z dwoma synami. Następnikiem węzła jest węzeł z kluczem 4
-
Usuwanie węzła z kluczem 8 z dwoma synami. Następnikiem węzła jest węzeł z kluczem 10
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
[edytuj | edytuj kod]Ś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ń
[edytuj | edytuj kod]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ż
[edytuj | edytuj kod]- algorytm DSW
- drzewo AVL
- drzewo czerwono-czarne
- drzewo o ograniczonym zrównoważeniu
- drzewo splay
- przechodzenie drzewa
- rotacja drzewa
Przypisy
[edytuj | edytuj kod]- ↑ a b c d e f g h i j k Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. Warszawa: Wydawnictwa Naukowo-Techniczne, 2007, s. 253–272. ISBN 978-83-204-3328-9.
- ↑ a b c Thomas A. Anastasio: Successor/Predecessor Rules in Binary Search Trees. 2003-07-07. [dostęp 2010-09-18]. (ang.).