NOVINKA: Získej 40 hodin praktických dovedností s AI – ZDARMA ke každému akreditovanému kurzu!

Diskuze – Lekce 7 - AVL strom

Zpět

Upozorňujeme, že diskuze pod našimi online kurzy jsou nemoderované a primárně slouží k získávání zpětné vazby pro budoucí vylepšení kurzů. Pro studenty našich rekvalifikačních kurzů nabízíme možnost přímého kontaktu s lektory a studijním referentem pro osobní konzultace a podporu v rámci jejich studia. Toto je exkluzivní služba, která zajišťuje kvalitní a cílenou pomoc v případě jakýchkoli dotazů nebo projektů.

Komentáře
Avatar
Patrik Pastor
Člen
Avatar
Patrik Pastor:24.5.2019 18:10

wtf? zadna graficka ukazka jenom popis na 5 radku?? CO to jako je? Na youtube jsou sice animace ale nechapu moc to pocitani na uzlech. Treba to vice vysvetlit, autor pospichal na vlak?

 
Odpovědět
24.5.2019 18:10
Avatar
Martin Dráb
Tvůrce
Avatar
Odpovídá na Patrik Pastor
Martin Dráb:24.5.2019 19:42

CO to jako je?

I tak může vypadat práce komunity. Ne vždycky mají ti, co část svého času věnují práci na obecně prospěšných projektech, dostatek času, energie či nálady, aby své dílo dokončili v dostatečné kvalitě. Samozřejmě se nejedná o ideální stav, ale je třeba se naučit žít s tím, co máme. Kromě toho, hodnocení článku poměrně jasně říká, že zde asi není všechno v pořádku..

Zrovna téma AVL stromů je dobře zpracovány na mnoha místech včetně např. anglické Wikipedie.

Na youtube jsou sice animace ale nechapu moc to pocitani na uzlech.

V každém uzlu se uchovává informace o rozdílu hloubek jeho levého a pravého podstromu (stromu majícího za kořen jeho levého resp. pravého syna). Definice AVL vynucuje, aby tento rozdíl byl nejvýše roven jedné. Pokud tato podmínka platí, dá se dokázat, že hloubka takového stromu je řádově dvojkový logaritmus z počtu uzlů, což právě zajišťuje logaritmickou složitost operací vkládání, mazání a vyhledávání (a logaritmická složitost je dobrá složitost).

Rotace právě slouží k úpravě hloubek podstromů (na definici klidně mrkni na Wikipedii; jsou tam obrázky i pseudokód). Doporučuji si všechno pěkně rozkreslit (všechny případy, co mohou nastat – není jich tak moc).

Také doporučuji si zkusit AVL strom (třeba podle rozkreslení zmíněného v minulém odstavci) zkusit naimplementovat. Na rozdíl třeba od červeno-černých stromů, které mají lepší vlastnosti při mazání (není třeba v nejhorším případě provádět logaritmický počet rotací), má výsledný kód jen pár obrazovek (a to i na rozlišeních, které se běžně používaly před dvanácti lety). Můžu poskytnout svoji implementaci, ale myslím, že ji diskvalifikuje použitý jazyk (Object Pascal).

P.S.
Myslím, že při vkládání vždy stačí konstantní počet rotací, není třeba postupovat až do kořene, ale to je pro obvyklá užití detail.

Odpovědět
24.5.2019 19:42
2 + 2 = 5 for extremely large values of 2
Avatar
Patrik Pastor
Člen
Avatar
Odpovídá na Martin Dráb
Patrik Pastor:24.5.2019 20:07

dik, uz sem se dival na to youtube jak jsem psal, protoze to potrebuji vysvetlit krok po kroku (jsem samouk), wle pochopil jsem. Reakce byla spis na filozofii tady nekterych clanku, nejsem hater, rad si je ctu (jinak bych za to neplatil), ale nektere clanky jsou proste odflaknute, chapu ze nekdo treba nema cas, ale tak at to potom nedela vubec. Zacatecniky jako ja to jenom zmate, viz srial o sql, tam na to nadava hodne lidi. Ale abych nebyl jenom negativni treba tvuj koment pomuze, myslim si, ze kdybys treba toto napsal ty, bylo by to lidstejsi.

 
Odpovědět
24.5.2019 20:07
Avatar
Patrik Pastor
Člen
Avatar
Patrik Pastor:24.5.2019 20:53

A dalsi vec krom toho ze to chapu "na papire", nevim jak by vypadal zdrojovy kod. Tady prave ani neni prilozeni, v minule lekci byl, dalsi chyba

 
Odpovědět
24.5.2019 20:53
Avatar
Martin Dráb
Tvůrce
Avatar
Odpovídá na Patrik Pastor
Martin Dráb:24.5.2019 20:57

ale nektere clanky jsou proste odflaknute, chapu ze nekdo treba nema cas, ale tak at to potom nedela vubec.

Máš pravdu, že kvalita článků je tady dost různá. Na druhou stranu se na to je třeba dívat z dlouhodobější perspektivy. ITNetwork má teď poměrně rozsáhlou komunitu, ale pamatuji, doby, kdy teprve začínal (což by se asi teď dalo říci o jeho anglické verzi). Obsahu bylo málo, lidí ještě méně, takže laťka byla nastavena dosti nízko (resp. myslím si, že tomu tak nějak bylo, aby se to tu rozrůstalo (problém se schopnými lidmi totiž je obvykle ten, že jakmile dosáhnout určitého věku, přestanou mít čas :-) ).

Souhlasím, že by bylo fajn, kdyby ty články někdo průběžně procházel a rozšířil ty, kde něco podstatného chybí.

Ale abych nebyl jenom negativni treba tvuj koment pomuze, myslim si, ze kdybys treba toto napsal ty, bylo by to lidstejsi.

Tak, stát se to klidně může. Aktuálně mám ale rozepsaný takový tutoriál na jiné téma, takže těžko říci, kdy se dostanu k popisu algoritmů (ač třeba AVL stromy mám rád).

Odpovědět
24.5.2019 20:57
2 + 2 = 5 for extremely large values of 2
Avatar
Patrik Pastor
Člen
Avatar
Odpovídá na Martin Dráb
Patrik Pastor:24.5.2019 20:59

a co teda postujes, nebo v jakem jazyce?

 
Odpovědět
24.5.2019 20:59
Avatar
Patrik Pastor
Člen
Avatar
Odpovídá na Martin Dráb
Patrik Pastor:24.5.2019 21:01

nechtel bys neco o assembleru? To jsem tu nikde nevidel, je sice pravda, ze nez bych se k tomu dostal trvalo by to, ale chci zacit posleze C-cko kde by se assembler taky hodil, a vidim ze te bavi, tak jenom me to napadlo.

 
Odpovědět
24.5.2019 21:01
Avatar
Martin Dráb
Tvůrce
Avatar
Odpovídá na Patrik Pastor
Martin Dráb:24.5.2019 22:04

nechtel bys neco o assembleru? To jsem tu nikde nevidel, je sice pravda, ze nez bych se k tomu dostal trvalo by to, ale chci zacit posleze C-cko kde by se assembler taky hodil, a vidim ze te bavi, tak jenom me to napadlo.

Právě Assembleru se ten tutoriál týká :-).

Odpovědět
24.5.2019 22:04
2 + 2 = 5 for extremely large values of 2
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Patrik Pastor
David Hartinger:26.5.2019 16:58

Hejtuj autora za to, že napsal něco zadarmo pro komunitu a ještě k tomu piš vulgární komentáře, to se mi snad zdá. Jelikož to není první reakce z tvé strany na free článek, za další ti zakáži do diskuzí přispívat a můžeš se to učit třeba z youtube.

Editováno 26.5.2019 16:59
Odpovědět
26.5.2019 16:58
New kid back on the block with a R.I.P
Avatar
Patrik Pastor
Člen
Avatar
Odpovídá na David Hartinger
Patrik Pastor:26.5.2019 18:06

Beru v potaz, ze jsem si neuvedomil, ze to neni premiovy obsah, nicmene jsem stale zacatecnikem, takze mi tento clanek moc nepomohl (ale beru to, autor to delal bez honorare), nicmene dokud tady za clanky platim (a myslim ze jsem toho uz u vas dost zaplatil, to urcite vite), tak ma pravo tady komentovat (ano - slusne. Moje reakce byla mozna trochu tvrdsi, ale urcite ne vulgarni jak pises). A za trochu ironie se tedy omlouvam. Presto mi ale nikdo nemuze vzit moznost komentovat clanek, dokud za neho platim.

 
Odpovědět
26.5.2019 18:06
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 10 zpráv z 15.