Witam,
Jestem studentem Informatyki . Mam problem z zdaniami z Algorytmów . http://imageshack.us/f/688/skancd.jpg/ Co do podpunktów f oraz g to nie mam pojęcia jak je rozwiązać . Może ktoś zna się na takiego typu zadaniach ? Byłbym bardzo wdzięczny .
Pozdrawiam Łukasz
f) dobrze wybierz element środkowy, a z reszty elementów zbuduj poddrzewa poddrzewa (itd. rekurencyjnie)
g) http://pl.wikipedia.org/wiki/Drzewo_AVL
A czy te pozostałe podpunkty są dobrze zrobione ?
Wygląda na to, że tak.
Kurcze , próbuję rozwiązać podpunkt f ale mi nie wychodzi . Mógłby ktoś wytłumaczyć na tym przykładzie jak to działa , najlepiej "jak krowie na rowie" bo mi się już wszystko miesza . Albo może ktoś zna dobrą stronkę gdzie jest ładnie to wytłumaczone na przykładzie .
Pozdrawiam
Mając elementy
1 5 2 4 3 7 6 8
Należy je posortować
1 2 3 4 5 6 7 8
Można przyjąć, że prawe i lewe poddrzewo będą miały tyle samo elementów, więc korzeń należy wybrać ze środka, czyli
1 2 3 (4) 5 6 7 8
lub
1 2 3 4 (5) 6 7 8
(ja wybieram pierwszą wersję)
Mamy korzeń i elementy na dwa poddrzewa:
5
1 2 3 4 6 7 8
Z każdego zbioru wybieramy element środkowy, który będzie korzeniem danego poddrzewa
5
1 (2) 3 4 6 (7) 8
I budujemy dalej...
5
2 7
1 3 4 6 8
I ostatecznie z
5
2 7
1 (3)4 6 8
powstaje
5
2 7
1 3 6 8
4
dzięki Ci bardzo , jednak taki nie mogę przyjąć . Muszę wg. Cormena ten przykład trzeba rozpisać na 1,5 strony ! . A i prządek pre-order i post-order jest też zły .