AVL-strom

Ukázka ne-AVL stromu

Stejný strom poté, co byl vyvážen

AVL strom je datová struktura pro uchovávání údajů a jejich vyhledávání. Pracuje v logaritmicky omezeném čase. Jedná se o samovyvažující se binární vyhledávací strom.

Jméno stromu pochází z iniciál jeho objevitelů. G. M. Adelson-Velsky a E. M. Landis popsali tuto strukturu v roce 1962 v článku An algorithm for the organization of information. Dokázali, že AVL-strom bude maximálně o 45 % vyšší než dokonale vyvážený strom, složený ze stejných vrcholů. Pokud v(n) je výška AVL-stromu s n uzly, potom platí

log(n+1) ≤ v(n) ≤ 1.4404 log(n+2) − 0.328.

[editovat] Vlastnosti vrcholů AVL stromu

Vrchol má maximálně dva následníky (je to binární strom).
V levém podstromu vrcholu jsou pouze vrcholy s menší hodnotou klíče (je to binární vyhledávací strom).
V pravém podstromu vrcholu jsou pouze vrcholy s větší hodnotou klíče (je to vyhledávací strom).
Délka nejdelší větve levého a pravého podstromu se liší nejvýše o 1 (vyvážení AVL stromu).

[editovat] Vlastnosti AVL stromu

Hlavní vlastností AVL stromu je, že definice nedovoluje, aby strom zdegeneroval, tj. zajišťuje vyváženost stromu. Pokud označíme i výšku stromu reprezentujícího množinu o velikosti n, platí následující:

$\frac {c_1}{\sqrt {5}}(\frac {1+ \sqrt {5}}{2})^{i+2} -1 < F_{i+2} - 1 <= n < 2^{i} -1$ ,

kde $F i$ je i-té Fibonacciho číslo. Z toho plyne, že výška stromu je úměrná logaritmu velikosti reprezentované množiny.

[editovat] Operace

Na AVL stromech je možno v čase O(log(N)) provádět následující operace:

vyhledání uzlu
vložení uzlu
zrušení uzlu

[editovat] Vyhledání uzlu v AVL stromu

Vyhledávání uzlu v AVL stromu se realizuje stejně jako u binárního vyhledávacího stromu. Tato operace neklade žádné speciální požadavky a nemění strukturu stromu.

[editovat] Vkládání do AVL stromu

Přidáváme-li nebo rušíme-li vrchol ve vyváženém stromu, může se ovšem stát nevyváženým.

Koeficient vyváženosti i-tého uzlu B_i = | v_{L_i} - v_{R_i} |, kde v_{L_i} je výška levého podstromu i-tého uzlu a v_{R_i} je výška pravého podstromu i-tého uzlu. Strom s kořenem i je vyvážený, jestliže B_i ≤ 1. Předpokládejme, že přidáme uzel do levého podstromu. Pokud si označíme K kořen, L levý, P pravý podstrom a v_L, v_P jejich výšky, pak před přidáním bude platit jedna z následujících možností:

v_L = v_P: Po přidání bude tedy výška levého podstromu o jedničku větší než je výška pravého podstromu, a proto bude vyváženost stromu zachována.
v_L < v_P: Po přidání budou výšky podstromů sobě rovny a kritérium vyváženosti se tedy ještě zlepší.
v_L > v_P: Po přidání bude výška levého podstromu o dvě větší než je výška pravého podstromu a bude kritérium vyváženosti stromu porušeno.

Před vložením hodnoty nejprve zjistíme, zda se daný uzel ve stromu již nenachází. Pokud takový uzel neexistuje, pak přidáme nový stejně jako u binárního vyhledávacího stromu a určíme pro něj koeficient vyváženosti. Potom následuje zkontrolování koeficientu vyváženosti pro každý uzel na cestě směrem ke kořeni stromu. Není-li splněno kritérium vyváženosti, musíme provést vyvažování stromu pomocí cyklické záměny ukazatelů (rotace stromu).

Při operaci vkládání a rušení je zapotřebí uchovávat o každém uzlu jeho koeficient vyváženosti. Proto je vhodné tento koeficient ukládat do každého vrcholu.

[editovat] Vyvažování AVL stromu

Operace potřebné pro vyvažování jsou realizovány cyklickými záměnami ukazatelů. Můžeme provádět jednoduché RR-rotace, LL-rotace nebo dvojité LR-rotace, RL-rotace. Při rotaci je nutné aktualizovat koeficient vyváženosti každého rotovaného uzlu.

Na první ukázce je po přidání uzlu 1 porušena vyváženost stromu, protože u uzlu 5 a uzlu 4 nabývá koeficient vyváženosti hodnoty 2. Jednoduchou LL-rotací získáme opět vyvážený strom. U druhé ukázce je po vložení vrcholu 7 porušena vyváženost, která je odstraněná RR-rotací.

Ukázka RR-rotace stromu

Ukázka LL-rotace stromu

Přidáním uzlu 3 se naruší kritérium vyváženosti kořene 5. Znovuvyvážení dosáhneme složitější LR-rotací. Na poslední ukázce vyvažování AVL stromu je kritérium vyváženosti vrcholu 5 rovno dvěma, a proto je realizovaná dvojitá rotace RL okolo uzlu 5.

Ukázka RL-rotace stromu

Ukázka LR-rotace stromu

[editovat] Rušení uzlů z AVL stromu

Rušení uzlů se vykonává stejně jako u binárního vyhledávacího uzlu s tím, že pokud dojde k porušení vyváženosti, provede se znovuvyvážení pomocí příslušných jednoduchých či dvojitých rotací.

[editovat] Související články

[editovat] Externí odkazy

Aplet na vyvážení binárního stromu: Věra Edelmannová, Iva Henzlová

Kategorie: Stromy (datové struktury)

AVL-strom v jiných jazycích: Dansk, Deutsch, English, Español, Suomi, Français, עברית, Magyar, Bahasa Indonesia, Italiano, 日本語, Lietuvių, Polski, Português, Русский, Slovenčina, Slovenščina, Српски / Srpski, Svenska, Tiếng Việt, 中文

Tento článek je převzat z české wikipedie - otevřené encyklopedie, originální článek naleznete na adrese: „http://cs.wikipedia.org/wiki/AVL-strom“
Stránka byla naposledy upravena v Stránka byla naposledy editována 10. 4. 2008 v 17:22.
Veškerý text je dostupný za podmínek GNU Free Documentation License (Autorské právo pro podrobnosti).