AVL stablo

AVL-stablo je struktura podataka koja se koristi u računarstvu. Radi se o balansiranom binarnom stablu pretrage, koje jamči da se operacije umetanja, traženja i brisanja elemenata iz stabla i u najgorem slučaju mogu sprovesti u broju koraka koji odgovara logaritmu broja elemenata u stablu, O(log n). Motiv za korištenje binarnih stabala upravo je brza pretraga stabla, ali kod uobičajenog, nebalansiranog binarnog stabla može doći do debalansa (neka grana stabla se značajnije izduži), i onda pretraga koja ide kroz tu granu nema logaritamsku, već linearnu složenost.

AVL-stablo je dobilo ime po izumiteljima (G.M. Adelson-Velskii i E.M. Landis) koji su opisali ovu strukturu 1962. u radu Algoritam za organiziranje podataka (An algorithm for the organization of information).

Definicija AVL-stabla glasi:

AVL-stablo je binarno stablo pretrage kod kojeg apsolutna razlika visina lijevog i desnog podstabla svakog elementa nije veća od jedan.

Balansiranje i rotacije

Slika 1. Primjer rotacija

Balansiranost AVL stabla provodi se pomoću tzv. faktora balansiranja. Faktor balansiranja je razlika visine lijevog i desnog podstabla lista. Prema definiciji AVL stabla, faktor balansiranja svakog lista mora biti između -1 i 1 da bi stablo bilo u balansu. U slučaju da prilikom brisanja ili unosa listova uočimo da je on 2 ili -2 (ne može biti niži ili viši ako se ispravno balansira), moramo provesti rotaciju. Ako je faktor jednak 2, podstablo naginje na lijevo, inače naginje na desno.

Postoje četiri vrste debalansova:

• LL debalans
• RR debalans
• LR debalans

• RL debalans

Slova L (left) i R (right) označavaju u koju stranu je umetnut list stabla. Na primjer, ako je list X u LR debalansu, to znači da je novi list umetnut u desno podstablo X-ovog lijevog djeteta.

Za implementaciju rotacije potrebna su tri (četiri) lista:

1. X (kritični list u kojemu je faktor balansiranja >1 ili <-1),
2. X-ovo lijevo (LL, LR debalans) ili desno dijete (RR, RL debalans)
3. Lijevo (LL, RL debalans) ili desno (RR, LR debalans) dijete prethodnog lista
4. Roditelj kritičnog lista (prilikom rotacije X više nije na vrhu - stoga kao dijete roditelja moramo postaviti odgovarajuće dijete kritičnog lista)

Svaki debalans se rješava posebnom rotacijom: LL debalans rješava se desnom rotacijom oko kritičnog lista, RR debalans lijevom, LR dvostrukom lijevo-desnom rotacijom prvo oko srednjeg lista, a zatim kritičnog lista relevantne trojke te RL dvostrukom desno-lijevom rotacijom prateći logiku prethodne LR rotacije. Desno-lijeve i Lijevo-desne rotacije mogu se obaviti jednostavnijim postupkom vidljivim u trećem programskom isječku.

Napomena: ukoliko spremimo i ispravno podesimo djecu relevantnih listova, nije bitno da li se balans dogodio na vrhu ili drugdje u stablu zbog toga što će se ispravnim postavljanjem djece njihova podstabla ispravno postaviti u odnosu na ostale listove stabla. Na primjer, u slučaju da se list unese 10 razina ispod nekog lista X koji je postao kritičan, relevantna trojka su i dalje X, njegovo dijete i dijete njegovog djeteta, zbog toga što je X kritični list.

Implementacija u kodu (C++)

Preduvjeti:

class AVL_Stablo    // minimalističko stablo
{
private:
    struct Node
    {
    	Node* lijevo;
    	Node* desno;
    
    	long visinaLijevo;  // broj razina lijevog podstabla + 1
    	long visinaDesno;
    
    	inline long visina()
    	{
    		if (visinaLijevo > visinaDesno)
    			return visinaLijevo;
    		return visinaDesno;
    	}
    	inline int faktorBalansiranja()
    	{
    	    return visinaLijevo - visinaDesno;
    	}
    };
    Node* vrh;
    
    bool desnaRotacija(Node* A, Node* B, Node* C, Node* roditelj);
    bool lijevoDesnaRotacija(Node* A, Node* B, Node* C, Node* roditelj);
    // dodati lijevu i desno-lijevu rotaciju pomoću drugog i trećeg programskog koda
public:
    // ostatak klase
};

Desna rotacija pozvana prilikom LL debalansa, faktorBalansiranja = 2 (prema istoj logici je izvedena i lijeva rotacija uzrokovana RR debalansom):

bool AVL_Stablo::desnaRotacija(Node* A, Node* B, Node* C, Node* roditelj)
{
    /*roditelj          roditelj
      A                B
     B      postaje  C   A
    C x                 x
    
    "x" je relevantno dijete koje mijenja roditelja (iz B->desno u A->lijevo)
    netaknuto:
    A->desno
    C->lijevo
    C->desno
    
    promjene:
    B->desno postaje A
    A->lijevo postaje izvorni B->desno
    roditeljevo lijevo ili desno dijete postaje B (provjerom utvrditi je li A bio roditelj->lijevo ili roditelj->desno)
    */
	if (!A || !B || !C)		// svi moraju biti != nullptr
	{
		return false;   // neuspješna rotacija
	}
	Node* Bd = B->desno;
	B->desno = A;
	A->lijevo = Bd;

    // Ako Bd != nullptr, pozovi visinu. Inače, vrati 0
	A->visinaLijevo = (Bd ? Bd->visina() : 0) + 1;
	B->visinaDesno = A->visina() + 1;

	if (roditelj != nullptr)    // roditelj == nullptr samo kada je A ishodišni list (this->vrh)
	{
		if (A == roditelj->lijevo)
		{
			roditelj->lijevo = B;
		}
		else if (A == roditelj->desno)
		{
			roditelj->desno = B;
		}
	}
	else if (this->vrh == A)    // ishodišni list je bio u debalansu
	{
		this->vrh = B;          // postavi B kao novi ishodišni list
	}
	return true;
}

Unatoč tome što se LR i RL debalansi rješavaju tzv. "dvostrukim" rotacijama, umjesto dvostrukog rotiranja možemo odmah napraviti zamjene koje će rezultirati jednakim, ali kompaktnijim rješenjem vidljivim u sljedećem programskom kodu. Primjer dvostruke lijevo-desne rotacije nastale prilikom LR debalansa, faktorBalansiranja = 2 (rotacija RL debalansa prati istu logiku):

bool AVL_Stablo::lijevoDesnaRotacija(Node* A, Node* B, Node* C, Node* roditelj)
{
	/* roditelj             roditelj
	    A				    C
	  B			postaje   B   A
	   C                   x x
	  x x
	  
	"x" označava relevantnu djecu (podstabla)
    netaknuta djeca:
    B->lijevo
    A->desno
    
    promjene:
    C->lijevo postaje B
    C->desno postaje A
    B->desno postaje C->lijevo
    A->lijevo postaje C->desno
    roditelj->lijevo ILI roditelj->desno postaje C (ne znamo je li A bio lijevo ili desno dijete)
	*/
	
	if (!A || !B || !C)		// niti jedan list ne bi trebao biti nullptr
	{
		return false;
	}

	Node* Cl = C->lijevo;       // moramo spremiti za referencu
	Node* Cd = C->desno;
	C->lijevo = B;
	C->desno = A;
	B->desno = Cl;
	A->lijevo = Cd;

	B->visinaDesno = (Cl ? Cl->visina() : 0) + 1;
	// Za Cl i Cd nismo sigurni jesu li nullptr
	// Stoga: ako nisu - pozovi njihovu visinu, inače - vrati 0
	A->visinaLijevo = (Cd ? Cd->visina() : 0) + 1;
	C->visinaLijevo = B->visina() + 1;
	C->visinaDesno = A->visina() + 1;

	if (roditelj)   // ako nije parent nullptr, najviši list nije == this->vrh
	{
		if (A == roditelj->lijevo)  // ako je najviši list lijevo dijete njegovog roditelja
		{
			roditelj->lijevo = C;
		}
		else if (A == roditelj->desno)  // ako je najviši list desno dijete njegovog roditelja
		{
			roditelj->desno = C;
		}
	}
	else    // najviši list nema roditelja, što znači da je izvorno debalansirani list bio
	{       // this->vrh te zbog toga sada moramo postaviti novi vršni list
		this->top = C;
	}
	return true;
}