Wikipedie

AA strom: Porovnání verzí

Interaktivně procházet historii
← Přejít na předchozí porovnáníPřejít na další porovnání →
Smazaný obsah Přidaný obsah
VizuálníWikitext
Bez shrnutí editace
Bez shrnutí editace
Řádek 1:
'''AA strom''' ('''Arne Andersson strom''') je [[červeno-černý strom]] s jedním přídavným pravidlem. Na rozdíl od červeno-černého stromu mohou být červené uzly přidávány pouze do pravého potomka, což znamená, že žádný červený uzel nemůže být levý potomek. Takto získáme strom [[izomorfismus|izomorfní]] s [[B-strom|B-stromem]] třetí úrovně ([[2-3 strom]]) místo [[B-strom|B-stromu]] čtvrté úrovně ([[2-3-4 strom]]) jako [[červeno-černý strom]] a značně se tak usnadní implementace stromových operací. Pro správné vyvážení červeno-černého stromu musí vyvažovací algoritmy uvažovat sedm různých tvarů
 
* * * * * * *
== Princip ==
\ / / \ \ / / \
Základní princip všech vyvážených stromů spočívá v tom, že žádná cesta není výrazně kratší než nejdelší cesta stromu. Tuto vlastnost zajišťujeme v binárních stromech několika způsoby. Například můžeme v každém uzlu uchovávat informaci o vyvážení, třeba rozdíl ve výšce mezi pravým a levým podstromem. Dalším častým principem je použití některých uzlů jako pseudo-uzly, které nám umožní využívat binární strom jako n-ární strom. Pseudo-uzel je pomyslné spojení několika regulárních uzlů do jednoho. Takto získaný pseudo-uzel může nabývat arity více než dva a tvoří vrchol n-árního podstromu. Na tomto principu jsou postaveny i červeno-černé stromy. V notaci červeno-černých stromů se používá černá barva uzlů pro zachycení vertikálních spojení a červená horizontálních.<br/>
* * * * * * * *
/ \ / \
* * * *
 
U AA stromů stačí vzít v potaz pouze dva případy, díky omezení že pouze pravé hrany, mohou být červené.
 
* *
\ \
* *
\
*
 
Pro další úvahy (které jsou rovněž tradičním způsobem implementace AA stromu), budeme předpokládat, že v každém uzlu je uložena proměnná "úroveň", uchovávající počet levých hran, které musíme sledovat než narazíme na nulový ukazatel. To znamená, že listy budou mít úroveň jedna.
 
Původní strom
Uvažujme následující binární strom, který je AA stromem.
 
4
/ \
2 10
Řádek 15 ⟶ 28:
/ \
7 9
Spojením uzlu 4 a 10 a také 6 a 8 do jednoho pseudo-uzlu získáme následující ternální strom:
 
 
(4-------------10)
a strom, ve kterém jsou zaznamenány úrovně:
/ | \
 
2 (6---8) 12
/ \ / | \ / \
1 3 5 7 9 11 13
Abychom mohli s tímto stromem pracovat jako s binárním a přesto uchovali informace o uzlech myšlenkově spojeným do pseudo-uzlů, zavedeme značení. Do každého uzlu zaznamenáme 'úroveň', která označuje počet levých hran, které musíme projít, než narazíme na konec stromu. Listy tedy budou mít úroveň jedna. Uzly, které jsou součástí stejného pseudo-uzlu mají stejnou úroveň.
4,3
/ \
2,2 10,3
/ \ / \
1,1 3,1 6,2 12,2
/ / \ / \
5,1 8,2 11,1 13,1
/ \
7,1 9,1
Takto by vypadal strom zakreslený v notaci červeno-černých stromů.
 
B(4)
Z označení je vidět, že uzly 4 a 10 mají stejnou úroveň, jsou přímo spojeny a tvoří tak pseudo-uzel. Ovšem mezi uzly 6 a 12 není přímé spojení i přestože mají stejnou úroveň a netvoří tedy pseudo-uzel.
/ \
A to je důležitá vlastnost AA stromu - neumožňuje horizontální přímé spojení mezi levými uzly se stejnou úrovní.
B(2) R(10)
/ \ / \
B(1) R(3) B(6) B(12)
/ \ / \
B(5) R(8) B(11) R(13)
/ \
B(7) B(9)
 
Pravidla pro AA stromy, tedy jsou:
#každá větev obsahuje stejný počet pseudo-uzlů
#levý potomek nemůže mít stejnou úroveň jako jako jeho rodič
#nejsou povoleni dva praví potomci se stejnou úrovní jako rodič
#horizontální levé spojení není povoleno
#nejsou povolena souvislá horizontální spojení
 
Pro AA strom platí následující pravidla:
Tím se princip liší od červeno-černých stromů, které umožňují levé horizontální spojení. Díky tomuto omezení se ovšem značně zjednoduší operace s AA stromem.
Při vyvažování červeno-stromů se musí brát v potaz několik komplikovaných případů tvaru stromu:
 
# Každý uzel s úrovní větší než jedna musí mít pravého potomka, jehož úroveň je stejná nebo menší než úroveň uzlu (levý potomek nesmí mít stejnou úroveň, jako jeho rodič)
* * * * * * *
# Když má uzel prapotomka, nesmí mít stejné úrovně. (dva pravý potomci se stejnou úrovní jako rodič nejsou dovolené)
\ / / \ \ / / \
* * * * * * * *
/ \ / \
* * * *
 
Pokud bychom chtěli tyto pravidla zapsat v terminologii červeno-černých stromů:
V případě AA stromu se těchto sedm případů redukuje na pouhé dva:
 
# červené levé hrany nejsou povoleny
* *
# dvě po sobě jdoucí červené hrany nejsou povoleny
\ \
 
* *
Díky vlastnostem AA stromu, kdy pouze pravý potomek může být červený, jsou tato pravidla ekvivalentní a budeme je v článku různě střídat.
\
 
*
Pro vyvažování AA stromu stačí dvě operace: split a skew. Skew je pravá rotace pokud, vkládání nebo mazání vytvoří levou červenou hranu. Split je podmíněná levá rotace, když vkládání nebo mazání vytvoří dvě po sobě jdoucí červené hrany.
 
Při vyvažování AA stromu se musí ověřovat, zda úrovně uzlů neporušují výše uvedená pravidla. Pro vyvažování stromů nám budou stačit dvě operace: skew a split.
void Skew (struct node *oldparent)
{
struct node *newp = oldparent->left;
if (oldparent->parent->left == oldparent) oldparent->parent->left = newp;
else oldparent->parent->right = newp;
newp->parent = oldparent->parent;
oldparent->parent = newp;
oldparent->left = newp->right;
if (oldparent->left) oldparent->left->parent = oldparent;
newp->right = oldparent;
oldparent->level = oldparent->left ? oldparent->left->level + 1 : 1;
}
int Split (struct node *oldparent)
{
struct node *newp = oldparent->right;
if (newp && newp->right && newp->right->level == oldparent->level) {
if (oldparent->parent->left == oldparent) oldparent->parent->left = newp;
else oldparent->parent->right = newp;
newp->parent = oldparent->parent;
oldparent->parent = newp;
oldparent->right = newp->left;
if (oldparent->right) oldparent->right->parent = oldparent;
newp->left = oldparent;
newp->level = oldparent->level + 1;
return 1;
}
return 0;
}
AA stromy se snadněji implementují, pokud se k označení konce stromu, použijí uzly se zarážkami, které se lépe testují, místo nulových ukazatelů. Je relativně snadné převést kód se zarážkami na kód s ukončováním pomocí nulových ukazatelů. Jediné v čem bude rozdíl je implementace operací split a skew.
 
== Vkládání ==
Po vkládání je stejně jako u ostatních binárních vyvážených stromů nutné provést vyvažování. Pokud se zvýší úroveň pravého potomka (protože nový uzel byl vložen napravo, nebo se zvýšila úroveň pravého potomka, nebo přibyl nový levý potomek s vyšší úrovní), mohou se objevit dva po sobě jdoucí červené uzly, které musí být ošetřeny operací split (ta může způsobit zvýšení úrovně nového rodiče).
 
Pokud se zvýší úroveň uzlu, je potřeba vykonat operaci skew. Může se stát, že předchozí rodič uzlu (nyní potomek) a nebo jeho předchozí potomek (nyní prapotomek) jsou červení. Tím pádem jsme opět v situace, kdy musíme provést split.
 
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ň 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 zvýší úroveň uzlu 1 o 1.
 
0,1 1,2
\ / \
1,1 -> 0,1 2,1
\
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
/ \ / \
0,1 2,1 0,1 3,2
\ -> / \
3,1 2,1 4,1
\
4,1
 
Přidání 5 projde hladce, 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ň o 5 a dojde k porušení druhého pravidla uzly 1, 2 a 5:
 
 
1,2 1,2
/ \ / \
0,1 3,2 0,1 3,2
/ \ / \
2,1 4,1 -> 2,1 5,2
\ / \
5,1 4,1 6,1
\
6,1
 
Pro vyvážení stromu musíme provést split na uzlu 1.
 
1,2 3,3
/ \ / \
0,1 3,2 1,2 5,2
/ \ -> / \ / \
2,1 5,2 0,1 2,1 4,1 6,1
/ \
4,1 6,1
 
Tento příklad je umělý, uzly jsme přidávali v vzestupném pořadí a nebylo potřeba využít operace skew. V dalším příkladu budeme vkládat uzly sestupně.
Nejdříve do prázdného stromu přidáme 6, nic se nastane, vloží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
/ \ -> \ -> / \
4,1 6,1 5,1 4,1 6,1
\
6,1
Dále vložíme 3 provedeme vyvážení pomocí skew.
 
5,2 5,2
/ \ -> / \
4,1 6,1 3,1 6,1
/ \
3,1 4,1
 
Po vložení 2 musíme použít skew i split.
 
5,2 5,2 5,2
/ \ / \ / \
3,1 6,1 -> 2,1 6,1 -> 3,2 6,1
/ \ \ / \
2,1 4,1 3,1 2,1 4,1
\
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
/ \ / \
3,2 6,1 -> 2,1 5,2
/ \ / \
2,1 4,1 4,1 6,1
 
 
Na vyvážení stromu po vkládání může použít následující funkci:
 
void RebalanceAfterLeafAdd (struct node *n)
{ // n is a node that has just been inserted and is now a leaf node.
n->level = 1;
n->left = NULL;
n->right = NULL;
for (n = n->parent; n != &root; n = n->parent) {
if (n->level != (n->left ? n->left->level + 1 : 1)) {
Skew (n);
if (!n->right || n->level != n->right->level) n = n->parent;
}
if (!Split (n->parent)) break;
}
}
 
== Odstranění ==
Odstranění uzlu v AA stromu není složitější než vkládání a je postavené na jednoduchém principu. Pokud odstraňovaný uzel není list, najdeme takový list, který je v pořadí těsně před nebo za odstraňovaným uzlem. Vlastnosti AA stromu nám zaručují, že takový list skutečně existuje. Následně tyto dva uzly vyměníme a odstraníme list. U rodiče levého potomka musíme snížit úroveň a u pravého potomka se musíme ujistit, zda dva po sobě jdoucí uzly nejsou červené.
 
Algoritmus odstranění si předvedeme na následujícím vyváženém stromu.
 
3,3
/ \
1,2 5,2
/ \ / \
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
/ \
1,1 5,2
\ / \
2,1 4,1 6,1
 
Následně odstraníme 3.
 
2,2
/ \
1,1 5,2
/ \
4,1 6,1
 
 
3 je nahrazena svým inorder 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 úroveň u listu 2 a 5 musí být snížena.
 
2,2 2,1
\ \
5,2 -> 5,1
/ \ / \
4,1 6,1 4,1 6,1
 
Pro vyvážení musíme nyní použít skew a následovaný split.
 
2,1 2,1 4,2
\ \ / \
5,1 -> 4,1 -> 2,1 5,1
/ \ \ \
4,1 6,1 5,1 6,1
\
6,1
 
Kompletní algoritmus odstranění v jazyce C vypadá následovně:
 
void Remove (struct node *n)
Skew odstraní levé horizontální spojení otočením doprava podél rodiče. Po provedení skew není potřeba měnit úrovně prvků, neboť tato operace jednoduše změní levé horizontální spojení na pravé horizontální spojení.
{
struct node *leaf = n, *tmp;
if (n->left) {
for (leaf = n->left; leaf->right; leaf = leaf->right) {}
}
else if (n->right) leaf = n->right;
tmp = leaf->parent == n ? leaf : leaf->parent;
if (leaf->parent->left == leaf) leaf->parent->left = NULL;
else leaf->parent->right = NULL;
if (n != leaf) {
if (n->parent->left == n) n->parent->left = leaf;
else n->parent->right = leaf;
leaf->parent = n->parent;
if (n->left) n->left->parent = leaf;
leaf->left = n->left;
if (n->right) n->right->parent = leaf;
leaf->right = n->right;
leaf->level = n->level;
}
for (; tmp != &root; tmp = tmp->parent) {
if (tmp->level > (tmp->left ? tmp->left->level + 1 : 1)) {
tmp->level--;
if (Split (tmp)) {
if (Split (tmp)) Skew (tmp->parent->parent);
break;
}
}
else if (tmp->level <= (tmp->right ? tmp->right->level + 1 : 1)) break;
else {
Skew (tmp);
if (tmp->level > tmp->parent->level) {
Skew (tmp);
Split (tmp->parent->parent);
break;
}
tmp = tmp->parent;
}
}
}
 
== Výkon ==
d,2 b,2
Výkon AA stromu je ekvivalentní s výkonem červeno-černého stromu. Přestože AA provádí více rotací, jednodušší algoritmy bývají rychlejší a vyrovnají tak ztrátu výkonu.
/ \ / \
Červeno-černý strom podává vyrovnanější výsledky, ale AA strom je často ploší, což znamená rychlejší hledání.
b,2 e,1 --> a,1 d,2
/ \ / \
a,1 c,1 c,1 e,1
Bohužel skew může vytvořit dvě následující pravá horizontální spojení. Split odstraní souvislé horizontální spojení otočením doleva a zvýšením úrovně rodičů.
 
== ReferenceSouvisející články ==
* [[červeno-černý str]]
[http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_andersson.aspx Eternally Confuzzled - Andersson Tree Tutorial]
* [[B-strom]]
* [[AVL strom]]
 
==Reference==
{{Překlad|en|en:AA tree}}
*[http://www.rational.co.za/aatree.c Complete sourcecode for the above]
*[http://user.it.uu.se/~arnea/abs/simp.html A. Andersson. Balanced search trees made simple]
*[http://user.it.uu.se/~arnea/abs/searchproc.html A. Andersson. A note on searching in a binary search tree]
 
[[Kategorie:Stromy (datové struktury)]]
Citováno z „https://cs.wikipedia.org/wiki/AA_strom“