AA drevo je uravnoteženo dvojiško drevo, imenuje se po njegovem izumitelju Arne Anderssonu.

Uravnoteženost je lastnost iskalnih dvojiških dreves, ki poskrbi za to, da je višina drevesa majhna v primerjavi s količino podatkov v njih. Taka struktura drevesa poskrbi, da so podatki v drevesu razvrščeni čim bolj optimalno in s tem primerni za spremenljive urejene sezname in tudi druge oblike višjih podatkovnih struktur kot so asociativna polja in ostali.

AA drevo ima to prednost pred ostalimi iskalnimi dvojiškimi drevesi, da zaradi posebnih lastnosti, ki so naštete spodaj, močno poenostavi operacije, ki jih potrebujemo, da drevo ohranimo v ravnotežju. V nasprotju z rdeče-črnim drevesom imamo pri AA drevesu samo dve možni obliki, ki jih moramo upoštevati pri uravnoteževanju drevesa. Rdeče-črno drevo pozna sedem takih oblik.

Glavna prednost AA drevesa pred ostalimi je torej enostavnost in hitrost izvajanja algoritmov pri vstavljanju in brisanju vozlišč. AA drevo se uporablja za shranjevanje in hitro iskanje urejenih podatkov. Je posebna vrsta iskalnega dvojiškega drevesa z dodatnimi lastnostmi. Pri tem je pomembno povedati, da stopnja vozlišča v primeru AA drevesa ni stopnja vozlišča, kot je definirana pri ostalih drevesih, temveč je stopnja dodatna lastnost vozlišč. Stopnja v primeru AA drevesa je definirana v nadaljevanju.

Slika 1

Slika v rumenem krogcu prikazuje vozlišče z indeksom 14. Število 1, ki je zapisano v rdečem kvadratu je stopnja vozlišča.

Lastnosti AA drevesa:

1. Stopnja lista je vedno enaka ena.
2. Stopnja levega otroka je vedno strogo manjša od njegovega očeta.
3. Stopnja desnega otroka je manjša ali enaka stopnji njegovega očeta.
4. Stopnja desnega vnuka je vedno strogo manjša od dedka.
5. Vsako vozlišče s stopnjo več od ena mora imeti dva otroka.

Povezavi, kjer je stopnja otroka enaka desni stopnji otroka, rečemo horizontalna povezava. Dve zaporedni horizontalni povezavi sta vedno prepovedani(zaradi 4. točke).

Da drevo, pri dodajanju ali brisanju elementov, ohranimo v ravnotežju, potrebujemo dve operaciji in sicer sta to leva in desna rotacija.

Slike 2, 3 in 4 prikazujejo primere AA drevesa.

Slika 2

Slika 3

Slika 4

Slika 5: Za primer vzemimo iskalno dvojiško drevo, ki ni AA drevo. Na sliki je vidno iskalno dvojiško drevo, ki ima pri vozliščih 47, 43, 36 dve zaporedni horizontalni povezavi. To je primer iskalnega dvojiškega drevesa, ki ne ustreza definiciji AA drevesa. V tem primeru bi morali drevo spremeniti, da bi zadostilo lastnostim AA drevesa.

Slika 5

LEVA ROTACIJA je potrebna, ko pri dodajanju ali brisanju vozlišč nastaneta dve horizontalni desni povezavi(kateri sta prepovedani).

Za primer zgradimo enostavno AA drevo tako, da v drevo najprej vstavimo vozlišče z indeksom 1 (Slika 6). To vozlišče ima po definiciji stopnjo 1, ker je list drevesa. Nadaljujemo z vstavljanjem vozlišča z indeksom 2 (Slika 7). Vozlišče postavimo desno spodaj pod vozlišče z indeksom 1. Zopet ima novo vozlišče stopnjo 1.

Slika 6

Slika 7

Zatem vstavimo vozlišče z indeksom 3 (Slika 8). Vozlišče postavimo skrajno desno podaj pod vozlišče z indeksom 2. Vozlišče dobi stopnjo 1, ker je list. Če sedaj pogledamo drevo opazimo, da obstajata dve desni zaporedni horizontalni povezavi. Po definiciji to ne ustreza AA drevesu, zato uporabimo v tem primeru levo rotacijo.

Postopek leve rotacije je naslednji: sredinskemu vozlišču v tem primeru stopnjo povišamo za ena, trenutnega starša pa postavimo na mesto njegovega otroka. Tako dobimo rešitev, ki je vidna na sliki 9.

Na sliki 9 vidimo AA drevo zaradi naslednjih lastnosti:

1. Stopnje listov so 1.
2. Stopnja vozlišča 1 je manjša od stopnje očeta (vozlišče 1 je levi otrok vozlišča 2).
3. Stopnja vozlišča 3 je manjša od stopnje očeta (vozlišče 3 je desni otrok vozlišča 2).
4. Desni vnuk v tem drevesu ne obstaja.

5. Vozlišče 2 ima dva otroka in stopnjo 2.

   Slika 8

   Slika 9

DESNA ROTACIJA je potrebna, ko pri dodajanju ali brisanju vozlišč nastane leva horizontalna povezava(katera je prepovedana).

Vzemimo za primer AA drevo, ki smo ga narisali pri prejšnjem primeru (Slika 10) in vstavimo vozlišče z indeksom 0 (Slika 11 ). Vozlišče postavimo levo spodaj pod vozlišče z indeksom 1. Vozlišče dobi stopnjo 1. Opazimo, da pri vozlišču z indeksom 1 obstaja leva horizontalna povezava, kar je po definiciji prepovedano. Zato opravimo desno rotacijo.

Slika 10

Slika 11

Postopek desne rotacije je naslednji: vozlišču z indeksom 1 levega otroka (tj. vozlišče z indeksom 0) prestavimo na mesto vozlišča z indeksom 1. Vozlišče z indeksom 1 pa postavimo na mesto desnega otroka vozlišča z indeksom 0 (Slika 12).

Na sliki 12 vidimo AA drevo zaradi naslednjih lastnosti:

1. Stopnje listov so 1.
2. Stopnja vozlišča 0 je manjša od stopnje očeta (vozlišče 0 je levi otrok vozlišča 2).
3. Stopnja vozlišča 3 je manjša od stopnje očeta (vozlišče 3 je desni otrok vozlišča 2).
4. Desni vnuk v tem drevesu ne obstaja.
5. Vozlišče 2 ima dva otroka in stopnjo 2.

Slika 12

Vstavljanje vozlišč: 46, 23, 52, 87, 65, 29, 61, 50, 30, 48, 94, 58 in 78.

Najprej vstavimo vozlišče z indeksom 46 (Slika 13), vozlišče dobi stopnjo 1.

Nato vstavimo vozlišče z indeksom 23, najprej pogledamo ali je vozlišče, ki ga želimo vstaviti večje ali manjše od korena. Ugotovimo, da je vozlišče z indeksom 23 manjše od vozlišča z indeksom 46, torej ga vstavimo levo spodaj pod vozlišče z indeksom 46 (Slika 14). Vozlišče z indeksom 23 dobi stopnjo 1. Ker mora biti stopnja levega otroka vedno strogo manjša od njegovega očeta, je potrebno izvesti desno rotacijo.

Torej vozlišče z indeksom 23 postane koren s stopnjo 1, vozlišče z indeksom 46 pa postane desni otrok vozlišča 23. Tudi vozlišče 46 ima stopnjo 1 (Slika 15).

Slika13

Slika 14

Slika 15

Sedaj, vstavimo vozlišče z indeksom 52.

Najprej pogledamo ali je vozlišče z indeksom 52 večje ali manjše od korena. Ugotovimo, da je večje od korena, torej pot nadaljujemo v desno poddrevo. Pridemo do vozlišča z indeksom 46, katero je manjše od vozlišča z indeksom 52. Torej vozlišče z indeksom 52 vstavimo desno pod vozlišče z indeksom 46, vozlišče dobi stopnjo 1 (Slika 16).

Ustavimo se pri vozlišču 52 in preverimo lastnosti AA drevesa. Ugotovimo, da so pri vozlišču 52 vse lastnosti AA drevesa izpolnjene, zato nadaljujemo pot proti korenu. Naslednje vozlišče na tej poti je 46. Zopet preverimo, če so pri tem vozlišču izpolnjeni vse lastnosti za AA drevo. Vozlišče ima desnega otroka, ki ima stopnjo 1. Tudi samo vozlišče 46 ima stopnjo 1, vendar v tem primeru drevo ne krši lastnosti AA drevesa (posebej 3. točko). Ker tudi nima levega otroka, ima lahko to vozlišče stopnjo 1 brez da bi kršilo lastnosti AA drevesa (točka 5). Ugotovili smo, da drevo od vozlišča 46 naprej ne krši lastnosti AA drevesa in je zato to poddrevo AA drevo. Nadaljujemo pot proti korenu. Preveriti moramo še lastnosti AA drevesa na vozlišču 23. Tu pa ugotovimo, da drevo ne ustreza vsaj točki 3, zato ga moramo preoblikovati, da bo ustrezalo pogojem AA drevesa - uporabimo levo rotacijo .

Slika 16

Vozlišče z indeksom 46 postavimo za koren in dobi stopnjo 2.

Vozlišče z indeksom 23, kar je manjše od trenutnega korena postavimo za levega otroka, vozlišče z indeksom 52, kar je večje od trenutnega korena pa postavimo za desnega otroka (Slika 17).

Vstavimo vozlišče z indeksom 87. Vozlišče je večje od trenutnega korena, torej pot nadaljujemo v desnem poddrevesu. Vozlišče z indeksom 87 je večje od vozlišča z indeksom 52, torej vozlišče postavimo za desnega otroka vozlišča z indeksom 52 (Slika 18).

Preverimo vse lastnosti AA drevesa, ker ugotovimo, da je vse v redu nadaljujemo z vstavljanjem dokler ne pridemo do zadnjega od naštetih vozlišč. Tako pridemo do AA drevesa, ki ga prikazuje slika 19.

Slika 17

Slika 18

Slika 19

Brisanje vozlišč

Poglejmo si kako iz AA drevesa izbrišemo vozlišče. Vzemimo drevo, ki smo ga dobili pri prejšnjem primeru(Slika 19).

Iz drevesa bomo izbrisali vozlišče z indeksom 46. Vedno, ko želimo vozlišče izbrisati, ga moramo najprej poiskati. Preverimo, ali je vozlišče z indeksom 46 večje ali manjše od korena, ki je na sliki označen z rdečim kvadratom(Slika 20). Ker je 46 manjše od 52, pot nadaljujemo v levo poddrevo(Slika 21).

Zopet preverimo, ali je iskano vozlišče večje ali enako od korena levega poddrevesa. Koren levega poddrevesa oziroma vozlišče z indeksom 29, je na sliki označen z rdečim kvadratom. Ker je 46 večje od 29, pot nadaljujemo desno od korena. Tako, pridemo do iskanega vozlišča z indeksom 46(Slika 22).

Slika 19	Slika 20
Slika 21	Slika 22

Od vozlišča z indeksom 46 poiščemo vozlišče, ki je v desnem poddrevesu najbolj levo. V našem primeru je to vozlišče z indeksom 48, ki je na sliki označeno z rdečim kvadratkom (Slika 23).

Vozlišče z indeksom 48 nadomesti zeleno obarvan krogec vozlišča z indeksom 46. Pri tem obdrži njegovo stopnjo(Slika 24). Slika 25 prikazuje AA drevo, potem ko iz njega izbrišemo vozlišče z indeksom 46.

Sedaj, pa moramo preveriti ali je to drevo, ki smo ga dobili, res AA drevo. Začnemo pri vozlišču 48. Drevo na tem mestu ustreza vsem 5 lastnostim AA drevesa, zato nadaljujemo pot proti korenu. Naslednje na vrsti je vozlišče 29.

Zopet preverimo, če pri tem vozlišču poddrevo ustreza vsem 5 lastnostim AA drevesa. Ker je to res, gremo do korena. Tudi tu ugotovimo, da so na mestu tega vozlišča izpolnjene vse lastnosti AA drevesa. Torej, smo prepričani, da slika 25 prikazuje AA drevo.

Slika 23

Slika 24

Slika 25

Filmček, ko iz AA drevesa izbrišemo vozlišče z indeksom 52.

Filmček, kjer nastopa dvajset vozlišč, na kocu pa izbrišemo vozlišče z indeksom 30.

Kaj velja za stopnjo lista v AA drevesu?

Kdaj je potrebna leva rotacija?

Kdaj je potrebna desna rotacija?

• AA Tree: http://en.wikipedia.org/wiki/AA_tree (dostopno 13.3.2011)
• Binary search trees: http://people.ksp.sk/~kuko/bak/index.html (dostopno 13.3.2011)
• Balanced search trees made simple, Andre Andersson: http://user.it.uu.se/~arnea/ps/simp.pdf (dostopno 13.3.2011)
• Lie Hetland, Mangus. Python Algorithms: Mastering Basic Algorithms in the Python Language, 2010. Springer Science+Business Media, New York