Uvod u AVL stablo u strukturi podataka
Drvo AVL u strukturi podataka odnosi se na drvo Adelson, Velski i Landis. Ovo je poboljšana verzija stabla binarnog pretraživanja. Ima sve značajke kao Binarno stablo pretraživanja, ali razlikuje se samo po tome što održavaju razliku između visine lijevog poddrvenog i desnog potrednog drveta, a također uvjeravaju da je njegova vrijednost <stablo <= 1, to je poznato pod nazivom Balance Faktor.
Balance Factor = height(left-subtree) − height(right-subtree)
Na primjer: Razmotrite sljedeća stabla
U gornjem primjeru, visina desnog potkrovla = 2, a lijeva = 3, dakle BF = 2, što je <= 1, pa se kaže da je stablo uravnoteženo.
Zašto nam treba DSL stablo u DS-u?
Tijekom rada s Binarnim stablom pretraživanja nailazimo na scenarij gdje su elementi poredani. U takvim su slučajevima svi elementi matrice raspoređeni na jednoj strani korijena, što dovodi do povećanja vremenske složenosti pretraživanja elementa u nizu i složenost postaje -O (n), tj. Najgora složenost stabla, Da bi riješili takve probleme i smanjili vrijeme pretraživanja, AVL stabla izumili su Adelson, Velski i Landis.
Primjer:
Na gornjoj slici visina lijevog poddreva = 3 bila je jednaka
Visina desnog poddreva = 0
Dakle Faktor ravnoteže = 3-0 = 3. Stoga potraga za elementom u takvom stablu ima složenost O (n) koja je slična linearnom pretraživanju. Kako bi se izbjeglo to složeno pretraživanje AVL stabla uvedeno je tamo gdje svaki čvor na stablu mora održavati
faktor ravnoteže <= 1, inače se za balansiranje takvog stabla moraju provoditi različite tehnike rotacije.
Struct AVLNode
(
int data;
struct AVLNode *left, *right;
int ball factor;
);
Vrste rotacija
Kad faktor ravnoteže za stablo ne zadovolji uvjet <= 1, tada treba izvršiti rotacije na njima kako bi ga pretvorili u uravnoteženo stablo.
Postoje 4 vrste rotacije:
1. Lijeva rotacija: Ako dodavanje čvora desno od stabla neravnotežu tada, u tom slučaju treba izvršiti rotaciju ulijevo.
2. Desna rotacija: Ako dodavanje čvora lijevo od stabla uzrokuje neravnotežu čvora, tada treba obaviti Desnu rotaciju. Drugim riječima, kada se broj čvorova povećava na lijevoj strani, pojavljuje se potreba da se elementi pomaknu u desnu stranu kako bi se to uravnotežilo, pa se kaže da je to rotacija u desno.
3. Rotacija lijevo-desno: Ova vrsta rotacije je kombinacija gore navedene dvije rotacije. Ova vrsta rotacije se događa kada se jedan element doda u desno podređenje lijevog stabla.
U takvom slučaju najprije izvedite rotaciju ulijevo na podrezi, a zatim desnu rotaciju lijevog stabla.
4. Desno-lijevo okretanje: Ova vrsta rotacije također je sastavljena od niza iznad 2 rotacije. Ova je vrsta rotacije potrebna kada se doda element s lijeve strane desnog poddreva i stablo postane neuravnoteženo. U takvom slučaju prvo izvršavamo desnu rotaciju na desnoj podlozi, a zatim lijevu rotaciju na desnom stablu.
Operacije na AVL stablu u DS-u
Ispod 3 operacije koje se mogu izvesti na AVL stablu: -
1. Traži
Ova je operacija slična pretraživanju u stablu binarnog pretraživanja. Sljedeći koraci su navedeni u nastavku:
- Pročitajte element koji pruža korisnik recimo x.
- Usporedite element iz korijena, ako je isti onda izlazite u suprotnom prijeđite na sljedeći korak.
- Ako je x
Ostalo pođi pravo dijete i opet usporedi.
Slijedite procese B i C dok ne pronađete element i izađete.
Ovaj postupak ima složenost O (log n).
Primjer:
 | Razmotrite ovo stablo gdje trebamo izvršiti pretraživanje vrijednosti čvora 9. Najprije x = 9, korijenska vrijednost (12)> x, tada vrijednost mora biti u lijevom podređenju korijenskog elementa. |
 | Sada se x uspoređuje s vrijednosti čvora 3 x> 3, stoga moramo krenuti prema desnom podrezi. |
 | Sada se x uspoređuje s čvorom (9), gdje je 9 == 9 vraća istinu. Dakle, pretraživanje elemenata dovršava se u stablu. |
2. Umetanje
Prilikom umetanja elementa u AVL stablo moramo pronaći određeni element koji je potrebno umetnuti, a zatim je element pričvršćen isto kao i umetanje u BST, ali nakon toga se provjerava je li stablo još uvijek uravnoteženo ili ne tj. faktor ravnoteže čvora je <= 1. I određene rotacije se izvode prema potrebi.
Složenost je O (log n).
Primjer: Razmotrite dolje stablo,
 | Svaki čvor ima faktor ravnoteže kao 0, -1 ili 1, tako da je drvo uravnoteženo. Sada dozvoljavamo što se događa kad se ubaci čvor sa vrijednošću 1. Prolazi prvo stablo da bi pronašlo mjesto na kojem ga treba umetnuti … 1 <2 se tako piše kao lijevo dijete čvora (2). |
 | Nakon umetanja, čvor (9) postaje neuravnotežen s faktorom ravnoteže = 2. Sada je podvrgnut pravoj rotaciji. |
 | Stablo postaje ravnoteža nakon zakretanja desno i time je operacija umetanja uspješno završena. |
3. brisanje
Brisanje elementa u stablu AVL također uključuje pretraživanje elementa u stablu i njegovo brisanje. Operacija pretraživanja jednaka je BST-u, a nakon pronalaska elementa koji se briše element se uklanja sa stabla i elementi se prilagođavaju tako da ponovo postanu BST. Nakon provjere ovih elemenata da ima faktor ravnoteže 0, -1 ili 1, pa se provode prikladne rotacije kako bi se on uravnotežio.
Složenost ako je O (log n).
 | Razmotrite dano stablo, čiji svi imaju faktor ravnoteže 0, -1 ili 1. Sada ćemo izbrisati čvor sa vrijednošću 16. Prvo stablo preskače pronalazak čvora sa vrijednošću 16 isto kao algoritam pretraživanja. |
 | Čvor 16 bit će zamijenjen prethodnim redoslijedom ovog čvora koji je najveći element s lijevog poddrveta tj. 12 Stablo je postalo neuravnoteženo, pa je potrebno provesti rotaciju LL. |
 | Sada je svaki čvor postao uravnotežen. |
Zaključak - AVL stablo u strukturi podataka
AVL stablo potomak je Binarnog stabla za pretraživanje, ali prevazilazi nedostatak povećane složenosti u slučaju da su elementi sortirani. Ona nadgleda faktor ravnoteže na stablu 0 ili 1 ili -1. U slučaju da stablo postane neuravnoteženo, za balansiranje stabla provode se odgovarajuće tehnike rotacije.
Preporučeni članci
Ovo je vodič za AVL stablo u strukturi podataka. Ovdje ćemo razgovarati o uvodu, operacijama na AVL stablu u DS-u i vrstama rotacija. Možete i proći kroz naše druge povezane članke da biste saznali više -
- jQuery elementi
- Što je znanost o podacima
- Vrste stabala u strukturi podataka
- Vrste podataka C #