Objašnjeni faktor umetanja, rotacije i ravnoteže AVL stabla

Što je AVL stablo?

AVL stablo je podvrsta binarnog stabla pretraživanja. Nazvana po izumiteljima Adelsonu, Velskom i Landisu, AVL stabla imaju svojstvo dinamičkog samobalansiranja uz sva svojstva koja pokazuju binarna stabla pretraživanja.

BST je struktura podataka sastavljena od čvorova. Ima sljedeća jamstva:

  1. Svako stablo ima korijenski čvor (na vrhu).
  2. Korijenski čvor ima nula, jedan ili dva podređena čvora.
  3. Svaki podređeni čvor ima nula, jedan ili dva podređena čvora i tako dalje.
  4. Svaki čvor ima do dvoje djece.
  5. Za svaki čvor njegovi su lijevi potomci manji od trenutnog čvora, što je manje od desnih potomaka.

AVL stabla imaju dodatno jamstvo:

  1. Razlika između dubine desnog i lijevog podstabla ne može biti veća od jedne. Da bi se zadržalo ovo jamstvo, implementacija AVL-a uključivat će algoritam za ponovno uravnoteženje stabla kada bi dodavanje dodatnog elementa poremetilo ovo jamstvo.

AVL stabla imaju najgori slučaj pretraživanja, umetanja i brisanja vremena O (log n).

Desna rotacija

Desna rotacija stabla AVL

Lijeva rotacija

Lijeva rotacija stabla AVL

Postupak umetanja AVL-a

Izvršit ćete umetanje slično uobičajenom umetanju binarnog stabla pretraživanja. Nakon umetanja popravljate svojstvo AVL pomoću rotacije lijevo ili desno.

  • Ako postoji neravnoteža u lijevom djetetu desnog podstabla, tada izvršavate rotaciju lijevo-desno.
  • Ako postoji neravnoteža u lijevom djetetu lijevog podstabla, tada izvršavate desnu rotaciju.
  • Ako postoji neravnoteža u desnom djetetu desnog podstabla, tada izvršavate lijevu rotaciju.
  • Ako postoji neravnoteža u desnom djetetu lijevog podstabla, tada izvršavate rotaciju desno-lijevo.

AVL stablo je samobalansirajuće binarno stablo pretraživanja. AVL stablo je binarno stablo pretraživanja koje ima sljedeća svojstva: -> Podstabla svakog čvora razlikuju se po visini za najviše jedno. -> Svako je podstablo AVL stablo.

AVL stablo provjerava visinu lijevog i desnog podstabla i osigurava da razlika nije veća od 1. Ova razlika naziva se faktor ravnoteže. Visina AVL stabla uvijek je O (Logn) gdje je n broj čvorova u stablu.

AVL rotacije stabla

U AVL stablu, nakon izvođenja svake operacije poput umetanja i brisanja moramo provjeriti faktor ravnoteže svakog čvora u stablu. Ako svaki čvor zadovoljava uvjet faktora ravnoteže, operaciju zaključujemo u suprotnom, moramo je uravnotežiti. Koristimo operacije rotacije kako bismo stablo uravnotežili kad god stablo postaje neuravnoteženo zbog bilo koje operacije.

Operacije rotacije koriste se za uravnoteženje stabla. Postoje četiri rotacije i klasificirane su u dvije vrste:

Jednostruka rotacija lijevo (LL rotacija)

U LL rotaciji svaki čvor pomiče se za jedan položaj ulijevo od trenutnog položaja.

Jedna rotacija udesno (RR rotacija)

U RR rotaciji svaki čvor pomiče jedan položaj udesno od trenutnog položaja.

Lijeva desna rotacija (LR rotacija)

LR rotacija kombinacija je jednostruke rotacije ulijevo, nakon čega slijedi jednostruka rotacija udesno. U LR rotaciji, prvo se svaki čvor pomiče za jedan položaj ulijevo, a zatim udesno od trenutnog položaja.

Desna lijeva rotacija (RL rotacija)

RL rotacija kombinacija je jednostruke desne rotacije nakon koje slijedi jednostruka rotacija lijevo. U RL rotaciji, prvo se svaki čvor pomiče za jedan položaj udesno, a zatim za jedan položaj ulijevo od trenutnog položaja.

Analiza vremena AVL stabala

AVL stablo je binarno stablo pretraživanja s dodatnim svojstvom da razlika između visine lijevog podstabla i desnog podstabla bilo kojeg čvora ne može biti veća od 1.

Algoritam Prosjek Najgori slučaj: Prostor:, O(n)Vrijeme:O(n)

Primjena AVL stabala

AVL stabla su korisna u slučajevima kada dizajnirate neku bazu podataka u kojoj umetanja i brisanja nisu tako česta, ali morate često tražiti stavke prisutne tamo.