Diskusia – AVL strom

Späť

Upozorňujeme, že diskusie pod našimi online kurzami sú nemoderované a primárne slúžia na získavanie spätnej väzby pre budúce vylepšenie kurzov. Pre študentov našich rekvalifikačných kurzov ponúkame možnosť priameho kontaktu s lektormi a študijným referentom pre osobné konzultácie a podporu v rámci ich štúdia. Toto je exkluzívna služba, ktorá zaisťuje kvalitnú a cielenú pomoc v prípade akýchkoľvek otázok alebo projektov.

Komentáre

Patrik Pastor

Člen

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?

Odpovedať

24.5.2019 18:10

Martin Dráb

Tvůrce

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.

Odpovedať

24.5.2019 19:42

2 + 2 = 5 for extremely large values of 2

Patrik Pastor

Člen

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.

Odpovedať

24.5.2019 20:07

Patrik Pastor

Člen

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

Odpovedať

24.5.2019 20:53

Martin Dráb

Tvůrce

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).

Odpovedať

24.5.2019 20:57

2 + 2 = 5 for extremely large values of 2

Patrik Pastor

Člen

Patrik Pastor:24.5.2019 20:59

a co teda postujes, nebo v jakem jazyce?

Odpovedať

24.5.2019 20:59

Patrik Pastor

Člen

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.

Odpovedať

24.5.2019 21:01

Martin Dráb

Tvůrce

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á :-) .

Odpovedať

24.5.2019 22:04

2 + 2 = 5 for extremely large values of 2

David Hartinger

Vlastník

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.

Editované 26.5.2019 16:59

Odpovedať

26.5.2019 16:58

New kid back on the block with a R.I.P

Patrik Pastor

Člen

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.

Odpovedať

26.5.2019 18:06

Robíme čo je v našich silách, aby bola tunajšia diskusia čo najkvalitnejšia. Preto do nej tiež môžu prispievať len registrovaní členovia. Pre zapojenie sa do diskusie sa zaloguj. Ak ešte nemáš účet, zaregistruj sa, je to zadarmo.

Zatiaľ nikto nevložil komentár - buď prvý!

Najčastejšie vyhľadávané

Diskusia – AVL strom