2. sada domácich úloh

Dokonca Theta(n log n), je to riešenie rekurencie T(n) = 2T(n/2) + n

To asi nie je tak celkom pravda, kedze nie je garantovane, ze uzlov v lavom a pravom podstrome bude priblizne rovnako. Staci zobrat degenerovany strom s linearnou hlbkou - tam to pojde k Theta(n^2). T.j. nasadi sa podobny argument, ako pri dokaze toho, ze QuickSort moze byt v najhorsom pripade az kvadraticky.

//EDIT: Jano ma predbehol a upravil svoj prispevok, takze moj komentar uz je neaktualny...

Pamat aspon O(h) bude treba, aby sa vedelo v strome navigovat (ulozenie navigacnej cesty). Usetrit pamat ide iba pri uplnych binarnych stromoch pri vhodnej reprezentacii.

//EDIT: Jano ma predbehol a upravil svoj prispevok, takze moj komentar uz je neaktualny...

:D

Ale zase som doplnil pekné intuitívne vysvetlenie ;)

Alebo intuitívne: Na hodnotu každého z n vrcholov sa pozrieme práve raz pri spracúvaní každého z jeho predkov, ktorých je O(log n).

Ale zase som doplnil pekné intuitívne vysvetlenie

Dokonca viac. Z tvojho intuitivneho argumentu vyplyva, ze casova zlozitost implementacie podla definicie je O(n.h), kde n je pocet uzlov stromu a h je vyska stromu. To dava O(n.log(n)) pre vyvazene stromy a O(n^2) pre degenerovane stromy.

no tak mala otazka.. vadi ak metoda pocet listov bude v public int?

no tak mala otazka.. vadi ak metoda pocet listov bude v public int?

Nielen, ze nevadi, ale to tak aj ma byt. V zadani som spravil chybu v hlavicke metody. Dakujem za upozornenie.

pytaj si bonusovy bod! (doc. krajci za najdenie chyby v skriptach dava tiez body)

v metode public int pocetListov() nema byt nejaky vstupny parameter este?

Nie, metoda pocetListov nema ziadne vstupne parametre. Jednoducho uzla sa pytame kolko listov ma strom, ktoreho on je korenom.

Komentar k ulohe removeAll. Aby ste sa vyhli sklamaniu z neakceptovania riesenia, pred odoslanim vyskusajte tieto zoznamy a odstranenie hodnoty 3:
[] - prazdny zoznam
[3]
[3, 3, 3, 3, 3]
[3, 3, 3, 3, 5, 5, 5, 3, 3, 3, 6, 6, 6, 3, 3, 3]

ked ma strom jeden uzol ktory je zaroven jeho korenom tak ma jeden list ci to za nepocita este ako list?

ked ma strom jeden uzol ktory je zaroven jeho korenom tak ma jeden list ci to za nepocita este ako list?

Ano, aj koren moze byt listom.