AA strom: Porovnání verzí
Smazaný obsah Přidaný obsah
mBez shrnutí editace |
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í červeno-černých stromů
* * * * * * *
Řádek 58:
Pro AA strom platí následující pravidla:
# Levý potomek nesmí mít stejnou úroveň
# Nejsou povoleny dva praví potomci se stejnou úrovní jako rodič
Řádek 66:
# 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 zmíměné zápisy pravidel ekvivalentní a budeme je v článku různě střídat.
== Split a skew ==
| |||