WikiSysop: Bot: Automatska zamjena teksta (- +)

2022-01-03T02:02:31Z

Bot: Automatska zamjena teksta (- +)

←Starija inačica		Inačica od 02:02, 3. siječnja 2022.
Redak 1:		Redak 1:
	~~<!--'''AVL stablo'''-->~~''AVL-stablo'' je struktura [[podatak]]a koja se koristi u [[računarstvo\|računarstvu]]. Radi se o [[Balansiranje\|balansiranom]] [[binarno stablo\|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 notacija\|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 struktura [[podatak]]a koja se koristi u [[računarstvo\|računarstvu]]. Radi se o [[Balansiranje\|balansiranom]] [[binarno stablo\|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 notacija\|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'').		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'').

WikiSysop: Bot: Automatski unos stranica

2021-09-07T23:20:50Z

Bot: Automatski unos stranica

Nova stranica

''AVL-stablo'' je struktura [[podatak]]a koja se koristi u [[računarstvo|računarstvu]]. Radi se o [[Balansiranje|balansiranom]] [[binarno stablo|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 notacija|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 ==
[[Datoteka:Tree Rebalancing.gif|mini|640x640px|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:

# X (kritični list u kojemu je faktor balansiranja <code>>1</code> ili <code><-1</code>),
# X-ovo lijevo ('''L'''L, '''L'''R debalans) ili desno dijete ('''R'''R, '''R'''L debalans)
# Lijevo (L'''L''', R'''L''' debalans) ili desno (R'''R''', L'''R''' debalans) dijete prethodnog lista
# 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:<syntaxhighlight lang="c++">
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
};
</syntaxhighlight>Desna rotacija pozvana prilikom LL debalansa, <code>faktorBalansiranja = 2</code> (prema istoj logici je izvedena i lijeva rotacija uzrokovana RR debalansom):<syntaxhighlight lang="c++">
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;
}
</syntaxhighlight>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, <code>faktorBalansiranja = 2</code> (rotacija RL debalansa prati istu logiku):<syntaxhighlight lang="c++">
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;
}
</syntaxhighlight>
[[Kategorija:Baze podataka]]

AVL stablo - Povijest promjena

WikiSysop: Bot: Automatska zamjena teksta (- +)

WikiSysop: Bot: Automatski unos stranica