Nisi u pravu!
Recimo da imash ovakvo stablo :
Code:
x3
/ \
x2 x5
/ / \
x1 x4 x6
i ona predstavlja niz : x1, x2, x3, x4, x5, x6
E sad, ti zelish da na trece mesto ubacish elemenat E.
Dakle, niz ce izgledati ovako : x1, x2, E, x3, x4, x5, x6
a stablo ce izgledati ovako :
Code:
x3
/ \
x2 x5
/ \ / \
x1 E x4 x6
E sad, kad ti to E ubacish na svoje mesto, koje cesh cvorove morati da azurirash?
x2 i x3.
x4, x5 i x6 necesh biti potrebe da se azuriraju, jer E nije njihov potomak, pa samim tim i ne utiche na broj cvorova u njihovom podstablu.
Dakle, potrebno je azurirati samo one cvorove u cijem se podstablu nalazi novoubaceni cvor (a takvih cvorova ima log N)!
Mislim da je jednostavnije da se za svaki cvor pamti kompletna velicina njegovog podstabla, a ne samo velicina njegovog levog podstabla!
mmmmmm.. aahhhhhh..
e, nije sex nego serem!