AA strom: Porovnání verzí
Smazaný obsah Přidaný obsah
m novy odkaz značky: možný spam editace z Vizuálního editoru |
značka: editor wikitextu 2017 |
||
Řádek 14:
Původní strom:
4
/ \
Řádek 24:
/ \
7 9
strom, ve kterém jsou uloženy úrovně:
4,3
/ \
Řádek 36:
/ \
7,1 9,1
a strom zaznamenaný v notaci červeno-černých stromů (B – černá, R – červená): {{Přesnost|část|celkem dobrej vtip}}
B(4)
/ \
Řádek 48:
/ \
B(7) B(9)
Pro AA strom platí následující pravidla:
Řádek 60:
# Dvě po sobě jdoucí červené hrany nejsou povoleny
Díky vlastnostem AA stromu, kdy může být pouze pravý potomek červený, jsou dva výše
== Split a skew ==
Řádek 112:
Jako názornou ukázku vybudujeme AA strom. Nejdříve vložíme 0 do prázdného stromu, tím neporušíme žádné pravidlo a úroveň tohoto uzlu bude 1. Následně vložíme uzel 1 a opět nejsou porušena žádná pravidla. Po vložení uzlu 2 už musíme použít operaci split, neboť je porušeno druhé pravidlo. Split provede levou rotaci a zvýší úroveň uzlu 1 o 1.
0,1 1,2
\ / \
Řádek 118:
\
2,1
Přidáním uzlu 3 se žádné pravidlo neporuší. Přidáním uzlu 4 se opět poruší druhé pravidlo tentokrát vzhledem k uzlu 2 a musíme použít operaci split:
1,2 1,2
/ \ / \
Řádek 128:
\
4,1
Přidání 5 projde bez komplikací, ale 6 znovu poruší druhé pravidlo a je potřeba využít split. Tentokrát však jeden split nebude stačit, neboť rozdělení 4, 5 a 6 způsobí, že se zvýší úroveň 5 a dojde k porušení druhého pravidla uzly 1, 2 a 5:
1,2 1,2
/ \ / \
Řádek 140:
\
6,1
Pro vyvážení stromu musíme provést split na uzlu 1.
1,2 3,3
/ \ / \
Řádek 150:
/ \
4,1 6,1
Tento příklad je umělý, uzly jsme přidávali ve vzestupném pořadí a nebylo potřeba využít operace skew. V dalším příkladu budeme vkládat uzly sestupně.
Do prázdného stromu vložíme 6, není potřeba žádného zásahu a hned přidáme 5. Tímto jsme porušili první pravidlo, neboť levý potomek nesmí mít stejnou úroveň jako jeho předek. Problém spravíme pomocí skew, která provede pravou rotaci a udělá z levé červené hrany pravou červenou:
6,1 5,1
/ → \
5,1 6,1
Po vložení 4 vznikne další červená levá hrana a znovu použijeme skew. Skew však vytvoří dvě po sobě jdoucí červené hrany, které musí být rozděleny pomocí split.
5,1 4,1 5,2
/ \ → \ → / \
Řádek 165:
\
6,1
Dále vložíme 3 provedeme vyvážení pomocí skew.
5,2 5,2
/ \ → / \
Řádek 173:
/ \
3,1 4,1
Po vložení 2 musíme použít skew i split.
5,2 5,2 5,2
/ \ / \ / \
Řádek 183:
\
4,1
Tato situace, ale porušuje první pravidlo, neboť 3 je levá hrana 5 a má stejnou úroveň. Strom znovu vyvážíme použitím operace skew.
5,2 3,2
/ \ / \
Řádek 191:
/ \ / \
2,1 4,1 4,1 6,1
Na vyvážení stromu po vkládání může použít následující proceduru:
<syntaxhighlight lang="c">
Řádek 213:
Algoritmus odstranění si předvedeme na následujícím vyváženém stromu.
3,3
/ \
Řádek 219:
/ \ / \
0,1 2,1 4,1 6,1
Po odstranění 0 musíme snížit úroveň uzlů 1 a 3 o jedna. Obejdeme se bez operací skew a split.
3,2
/ \
Řádek 227:
\ / \
2,1 4,1 6,1
Následně odstraníme 3.
2,2
/ \
Řádek 235:
/ \
4,1 6,1
3 je nahrazena svým in-order následníkem 2. V tomto případě se neporuší pravidla a není potřeba provádět vyvážení. Pokud však odstraníme 1, způsobíme nevyvážení a u listu 2 a 5 musí být snížena úroveň.
2,2 2,1
\ \
Řádek 243:
/ \ / \
4,1 6,1 4,1 6,1
Pro vyvážení musíme nyní použít skew následovaný split.
2,1 2,1 4,2
\ \ / \
Řádek 253:
\
6,1
Kompletní algoritmus odstranění v jazyce C vypadá následovně:
<syntaxhighlight lang="c">
| |||