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 26:
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 takhran, žekteré listymusíme označímeprojít, číslicínež 1narazíme ana postupujemekonec kstromu. Listy tedy budou mít úroveň vrcholujedna. 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
 
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í.
 
Pravidla pro AA stromy, tedy jsou:
Řádek 77:
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čů.
 
 
 
{{Překlad|en|en:AA tree}}
Citováno z „https://cs.wikipedia.org/wiki/AA_strom“