johny píše: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.