Binarne drzewo poszukiwań

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
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ń (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 nie większych 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 h, ponieważ operacje wykonywane są wzdłuż drzewa. Fakt ten w notacji Landaua zapisuje się O(h). Jeżeli drzewo jest zrównoważone, to jego wysokość bliska jest logarytmowi dwójkowemu liczby węzłów (h \approx \log_2(n)), zatem dla drzewa o n węzłach optymistyczny koszt każdej z podstawowych operacji wynosi O(log n). 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: h=n), z tego powodu koszt pesymistyczny wzrasta do O(n).

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]

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[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 wyszukiwania następnika 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).
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]

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 \log_2 n, gdzie n 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 dodatkowo wszystkie liście znajdują się na najwyżej dwóch poziomach.

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]

Wiki letter w.svg Ta sekcja jest niekompletna. Jeśli możesz, rozbuduj ją.

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ą O(n^3) lub przy niewielkich modyfikacjach pokazanych przez Knutha – O(n^2); złożoność pamięciowa wynosi O(n^2). 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.

Implementacje[edytuj | edytuj kod]

Przypisy

  1. 1,00 1,01 1,02 1,03 1,04 1,05 1,06 1,07 1,08 1,09 1,10 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.
  2. 2,0 2,1 2,2 "Successor/Predecessor Rules in Binary Search Trees" (ang.). [dostęp 2010-09-18].

Zobacz też[edytuj | edytuj kod]