AVL - drzewo BST

[iveldion]

AVL
Dla podanego ciągu wartości narysuj drzewo BST. Gdy kolejny wstawiany element zaburzy równowagę zaznacz podwójnym kółkiem najniższy węzeł niezrównoważony i narysuj drzewo zrównoważone dokonując właściwych rotacji kolejne elementy wstawiaj do drzewa zrównoważonego
ciąg znaków:8,3,17,19,13,6,10,15,18,20,1,4,16,14,12,9,11,7,5
tutaj jest drzewo BST


jak ja mam dalej zrobić to zadanie? Bo wsumie umie narysować to drzewo

[Crizz]

Hmmm... drzewo, które narysowałeś, jest zrównoważone, ale w wyniku wykonania podanego zadania, otrzymane drzewo miałoby inny układ węzłów.

Zacznij rysować to drzewo przez wstawianie wartości w podanej kolejności. Cały czas musisz kontrolować zrównoważenie każdego z węzłów drzewa (różnica wysokości lewego i prawego poddrzewa) może być równa jedynie \(\displaystyle{ -1,0,1}\) - zawsze, kiedy osiagnie \(\displaystyle{ 2}\) lub \(\displaystyle{ -2}\), trzeba wykonac odpowiednią rotację. Podpowiem, że trzeba będzie po drodze wykonać dwie rotacje typu RL. Najlepiej wpisz w google "Drzewo AVL", znajdziesz rodzaje rotacji.

[iveldion]

kurde, no nie umiem tego zrobić: wychodzi mi że rotacja rl byłaby w ułożeniu 17-13-10 [ i z 17stu wychodzi jeszcze gałąź 19ście) a z 2giej strony byłoby 3-6
i wtedy wychodzi 10-13 [ i z 10tki jeszcze 17stka wychodzi i 19stka ? ]
dobrze to w ogóle robię?

[Crizz]

Rozumiem, że mówisz o tym etapie drzewa?



Uploaded with

Przy każdym węźle podałem jego zrównoważenie. Jak widać, żaden nie ma zrównoważenia \(\displaystyle{ -2}\) ani \(\displaystyle{ 2}\), więc nie ma porzeby robienia żadnej rotacji. Na razie jeszcze wstawiaj dalej. Chyba, że masz na myśli inny etap, to najlepiej napisz, jaki. Moim zdaniem, pierwsza rotacja, której potrzebujemy, jest później i jest inna.

[iveldion]

nie rozumiem kompletnie zasady zrównoważenia przeczytałem już dosyć dużą ilość artykułów na temat zrównoważenia ale nie mogę tego załapać

13stka ma 1 dlatego że pod nią jest nastepna liczba ?
6 19 ma 0ro bo są na tej samej linii ? i pod nimi już nic nie ma ?
to czemu 10 też ma 0ro ?


Uploaded with
i teraz 18 i 20 ma 0ro ?

[Crizz]

Jak już mówiłem, zrównoważenie węzła to różnica między wysokością lewego i prawego poddrzewa. Przykładowo, dla węzła o kluczu 8 w Twoim rysunku: lewe poddrzewo, które zaczyna się w węźle 3, ma wysokość 2 (najdłuższą ścieżka jest 3-6), a prawe poddrzewo, które zaczyna się w węźle 17, ma wysokość 3 (najdłuższą ścieżką jest np. 17-13-10 lub 17-19-18). Stąd zrównoważenie węzła 8 wynosi \(\displaystyle{ 2-3=-1}\).

Liście, czyli tutaj węzły o kluczach 6,10,15,18,20 będa miały oczywiście zrównoważenie 0, bo ich lewe i prawe poddrzewa są puste, zatem mają wysokość 0.

Węzeł 13 będzie miał zrównoważenie 0, bo zarówno jego lewe, jak i jego prawe poddrzewo ma wysokość 1 i \(\displaystyle{ 1-1=0}\) itd.

Ok, to może jeszcze podpowiem: wg mnie (o ile się nie rąbnąłem gdzieś po drodze) pierwsza rotacja jest potrzebna po wstawieniu klucza 11.

[iveldion]

tak ma być ?
i teraz po rotacji będzie ;>
wg moich obliczeń
][img]http://img84.imageshack.us/img84/746/avl1223.jpg

wtedy trza zrobić znów rotacje z 12stką;> bo wsumie nie miałem pojęcia co z nią robić ;p

[Crizz]

Nie jest OK przed rotacją, bo 9 jest źle wstawione - u Ciebie jest prawym synem 10, a jest przecież mniejsze, niż 10. Prawidłowo ten kawałek powinien wyglądać tak:



Uploaded with

I teraz źle zrównoważony jest węzeł o kluczu 17 i to przy nim trzeba majstrować z rotacją.

Sorki, ale pomylił mi się rodzaj rotacji, bo (nie wiem czemu, ale) uznałem, że trzeba tu zrównoważyć korzeń, a nie węzeł 17. Tu oczywiście potrzeba rotacji LL.

Jeśli lukniesz na drugi link w googlach, to chodzi o coś takiego:

[url=http://img823.imageshack.us/i/rotb.png/][/url]

Uploaded with [url=http://imageshack.us]ImageShack.us[/url]

i ten układ trzeba poddać rotacji.

[iveldion]

a jak się rotacje BR i AR robi ? chyba że te rotacje mam czytać od 17ski ;>
bo jeśli tak to musiałbym zrobić 2 rotacje naraz a kompletnie nie mam pojęcia jakby to wyglądało