Zlozitost – Java – Fórum – Programujte.com

Vedel by niekto aku zlozitost ma inorder prehliadka stromu od najdeneho prvku ktory nie je korenom?

inorder - neserazeny
prehliadka stromu od najdeneho prvku - tomu prilis nerozumim, ale informatiku nestuduji; Obvykle prvek ve stromu hledas.
ktory nie je korenom - nemuze byt korenem nebo nemusi? V tom je rozdil, jestli od konecneho poctu odectes 1 nebo ne

Kdyz hledas prvek v neserazenem poli, ktery nemusi byt root, tak musis prohledat vsechny prvky. Takze nejspis slozitost by mela byt (1 az n).
Kdyz je pole serazeny, tak pulenim pole se da prvek najit za, ted vzorecek nevim, ale treba pro 100 prvku je to 100, 50, 25, 12/13, 6/7, 3/4, 2, 1 -> 1 az 8 kroku, cili slozitost (1 az 8). Coz je o neco lepsi nez (1 az 100) :)

Kdo vi, jakym zpusobem se prohledava strom. Mozna, ze prohledavas z kazde vetve min hodnotu a podle toho si zvolis, se kterou vetsi budes dal pracovat. A velikost vetve ma jakasi pravidla.
Cili, treba, pro 100 prvku mas 12 urovni, ktera ma pod sebou dalsi prvky. Prvky uvnitr urovne nemusi byt serazene, ale napric mezi jednotlivymi urovnemi je serazeni. Treba
1 | 2-7 | 3-4-5-6 (pro root=2), 8-9 (pro root=7)
Takze pak porovnavas x=<>1, x=<>2 nebo 7, x=<>3,4,5,6 nebo 8,9, pak mas (1 az 6) porovnani nebo (1 az 4). Cili soucet (urovni k urovni s hledanym cislem) + (pocet cisel v hledane vetvi) 2+4 nebo 2+2.

Ale, jak rikam, nejsem informatik.

Jo, pro to serazene pole, pulenim pole by strom vypadal asi takto, vzdy by se to vetvilo na 2 prvky:
50 (1-49, 51-100)
25 (1-24,26-49) | 75 (51-74, 76-100)
12 (1-12,13-24) | 37 (26-36, 38-49) | 63 (51-62, 64-74) | 88 (76-87, 89-100)
...
cili
50 | 25, 37 | 12, 37, 63, 88 | ...

Pro ten neserazeny, to nemusi byt v poradi
1 | 2-7 | 3-4-5-6 (pro root=2), 8-9 ale klidne zamichane. Jen vis, ze v te vetsni neni vetsi cislo nez v root
1 | 2-7 | 6-4-5-3 (pro root=2), 9-8
Tady jsem asi cisla nezvolil nejlip, spis to melo byt neco jako u toho serazeneho. S tim, ze tam nemusi byt jen 2 prvky pro vetveni, ale treba vic, jiny interval. Na to jsou nejaka pravidla, kolik jich tam muze byt, neznam.
50 | 25, 75 | 12 (1-12,13-24), 37, 63, 88 | ... serazeny, 2 prvky
50 | 25, 75 | 18 (1-17, 19-25), 37, 63, 88 | ... vice prvku, neserazeny