AVL - drzewo BST
-
- Użytkownik
- Posty: 48
- Rejestracja: 8 cze 2008, o 14:27
- Płeć: Mężczyzna
- Lokalizacja: oświęcim
- Podziękował: 9 razy
AVL - drzewo BST
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
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
-
- Użytkownik
- Posty: 4094
- Rejestracja: 10 lut 2008, o 15:31
- Płeć: Mężczyzna
- Lokalizacja: Łódź
- Podziękował: 12 razy
- Pomógł: 805 razy
AVL - drzewo BST
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.
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.
-
- Użytkownik
- Posty: 48
- Rejestracja: 8 cze 2008, o 14:27
- Płeć: Mężczyzna
- Lokalizacja: oświęcim
- Podziękował: 9 razy
AVL - drzewo BST
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ę?
i wtedy wychodzi 10-13 [ i z 10tki jeszcze 17stka wychodzi i 19stka ? ]
dobrze to w ogóle robię?
-
- Użytkownik
- Posty: 4094
- Rejestracja: 10 lut 2008, o 15:31
- Płeć: Mężczyzna
- Lokalizacja: Łódź
- Podziękował: 12 razy
- Pomógł: 805 razy
AVL - drzewo BST
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.
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.
-
- Użytkownik
- Posty: 48
- Rejestracja: 8 cze 2008, o 14:27
- Płeć: Mężczyzna
- Lokalizacja: oświęcim
- Podziękował: 9 razy
AVL - drzewo BST
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 ?
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 ?
-
- Użytkownik
- Posty: 4094
- Rejestracja: 10 lut 2008, o 15:31
- Płeć: Mężczyzna
- Lokalizacja: Łódź
- Podziękował: 12 razy
- Pomógł: 805 razy
AVL - drzewo BST
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.
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.
-
- Użytkownik
- Posty: 48
- Rejestracja: 8 cze 2008, o 14:27
- Płeć: Mężczyzna
- Lokalizacja: oświęcim
- Podziękował: 9 razy
AVL - drzewo BST
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
-
- Użytkownik
- Posty: 4094
- Rejestracja: 10 lut 2008, o 15:31
- Płeć: Mężczyzna
- Lokalizacja: Łódź
- Podziękował: 12 razy
- Pomógł: 805 razy
AVL - drzewo BST
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.
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.
-
- Użytkownik
- Posty: 48
- Rejestracja: 8 cze 2008, o 14:27
- Płeć: Mężczyzna
- Lokalizacja: oświęcim
- Podziękował: 9 razy
AVL - drzewo BST
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
bo jeśli tak to musiałbym zrobić 2 rotacje naraz a kompletnie nie mam pojęcia jakby to wyglądało