Drzewo AVL - wysokość i l.wierzchołkow

Odpowiedz Nowy wątek
2015-02-15 22:40
Meine_kleine
0

Mam krótkie pytanie.
Rozwiązujac zadania z drzew AVL natrafiłem na takie pytanie: Z ilu wierzchołków składa się najmniejsze drzewo AVL o wysokości 3?

Odpowiedź: 7

Teraz moje pytanie, dlaczego z 7 ? Nie wiem za bardzo czy nie mam mylnego pojęcia na temat definicji, bo według mnie z 3. Więc może mój błąd tkwi w mylnym zrozumieniu definicji wysokości drzewa i wierzchołków.

Jeśli ktoś mógłby mnie poprawić to chętnie zobaczę co nie tak w moim toku rozumowania:

Wysokość drzewa to maksymalna ilość liści w węźle, licząc od korzenia (pomijając sam korzeń, tj. licząc od korzenia zaczynamy od zera).

Wierzchołek drzewa to po prostu liść który nie ma dzieci + korzeń (też jest wierzchołkiem).

Dlaczego w takim bądź razie takie drzewo o 3 wierzchołkach nie spełnia wymagań zadania ?

Zdjęcie w załączniku, bo nie chce mi wstawić hiperłącza.

Pozostało 580 znaków

2015-02-15 23:35
1

Gdzie znalazłeś takie definicje? OO
http://pl.wikipedia.org/wiki/Drzewo
%28informatyka%29

A Twój przykład to nie jest AVL, bo węzeł 8 nie spełnia warunku, że wysokość lewego i prawego poddrzewa każdego węzła różni się co najwyżej o jeden (w tym przypadku 0 i 2).

Pozostało 580 znaków

2015-02-15 23:40
2

@ Meine_kleine te twoje definicje to z kosmosu jakieś. Wysokość drzewa to liczba węzłów od korzenia do liścia. AVL muszą byc zbalansowane, więc nie możesz mieć w żadnym węźle poddrzew o wysokości różniącej się o wiecej niż 1, bo wtedy należy wykonać rotacje.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0