ADT Strom
AVL - stromy
 Vytisknout studijní materiál

Zadání:

1, Vytvořte AVL - strom postupným vkládáním prvků 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12.

2,   Vytvořte AVL - strom postupným vkládáním prvků: 0, 2, 1, 4, 3, 5, 6, 7, 8

3, Ze stromu vytvořeného v úkolu 1odeberte postupně prvky:12. 6, 10

Tipy pro řešení:

1, Vkládejte prvky jako do BVS, ale nezapomeňte po každém vložení zkontrolovat vyváženost stromu. Nastala-li nevyváženost v přímé větvi, použijte jednoduchou rotaci (pravou, nebo levou), nastala-li nevyváženost v zalomené větvi, použijte dvojitou rotaci (LR, nebo RL).

2, Vkládejte prvky jako do BVS, ale nezapomeňte po každém vložení zkontrolovat vyváženost stromu. Nastala-li nevyváženost v přímé větvi, použijte jednoduchou rotaci (pravou, nebo levou), nastala-li nevyváženost v zalomené větvi, použijte dvojitou rotaci (LR, nebo RL).

3,Vzpomeňte si, co platilo u BVS. Postupujte obdobným způsobem.

šipka Návrh řešení:

Nejdříve si zopakujme podstatu rotace v AVL-stromu.

Jak jednoduše vypadá pravá rotace zobrazuje obrázek BVS rotace. Představa je taková, že strom je váha, která se podle potřeby převažuje, umí rozplátat své vazby a navazovat je jinde, kde je potřeba.

Řešení příklad u číslo 1, Vypadá následovně:

Řešení příkladu č.2:

Předtím, než si zkusíme vypouštění prvku, malé opakování:

3, Odebrání z listu není problém. Jednoduše ho vymažeme a zkontrolujeme, zda není porušena vyváženost. V tomto případě není.

Odebrání čísla 6 je odebrání prvku z uzlu. Nahradíme ho třeba sym. předchůdcem (5) a tím jsme převedli případ na ten minulý. ani v tomto případě není potřeba žádné rotace, strom je po odebrání vyvážený.

Pí odebrání čísla 10 postupujeme stejně jako při odebírání č. 6. Ani zde nenastane nevyváženost. Ta by nastala až při odebrání dalšího prvku z tohoto posdstromu. Třeba prvku 9. Pak bychom museli provádět pravou rotaci. Prvek 4 by se stal kořenem.