AVL stabla

U kompjuterskim naukama, AVL stablo (Georgy Adelson-Velsky i Evgenii Landis su konstruisali ovo stablo) je balansirano binarno stablo pretrage.To je bila prva takva struktura podataka koja je konstruisana.^[1] U AVL stablu, visina podstabala dvoje djece bilo kojeg čvora se može razlikovati najviše za jedan; ako se u bilo kojem trenutku ova razlika promijeni, izvršit će se rebalansiranje da bi se vratila ova osobina. Pretraživanje, umetanje i brisanje uzimaju O(log n) vremena i u prosječnom i u najgorem slučaju, gdje je n broj čvorova u početnom stablu. Umetanje i brisanje mogu zahtijevati da stablo bude rebalansirano preko jedne ili više rotacija stabla.

AVL stablo je imenovano nakon što su njegovi Sovjetski izumitelji, Georgy Adelson-Velsky i Evgenii Landis, objavili svoj rad "An algorithm for the organization of information" 1962.godine .^[2]

AVl stabla se često porede sa crveno-crnim stablima zato što oba podržavaju isti skup operacija i uzimaju O(log n) vremena za osnovne operacije. Za aplikacije koje intenzivno koriste pretraživanja, AVL stabla su brža od crveno-crvenih stabala zato što su ona čvrsto balansirana.^[3] Slično kao i crveno-crna stabla, AVL stabla su visinsko-balansirana. Oba u opštem slučaju nisu težinsko-balansirana niti μ-balansirana za bilo koje $\scriptstyle \mu \leq {\tfrac {1}{2}}$ ;^[4] što znači da čvorovi na istom nivou mogu imati ogroman broj različitih potomaka.

Operacije

Rotacije stabla

Osnovne operacije AVL stabla uključuju iste radnje kao one koje se trebaju sprovesti na neuravnoteženom binarnom stablu pretrage, ali promjene su praćene sa nula ili više operacija koje se zovu rotacije stabla, koje pomažu vratiti balansiranu visinu podstabala.

Pretraživanje

Pretraživanje po određenom ključu u AVL stablu može biti urađeno na isti način kao i kod normalnog neuravnoteženog binarnog stabla pretrage.

Obilazak AVL stabla

Nakon što je čvor pronađen u uravnoteženom stablu , sljedeći ili prethodni čvorovi mogu biti istraženi u amortiziranom stalnom vremenu. Neki slučajevi koji istražuju ove "obližnje " čvorove zahtijevaju obilaženje do log (n) veza ( posebno kada se kreće od krajnjeg desnog lista u lijevom podstablu pa do korijena ili iz korijena do krajnjeg lijevog lista desnog podstabla; npr. AVL stablo koje kreće od čvora 14 do čvora 19 traje 4 koraka ) . Međutim, istražujući sve čvorove stabla (n čvorova) na ovaj način, svaku veza će se koristiti tačno dva puta : jedan obilazak će unijeti podstablo ukorijenjeno u tom čvoru, a drugi će ostaviti podstablo tog čvora nakon što ga istraži. A budući da imamo n-1 veza u stablu , amortizirani trošak se utvrdi da je 2×(n-1)/n, ili približno 2 .

Umetanje

Nakon umetanja čvora, potrebno je provjeriti pretke svakog čvora zbog dosljednosti sa invarijantama AVL stabala: ovo se zove "vraćanje". Ovo se postiže tako što se razmatra faktor balansiranosti svakog čvora, koji je definisan kao razlika u visinama između lijevog i desnog podstabla.

Slikovni opis kako rotacije rebalansiraju čvorove AVL stabla. Brojevi predstavljaju kako su čvorovi rebalansirani. Slova predstavljaju podstabla koja su sama po sebi balansirana AVL stabla. Plavi broj pored čvora je mogući faktor balansiranja (brojevi u zagradama se pojavljuju samo u slučaju brisanja).

Faktor balansiranosti bilo kojeg čvora u AVL stablu je cijeli broj u opsegu [-1,+1]. Ovaj faktor balansiranja je smješten u čvoru, ali se možda mora ispraviti nakon umetanja ili brisanja, što se također izvrši u toku vraćanja. Zbog toga što jedno umetanje ne može promijeniti visinu AVL stabla za više od jedan, privremeni izračunati faktor balansiranja nekog čvora nakon umetanja biće u opsegu od [−2,+2]. Kada se svi čvorovi provjere, ako je ponovno izračunati faktor balansiranja ostao u opsegu od [−1,+1] rotacije nisu potrebne. Ako je ipak faktor balansiranja postao manji od -1 ili veći od +1, podstablo ukorijenjeno u tom čvoru je nebalansirano i potrebna je rotacija.

Opis rotacija

Pretpostavimo da je faktor balansiranja čvora P jednak 2 (moguća nebalansirana vrijednost je −2). Ovaj slučaj je u lijevoj koloni ilustracije sa P:=5. Onda gledamo lijevo podstablo (ono koje je više) sa čvorom N. Ako ovo podstablo nije naslonjeno desno - tj. N ima faktor balansiranosti 1 (ili, ako izbrišemo onda je 0) - možemo rotirati cijelo stablo udesno da bi dobili balansirano stablo. Ovo je imenovano kao "Left Left Case" u ilustraciji sa N:=4. Ako je ovo podstablo naslonjeno desno - tj. N:=3 ima faktor balansiranosti −1 - prvo moramo rotirati podstablo ulijevo i završiti prethodni slučaj. Ovaj drugi slučaj je imenovan kao "Left Right Case" u ilustraciji.

Ako je faktor balansiranosti čvora P jednak −2 (ovaj slučaj je u desnoj koloni ilustracije P:=3) možemo ponoviti gornji algoritam. Ako korijen N od (višeg) desnog podstabla ima faktor balansiranosti −1 (ili ako izbrišemo onda je 0) možemo rotirati cijelo drvo ulijevo i dobiti balansirano stablo. Ovo je imenovano kao "Right Right Case" u ilustraciji sa N:=4. Ako korijen N:=5 desnog podstabla ima faktor balansiranosti 1 ("Right Left Case") tada možemo rotirati stablo udesno i završiti u "Right Right Case".

Cijelo umetanje izgleda ovako:

 // N is the child of P whose height increases by 1.
 do {
   // balance_factor(P) has not yet been updated!
   if (N == left_child(P)) { // the left subtree increases
     if (balance_factor(P) == 1) { // The left column in the picture
       // ==> the temporary balance_factor(P) == 2 ==> rebalancing is required.
       if (balance_factor(N) == -1) { // Left Right Case
          rotate_left(N); // Reduce to Left Left Case
       }
       // Left Left Case
       rotate_right(P);
       break; // Leave the loop
     }
     if (balance_factor(P) == -1) {
       balance_factor(P) = 0; // N’s height increase is absorbed at P.
       break; // Leave the loop
     }
     balance_factor(P) = 1; // Height increases at P
   } else { // N == right_child(P), the child whose height increases by 1.
     if (balance_factor(P) == -1) { // The right column in the picture
       // ==> the temporary balance_factor(P) == -2 ==> rebalancing is required.
       if (balance_factor(N) == 1) { // Right Left Case
          rotate_right(N); // Reduce to Right Right Case
       }
       // Right Right Case
       rotate_left(P);
       break; // Leave the loop
     }
     if (balance_factor(P) == 1) {
       balance_factor(P) = 0; // N’s height increase is absorbed at P.
       break; // Leave the loop
     }
     balance_factor(P) = -1; // Height increases at P
   }
   N = P;
   P = parent(N);
 } while (P != null); // Possibly up to the root

Nakon rotacije podstablo ima istu visinu kao prije, pa vraćanje može stati. U cilju da se vrati faktor balansiranosti za sve čvorove, prvo primijetimo da svi čvorovi koji su na putu koji se koristio prilikom prvobitnog umetanja zahtijevaju promjenu. Ako se gornja procedura primijeni na čvorove na ovom putu, počev odozdo (tj. od umetnutog čvora), tada će svaki čvor u stablu imati opet faktor balansiranosti −1, 0, ili 1.

Vrijeme potrebno za pretraživanje je $O(log n),$ plus maksimum od $O(log n)$ vraćanja do korijena, pa cijela operacija može biti završena u $O(log n)$ vremenu.

Brisanje

Neka je čvor X čvor koji ima vrijednost koju trebamo izbrisati, i neka je čvor Y čvor koji trebamo naći da zauzme mjesto čvora X, i neka je čvor Z čvor koji trebamo izbrisati iz stabla.

Brisanje čvora sa dvoje djece iz binarnog stabla pretrage.

Koraci pri brisanju čvora u AVL stablu su sljedeći:

Ako je čvor X list ili ima samo jedno dijete, idi na korak 5 sa Z:=X.
Inače, ustanovi koji je čvor Y tražeći najveći čvor u lijevom podstablu čvora X ili najmanji čvor u njegovom desnom podstablu
Razmijeni sve veze između djece i roditelja čvora X sa onima od čvora Y. U ovom koraku, in-order sekvenca između čvorova X i Y je privremeno narušena, ali struktura stabla je nepromijenjena.
Izaberi čvor Z da bude veza između djeteta i roditelja starog čvora Y.
Ako čvor Z ima podstablo (koje je onda list) dodaj to roditelju čvora Z.
Ako je čvor Z bio korijen (onda on nema roditelja), promijeni korijen.
Izbriši čvor Z.
Vrati se putem od roditelja od Z pa do korijena, prilagođavajući faktore balansiranosti.

Jedno brisanje ne može smanjiti visinu AVL podstabla za više od 1, pa je trenutni faktor balansiranja u opsegu od -2 do +2.

Ako je faktor balansiranosti postao ±2 tada je podstablo nebalansirano i treba se rotirati. Različiti slučajevi rotacija su opisanu u dijelu "Umetanje".

Brisanje izgleda ovako:

 // N is the child of P whose height decreases by 1.
 do {
   // balance_factor(P) has not yet been updated!
   if (N == right_child(P)) { // the right subtree decreases
     if (balance_factor(P) == 1) { // The left column in the picture
       // ==> the temporary balance_factor(P) == 2 ==> rebalancing is required.
       S = left_child(P); // Sibling of N
       B = balance_factor(S);
       if (B == -1) { // Left Right Case
          rotate_left(S); // Reduce to Left Left Case
       }
       // Left Left Case
       rotate_right(P);
       if (B == 0) // (in the picture the small blue (0) at node 4)
         break; // Height does not change: Leave the loop
     }
     if (balance_factor(P) == 0) {
       balance_factor(P) = 1; // N’s height decrease is absorbed at P.
       break; // Leave the loop
     }
     balance_factor(P) = 0; // Height decreases at P
   } else { // N == left_child(P), the child whose height decreases by 1.
     if (balance_factor(P) == -1) { // The right column in the picture
       // ==> the temporary balance_factor(P) == -2 ==> rebalancing is required.
       S = right_child(P); // Sibling of N
       B = balance_factor(S);
       if (B == 1) { // Right Left Case
          rotate_right(S); // Reduce to Right Right Case
       }
       // Right Right Case
       rotate_left(P);
       if (B == 0) // (in the picture the small blue (0) at node 4)
         break; // Height does not change: Leave the loop
     }
     if (balance_factor(P) == 0) {
       balance_factor(P) = -1; // N’s height decrease is absorbed at P.
       break; // Leave the loop
     }
     balance_factor(P) = 0; // Height decreases at P
   }
   N = P;
   P = parent(N);
 } while (P != null); // Possibly up to the root

Vraćanje može stati ako je faktor balansiranosti postao ±1 i pokazuje na to da je visina podstabla ostala nepromijenjena.Ovo također može rezultirati iz rotacije kada više dijete ima faktor balansiranosti 0.

Ako je faktor balansiranosti postao 0 onda se visina podstabla smanjila za 1 i vraćanje treba da se nastavi. Ovo također može proizaći iz rotacije.

Vrijeme potrebno za pretraživanje je $O(log n)$ , plus maksimum od $O(log n)$ vraćanja do korijena, pa cijela operacija može biti završena u $O(log n) vremenu.$

Usporedba sa ostalim strukturama

I AVL stabla i crveno-crna stabla su samobalansirajuća binarna stabla pretrage i ona su matematički veoma slična.^[5] Operacija za balansiranje stabala su različite, ali se obje izvršavaju u prosječnom vremenu od O(1) sa maksimumom od O(log n). Prava razlika između njih je u visinama.

Reference

^ Robert Sedgewick, Algorithms, Addison-Wesley, 1983, ISBN 0-201-06672-6, stranica 199, poglavlje15: Balanced Trees.
^ Georgy Adelson-Velsky, G.; Evgenii Landis (1962).
^ Pfaff, Ben (June 2004).
^ AVL trees are not weight-balanced? (meaning: AVL trees are not μ-balanced?
^ In fact, each AVL tree can be colored red-black.

[1] Robert Sedgewick, Algorithms, Addison-Wesley, 1983, ISBN 0-201-06672-6, stranica 199, poglavlje15: Balanced Trees.

[2] Georgy Adelson-Velsky, G.; Evgenii Landis (1962).

[3] Pfaff, Ben (June 2004).

[4] AVL trees are not weight-balanced? (meaning: AVL trees are not μ-balanced?

[5] In fact, each AVL tree can be colored red-black.

[1]

[2]

[3]

[4]

[5]