Drzewa AVL …
Co to jest AVL?? Jest to zrównoważone drzewo poszukiwań binarnych ( BST ), w którym wysokość lewego i prawego poddrzewa każdego węzła różni się maxymalnie o jeden. Tyle w wielkim skrócie.
Jakie zalety ?
Otóż maksymalna wysokość drzewa AVL składającego się z n “danych” wynosić 1,44*log2(n), a drzewa BST niezrównoważonego n.
Wady ( jeśli można to tak nazwać )
Potrzeba wykonania rotacji ( 2 typy po 2 rotacje ):
RR - rotacja pojedyncza prawa
LL - rotacja pojedyncza lewa
RL - rotacja podwójna lewa ( najpierw prawa potem lewa )
LR - rotacja podwójna prawa ( najpierw lewa potem prawa )
szczegółów nie będę opisywał teraz.
Dlaczego pisze akurat o AVL?
Ponieważ na zajęciach z programowania wraz z kolegą dostaliśmy propozycję zaliczenia zajęć “w inny sposób niż kolokwia itd”. To właśnie realizacja tej propozycji.
Naszym zadaniem było napisanie pełnej obsługi drzewa AVL, wstawianie, usuwanie, szukanie, rotacje itd. Dodatkowo mieliśmy zaprezentować wszystko graficznie i przygotować porządną dokumentację.
Oczywiście stawiają wymagania to trzeba… wypełnić je z nawiązką. Dlatego zdecydowaliśmy się dodatkowo zrobić:
(in|pre|post)order - prościzna
BFS - Szukanie wszerz drzewa.
Drukowanie struktury drzewa w trybie TXT w poziomie.
Generowanie XML z historią operacji na drzewie AVL ( biblioteka mini-xml okazała się pomocna ).
Prezentowanie graficzne historii operacji na drzewie ( za źródło służy ww. XML ) w SVG.
Odczyt drzewa z pliku.
Graficznie prezentujemy wszystko w SVG. Poniżej png z wyglądem drzewa.
Dzięki SVG ten obrazek jest czytelny w dowolnej wielkości ( nie zachodzi “pixeloza” ), tutaj umieściłem jednak PNG, bo przeglądarka na “I” nie obsługuje SVG.
Historia operacji na drzewie, na przykładzie rotacji LR.
Znowu umieściłem PNG nie SVG.
Cały projekt będzie dostępny w internecie na początku czerwca. Po oficjalnej prezentacji na uczelni.
Oczywiście kody źródłowe wszystkich plikół również będą dostępne.
Z ciekawostek.
Generowanie SVG zajęło nam ~800 linii kodu.