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
m styl
mBez 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 vkládá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]]), který je izomorfní s [[červeno-černý strom| červeno-černým stromem]]. Značně se tak usnadní implementace stromových operací.
 
Pro správné vyvážení klasických červeno-černých stromů musímusíme při implementaci vyvažovacívyvažovacích algoritmyalgoritmů uvažovat sedm různých tvarů:
 
* * * * * * *
Řádek 17:
*
 
Pro další úvahy, které se běžne používají při implementaci AA stromů, budeme předpokládat, že je v každém uzlu uložena proměnná ''úroveň'', uchovávající počet levých hran, které musíme sledovat, než narazíme na nulový ukazatel. Listy tedy budou mít úroveň jedna.
 
Původní strom:
Řádek 31:
7 9
 
a strom, ve kterém jsou uloženy úrovně:
 
4,3
Řádek 59:
 
# Levý potomek nesmí mít stejnou úroveň, jako jeho rodič
# DvaNejsou povoleny dva praví potomci se stejnou úrovní jako rodič nejsou povolené
 
Pokud bychom chtěli tytotato pravidla zapsat v terminologii červeno-černých stromů, zněla by následovně:
 
# Červené levé hrany nejsou povoleny
# Dvě po sobě jdoucí červené hrany nejsou povoleny
 
Díky vlastnostem AA stromu, kdy může být pouze pravý potomek červený, jsou tatovýše pravidlazmíměné zápisy pravidel ekvivalentní a budeme je v článku různě střídat.
 
== Split a skew ==
 
ProNa vyvažování AA stromu stačí pouze 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.
 
void Skew (struct node *oldparent)
Řádek 112:
 
== Vkládání ==
Po vkládání je stejně jako u ostatních binárních vyvážených stromů nutné provéstzkontrolovat vyvažovánívyvážení stromu. 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, která ovšem 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ň 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
Citováno z „https://cs.wikipedia.org/wiki/AA_strom“