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

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.

1

Gdzie znalazłeś takie definicje? O_O
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).

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.

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