ITnetwork Flashka zdarma C# týden
Akce! Pouze tento týden sleva až 80 % na kurzy C# .NET. Lze kombinovat s akcí 50 % bodů navíc na prémiový obsah!
Brno? Vypsali jsme pro vás nové termíny školení Základů programování a OOP v Brně!

AVL strom

Unicorn College Tento obsah je dostupný zdarma v rámci projektu IT lidem.
Vydávání, hosting a aktualizace umožňují jeho sponzoři.

AVL strom je binární vyhledávací strom s jednou podmínkou navíc: V každém vrcholu stromu se hloubka jeho levého a pravého podstromu liší nejvýše o jedna. Tato podmínka zajistí, že strom nemůže příliš zdegenerovat, na rozdíl od běžného binárního stromu, který může skončit jako lineární spojový seznam. Jeho implementace je jednodušší, než u dokonale vyváženého stromu. Strom má i v nejhorším případě zajištěnu logaritmickou hloubku vůči počtu uložených vrcholů.

Vyhledání

Vyhledání probíhá stejně jako u binárního stromu. Pokud je hledaná hodnota rovna klíči ve vrcholu, nalezli jsme správný vrchol. Pokud je hodnota vetší než klíč, hledáme dál v pravém podstromu, respektive pokud je hodnota menší, hledáme dál v levém podstromu. Jestliže porovnáváme vrchol, který neexistuje (jeho ukazatel je null místo adresy), pak hledaná hodnota ve stromu není.

Vkládání

Nejprve nalezneme místo pro vložení nového vrcholu. Podobně jako při vyhledání porovnáme hodnotu klíče aktuálního vrcholu s vkládanou hodnotou. Jestliže nyní dojde ke shodě, snažíme se uložit prvek, který již uložen je a můžeme skončit. Pokud dojdeme k neexistujícímu vrcholu (ukazatel je null) přidáme na jeho místo nový list do něhož vkládáme.

Tím jsme mohli zvýšit hloubku všech vrcholů ležících na cestě ke kořenu. Musíme tedy ověřit, zda strom stále splňuje podmínku AVL a případnou chybu opravit pomoci rotací. Bez újmy na obecnosti předpokládejme, že nový vrchol je levý syn(vnuk...) vrcholu X. Pokud hloubka levého podstromu ve vrcholu X byla menší než pravého podstromu, jsou nyní stejné a celková hloubka podstromu ve vrcholu X se nezměnila. Pokud byly hloubky stejné, je nyní levá delší, což není nijak na škodu, ale musíme tuto informaci předat dále otci vrcholu X. Pokud byla hloubka levého podstromu větší než pravého, je nyní větší o dva a musíme použít rotaci. Nejprve zjistíme vyváženost našeho levého syna X, vrchol Y. Pokud je převážen doleva použijeme pravou rotaci. Vrchol X i Y jsou nyní vyvážené a hloubka celého podstromu se nezměnila – končíme. Druhá možnost, kdy Y bude vyvážen, nastat nemůže. Takže třetí možnost Y je převážena doprava, použijeme pravou dvojitou rotaci přes pravého syna Y jehož hloubka se zvýší o jedna a je nyní vyvážen. Hloubka podstromu se nezměnila a končíme.

Vymazání

Opět nejprve nalezneme správný vrchol průchodem od kořene jako při vyhledávání. Pokud dojdeme k neexistujícímu vrcholu, snažíme se smazat vrchol, který neexistuje a máme hotovo. Jinak dorazíme k hledanému vrcholu a budeme se dál rozhodovat dle počtu jeho synů. Pokud náš vrchol X nemá žádného syna, tak ho smažeme (do ukazatele na něj vložíme null). Pokud má jednoho syna, můžeme opět ihned smazat. Tentokrát místo null vložíme do ukazatele na vrchol X ukazatel na jeho syna(čímž X „přeskočíme“). Pokud má vrchol X dva syny, najdeme vrchol Y, jakožto maximum z levého podstromu (mohli bychom i minimum z pravého). Hodnotou Y nahradíme hodnotou ve vrcholu X a následně ze stromu odstraníme vrchol Y. Vlastnost binárního vyhledávacího stromu neporušíme, protože Y bylo maximum z levého podstromu, tudíž vše vlevo je stále menší než hodnota nového Y a vše vpravo zas větší. Odstraněním jsme ale mohli porušit vlastnost AVL stromu. Každý vrchol na cestě od smazaného vrcholu ke kořeni může být nyní špatně vyvážen, to budeme opět opravovat rotací. V každém vrcholu, který obdrží informaci o zkrácení hloubky v jednom z jeho podstromů, se budeme rozhodovat. Opět předpokládejme, že informace přijde od levého syna. Pokud byl vrchol převážen doleva, je nyní vyvážen, ale snížila se celková hloubka podstromu s kořenem v X a tuto informaci předáme výše. Pokud byl vrchol vyvážen, tak nyní přepadává doprava, ale celková hloubka se nezměnila a můžeme skončit. Třetí možnost je, že byl vrchol převážen doprava a nyní je tedy převážen o dva, a to vyřešíme rotací podle pravého syna. Pokud je pravý syn převážen doleva, použijeme dvojitou rotaci vlevo. Hloubka podstromu se snížila, o čemž informujeme výše. Pokud je pravý syn vyvážen, rotujeme vlevo přes pravého syna. Vrchol X je nyní vyvážen a celková hloubka se nezměnila. Pokud je pravý syn vrcholu X převážen doprava, použijeme opět levou rotaci. Levý syn a vrchol X jsou nyní vyváženi, ale celková hloubka se snížila, to oznámíme o úroveň výš.

Složitost

V nejhorším případě (nejvzdálenější list od vrcholu) se nám podaří nalézt správný vrchol za log(N) porovnání, které jsou v konstantním čase. Samotná operace vložení či mazání děláme v konstantním čase, stejně tak jako rotace (přepojení ukazatelů). Pokud bude nutné strom vyvažovat pokaždé při zpětném průchodu po operacích vložení a smazání prvku, které změnily strukturu. Rotace budeme v nejhorším případě muset použit log(N) krát. Což se ale schová do multiplikativní konstanty. Všechny operace provádíme v log(N).


 

 

Aktivity (2)

 

 

Komentáře
Zobrazit starší komentáře (2)

Avatar
Patrik Pastor:24. května 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. května 20:07
Avatar
Patrik Pastor:24. května 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. května 20:53
Avatar
Martin Dráb
Redaktor
Avatar
Odpovídá na Patrik Pastor
Martin Dráb:24. května 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  +1 24. května 20:57
2 + 2 = 5 for extremely large values of 2
Avatar
Odpovídá na Martin Dráb
Patrik Pastor:24. května 20:59

a co teda postujes, nebo v jakem jazyce?

 
Odpovědět 24. května 20:59
Avatar
Odpovídá na Martin Dráb
Patrik Pastor:24. května 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. května 21:01
Avatar
Martin Dráb
Redaktor
Avatar
Odpovídá na Patrik Pastor
Martin Dráb:24. května 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  +1 24. května 22:04
2 + 2 = 5 for extremely large values of 2
Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:26. května 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. května 16:59
Odpovědět 26. května 16:58
Jsem moc rád, že jsi na síti, a přeji ti top IT kariéru, ať jako zaměstnanec nebo podnikatel. Máš na to! :)
Avatar
Odpovídá na David Čápka
Patrik Pastor:26. května 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. května 18:06
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Patrik Pastor
David Čápka:26. května 19:18

To chápu, tak to stačí napsat normálně a já to předám dál. Už ti to zde říkalo několik lidí, že se máš vyjadřovat na úrovni, já ti neberu problém, ale tvojí reakci na něj. Dám vědět Ondrovi, co u nás teď píše o algoritmech, aby to upravil.

Odpovědět 26. května 19:18
Jsem moc rád, že jsi na síti, a přeji ti top IT kariéru, ať jako zaměstnanec nebo podnikatel. Máš na to! :)
Avatar
Odpovídá na David Čápka
Patrik Pastor:26. května 19:40

ok, budu se snazim byt mene agresivni v komentarich. jenom to trochu budu chtit dovysvetlit, pokud z clanku to nepochopim.

 
Odpovědět 26. května 19:40
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 12. Zobrazit vše