• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Drzewo AVL



    Podstrony: 1 [2] [3]
    Przeczytaj także...
    Drzewo – w informatyce to struktura danych reprezentująca drzewo matematyczne. W naturalny sposób reprezentuje hierarchię danych (obiektów fizycznych i abstrakcyjnych, pojęć, itp.) jest więc stosowane głównie do tego celu. Drzewa ułatwiają i przyspieszają wyszukiwanie, a także pozwalają w łatwy sposób operować na posortowanych danych.Rekurencja, zwana także rekursją (ang. recursion, z łac. recurrere, przybiec z powrotem) to w logice, programowaniu i w matematyce odwoływanie się np. funkcji lub definicji do samej siebie.
    Drzewo AVL
    To samo drzewo przed operacją równoważenia

    Drzewo AVL, nazywane również drzewem dopuszczalnym – zrównoważone binarne drzewo poszukiwań (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 rosyjskich matematyków: Adelsona-Velskiego oraz Landisa (właściwie: Gieorgij Adelson-Wielski i Jewgienij Łandis), którzy zaproponowali rozwiązanie problemu utrzymania dobrego drzewa wyszukiwań w roku 1962.

    Jewgienij Łandis, ros.: Евгений Михайлович Ландис (ur. 6 października 1921 w Charkowie, zm. 12 grudnia 1997 w Moskwie) - rosyjski matematyk. Jego prace dotyczyły głównie cząstkowych równań różniczkowych. Studiował i pracował na Uniwersytecie Moskiewskim, jego nauczycielami byli m.in. Aleksandr Kronrod i Iwan Petrowskij.Asymptotyczne tempo wzrostu jest miarą określającą zachowanie wartości funkcji wraz ze wzrostem jej argumentów. Stosowane jest szczególnie często w teorii obliczeń, w celu opisu złożoności obliczeniowej, czyli zależności ilości potrzebnych zasobów (np. czasu lub pamięci) od rozmiaru danych wejściowych algorytmu. Asymptotyczne tempo wzrostu opisuje jak szybko dana funkcja rośnie lub maleje, abstrahując od konkretnej postaci tych zmian.

    Drzewo AVL pozostaje drzewem binarnych poszukiwań, co oznacza, że wierzchołki są uporządkowane w określony sposób. Zazwyczaj przyjmuje się, że elementy w lewym poddrzewie są mniejsze od wierzchołka, zaś w prawym – większe. 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, by zachować własności drzewa BST), modyfikuje się też współczynnik wyważenia, a gdy przyjmie on niedozwoloną wartość, wykonuje specjalną operację rotacji węzłów, która przywraca zrównoważenie.

    Gieorgij Adelson-Wielski, ros. Гео́ргий Макси́мович Адельсо́н-Ве́льский (ur. 8 stycznia 1922) - matematyk i informatyk rosyjski. W roku 1962, wraz z Jewgieniem Łandisem zaproponował sposób przechowywania danych w strukturze, nazwanej później drzewem AVL (od angielskiego zapisu jego nazwiska pochodzą litery A i V w skrócie AVL).Rotacja drzewa – w informatyce operacja polegająca na lokalnej zmianie struktury binarnego drzewa poszukiwań (BST) z zachowaniem porządku wierzchołków. Rotacje stosuje się w drzewach BST do uzyskania wyważenia drzewa i minimalizacji jego wysokości, co prowadzi do zmniejszenia kosztu operacji na drzewie.

    Koszt modyfikacji drzewa jest nieco większy niż dla zwykłego BST, ale za to własności drzewa AVL gwarantują, że pesymistyczny czas wyszukiwania elementu w drzewie o n węzłach wynosi 1.44(log2n), podczas gdy dla niezrównoważonego BST (w postaci listy) czas ten wynosi n.

    Drzewa AVL są często porównywane z drzewami czerwono-czarnymi, ponieważ pozwalają na wykonanie tych samych operacji (dodawanie, usuwanie oraz wyszukiwanie elementów) przy równej co do rzędu pesymistycznej złożoności czasowej O(log n). Przy powtarzających się wyszukiwaniach drzewa AVL są jednak wydajniejsze.

    Tablica asocjacyjna (tablica skojarzeniowa, mapa, słownik, ang. associative array, map, dictionary) – nazwa dla powszechnie stosowanego w informatyce abstrakcyjnego typu danych, który przechowuje pary (unikatowy klucz, wartość) i umożliwia dostęp do wartości poprzez podanie klucza.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. Dla pełnego drzewa BST o n węzłach pesymistyczny koszt każdej z podstawowych operacji wynosi O(log n). Złożoność obliczeniowa jest tak niska, ponieważ operacje wykonywane są wzdłuż drzewa. Z tego samego powodu w skrajnym przypadku, gdy drzewo składa się z jednej gałęzi koszt ten wzrasta do O(n). W literaturze często też podaje się koszt wykonania operacji w uzależnieniu od wysokości drzewa h - wynosi on O(h). Przechodząc drzewo metodą in-order, uzyskuje się ciąg wartości posortowanych niemalejąco.

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

    Podobnie jak w BST, nie jest możliwe, by drzewo posiadało dwa równe elementy. Zazwyczaj oznacza to, iż elementy muszą posiadać unikatowy klucz identyfikacyjny; problem polega na tym, że drzewa z równymi elementami – nawet po zmodyfikowaniu porządku dzielącego elementy do lewych i prawych poddrzew – nie da się później zrównoważyć. Problem ten można rozwiązać na przykład przez przechowywanie w węzłach drzewa list zawierających elementy o identycznych kluczach.

    Donald Ervin Knuth (ur. 10 stycznia 1938 r. w Milwaukee) – amerykański matematyk, informatyk, emerytowany profesor na katedrze informatyki Uniwersytetu Stanforda.Drzewo czerwono-czarne – rodzaj samoorganizującego się binarnego drzewa poszukiwań - struktury danych stosowanej w informatyce najczęściej do implementacji tablic asocjacyjnych. Została ona wynaleziona przez Rudolfa Bayera w 1972 roku, który nazwał je symetrycznymi binarnymi B-drzewami. Współczesną nazwę oraz dokładne zbadanie ich właściwości zawdzięcza się pracy "A dichromatic framework for balanced trees" z 1978 roku autorstwa Leo J. Guibasa oraz Roberta Sedgewicka.

    Operacje[ | edytuj kod]

    Algorytmy podstawowych operacji na drzewie AVL przypominają te z binarnych drzew poszukiwań, ale są poprzedzane lub następują po nich jedna lub więcej "rotacji". Algorytmy te mogą być realizowane poprzez rekurencję lub, co nawet prostsze, poprzez iteracyjne przechodzenie po krawędziach w górę lub w dół drzewa. Koszt każdej operacji to Ο(log n).

    Animacja przedstawiająca wstawienie kilku elementów do drzewa AVL. Obejmuje rotację lewą, prawą, lewo-prawą i prawo-lewą.

    Wstawianie[ | edytuj kod]

    Drzewo AVL ze współczynnikami wyważenia (zaznaczone kolorem zielony)

    Wstawianie do drzewa AVL może odbywać się tak, jak gdyby było ono zwyczajnym drzewem poszukiwań binarnych, następnie zaś są odtwarzane kroki w kierunku korzenia i wykonywane aktualizacje wyważeń węzłów. Zmiana wartości współczynnika wyważenia na 0 oznacza, iż wysokość poddrzewa nie została zmieniona. Operacja wstawiania jest wówczas zakończona. Zmiana współczynnika wyważenia na 1 lub -1 oznacza, iż poddrzewo, którego korzeniem jest rozważany wierzchołek, zachowało własność drzewa AVL, lecz jego wysokość uległa zwiększeniu. Informacja o tym przekazywana jest do ojca tego węzła.

    Jeśli współczynnik został zmieniony na 2 lub -2, to drzewo straciło własność AVL. Aby ją przywrócić, potrzebna jest rotacja. Maksymalnie będą potrzebne dwie rotacje, po których nie ma potrzeby wykonywania dalszych aktualizacji.

    Usuwanie[ | edytuj kod]

    Jeśli usuwany węzeł jest liściem, zostaje usunięty. Jeśli nie jest liściem, musi zostać zastąpiony największym elementem z jego lewego poddrzewa lub najmniejszym z jego prawego poddrzewa. Wyszukany największy lub najmniejszy element ma co najwyżej jedno dziecko, które zostaje teraz dzieckiem rodzica wyszukanego elementu. Po jego usunięciu odtwarzana jest ścieżka od rodzica wyszukanego elementu do korzenia, zaś współczynniki wyważenia są aktualizowane. Odtwarzanie może być zatrzymane, jeśli współczynnik wyważenia zostaje zmieniony na -1 lub 1, oznacza to bowiem, iż wysokość poddrzewa pozostaje niezmieniona. Zmiana współczynnika wyważenia na 0 oznacza zmniejszenie wysokości poddrzewa, aktualizowanie współczynników musi być kontynuowane. Jeśli współczynnik zostanie zmieniony na -2 lub 2, to wykonywana jest rotacja w celu przywrócenia struktury AVL. W przeciwieństwie do operacji wstawiania wystąpienie rotacji nie musi oznaczać, iż drzewo zostało wyważone. W pesymistycznym przypadku rotacje będą wykonywane aż do korzenia drzewa.

    Wyszukiwanie[ | edytuj kod]

    Wyszukiwanie w drzewie AVL jest wykonywane tak samo jak w niezrównoważonym BST dzięki serii porównań wartości wyszukiwanej z wierzchołkami, poczynając od korzenia. Wynik porównania oraz istnienie poddrzew pozwala stwierdzić, czy element szukany jest wierzchołkiem, znajduje się w lewym bądź prawym poddrzewie, czy też nie należy do drzewa. Zachowanie struktury AVL pozwala jednak na redukcję pesymistycznego czasu wyszukiwania do O(lg n).

    Operacja wyszukiwania nie modyfikuje struktury drzewa, więc nigdy nie pociąga wyważania drzewa (rotacji węzłów).

    Podstrony: 1 [2] [3]




    Reklama

    Czas generowania strony: 0.02 sek.