Verze z 10. 2. 2009, 01:08 editovat Why Not A Duck (diskuse \| příspěvky) 3 editace +svg ← Přejít na předchozí porovnání		Verze z 3. 5. 2009, 22:36 editovat zrušit editaci Lukax (diskuse \| příspěvky) 1 164 editací Napravení nepřesnosti. Přejít na další porovnání →
Řá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í červeno-černých stromů musí vyvažovací algoritmy uvažovat sedm různých tvarů: Řádek 8: [[File:AA_Tree_Shape_Cases.svg]] Podobným způsobem k zjednodušení úlohy přistupují tzv. [[left-leaning červeno-černé stromy]], které zakazují červené pravé potomky určitého vrcholu s tou výjimkou, kdy je červený zároveň i levý potomek toho vrcholu. Tak vzniká struktura izomorfní s [[2-3-4-strom]]em. Pro další úvahy 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.

AA strom: Porovnání verzí