Drzewo dokładnie wyważone

[daniel285]

Czy istnieje jakaś szybka metoda na tworzenie drzewa dokładnie wyważonego?
Bo mi ciąg 14,5,7,12,11,4,6,2,13,16,15,9,1,3,8,18,17,10 zajmie ze 4 kartki A4 i mnóstwo czasu.
Ja wyważam od razu po wstawieniu elementu jeśli zaburzył on równowagę.

Czy te definicje są poprawne:
Drzewo dokładnie wyważone - ilość węzłów lewego i prawego poddrzewa nie może różnić się więcej niż o 1 (czy węzłami są też liście?)
Drzewo wyważone - wysokość lewego i prawego poddrzewa nie może różnić się więcej niż o jeden.
??

Czy istnieje drzewo, którego nie można wyważyć?

[Crizz]

Rozumiem, że ma to być drzewo poszukiwań binarnych?

Czy istnieje jakaś szybka metoda na tworzenie drzewa dokładnie wyważonego?

No a jaka liczba musi być korzeniem drzewa, żeby do lewego i prawego poddrzewa trafiło (mniej wiecej) po równo liczb? To samo dla korzenia każdego poddrzewa w tym drzewie. Chyba, że chcesz koniecznie wstawiać węzły do drzewa jakimś algorytmem.

Czy te definicje są poprawne:
Drzewo dokładnie wyważone - ilość węzłów lewego i prawego poddrzewa nie może różnić się więcej niż o 1 (czy węzłami są też liście?)
Drzewo wyważone - wysokość lewego i prawego poddrzewa nie może różnić się więcej niż o jeden.
??

Tak.

(czy węzłami są też liście?)

Z reguły tak.

Czy istnieje drzewo, którego nie można wyważyć?

Nie.

[daniel285]

Czyli rozumiem, że elementów nie trzeba wstawiać po kolei (o ile na egzaminie nie będzie takiego polecenia)

Moze być?

[Crizz]

Hmmm... ciężko mi odpowiedzieć na to pytanie. Jeśli masz znać metody rotacji drzew AVL, to być może będziesz musiał się nimi popisać. Jeśli masz natomiast pokazać końcowy wynik, to nie widzę sensu. Generalnie to ostateczny kształt drzewa idealnie zrównoważonego w mniejszym stopniu zależy od kolejności wstawiania liczb, niż w przypadku zwykłego drzewa BST (różnica polega tylko na tym, że mamy na każdym poziomie drzewa dwie możliwości, jeśli mediana liczb, które mają się znaleźć w poddrzewie, wypada pomiędzy dwoma liczbami).