Prije nego što saznamo o razlikama između binarnog stabla pretraživanja i AVL stabla, trebali bismo znati o binarnom stablu pretraživanja i AVL stablu zasebno.
Što je stablo binarnog pretraživanja?
The binarno stablo pretraživanja je drvo binarno stablo . Kao što znamo, to stablo može imati 'n' broj djece, dok; binarno stablo može sadržavati najviše dva djeteta. Dakle, ograničenje binarnog stabla također prati stablo binarnog pretraživanja. Svaki čvor u stablu binarnog pretraživanja trebao bi imati najviše dva djeteta; drugim riječima, možemo reći da je binarno stablo pretraživanja varijanta binarnog stabla.
Stablo binarnog pretraživanja također slijedi svojstva binarnog pretraživanja. U binarnom pretraživanju, svi elementi u nizu moraju biti poredani. Srednji element izračunavamo u binarnom pretraživanju u kojem lijevi dio srednjeg elementa sadrži vrijednost manju od srednje vrijednosti, a desni dio srednjeg elementa sadrži vrijednosti veće od srednje vrijednosti.
U stablu binarnog pretraživanja srednji element postaje korijenski čvor, desni dio postaje desno podstablo, a lijevi dio postaje lijevo podstablo. Stoga možemo reći da je binarno stablo pretraživanja kombinacija a binarno stablo i binarno pretraživanje .
Napomena: Binarno stablo pretraživanja može se definirati kao binarno stablo u kojem su svi elementi lijevog podstabla manji od korijenskog čvora, a svi elementi desnog podstabla veći od korijenskog čvora.
Vremenska složenost u stablu binarnog pretraživanja
Ako je binarno stablo pretraživanja gotovo uravnoteženo stablo tada će sve operacije imati vremensku složenost od O (prijava) jer je pretraga podijeljena na lijevo ili desno podstablo.
uključiti c programiranje
Ako je stablo binarnog pretraživanja zakošeno lijevo ili desno, tada će sve operacije imati vremensku složenost od Na) jer trebamo prijeći do n elemenata.
Što je AVL stablo?
An AVL stablo je samobalansirajuće binarno stablo pretraživanja gdje razlika između visina lijevog i desnog podstabla ne može biti veća od jedan. Ova razlika je poznata kao faktor ravnoteže. U AVL stablu, vrijednosti faktora ravnoteže mogu biti -1, 0 ili 1.
Kako se događa samobalansiranje stabla binarnog pretraživanja?
Kao što znamo da je AVL stablo samobalansirajuće binarno stablo pretraživanja. Ako stablo binarnog pretraživanja nije uravnoteženo, može se samo-uravnotežiti s nekim preuređivanjem. Ovi preraspodjeli mogu se izvesti pomoću nekih rotacija.
Razmotrimo samouravnoteženje kroz primjer.
Pretpostavimo da želimo umetnuti 10, 20, 30 u AVL stablu.
Sljedeći su načini umetanja 10, 20, 30 u AVL stablo:
Korak 1: Prvo stvaramo stablo binarnog pretraživanja, kao što je prikazano u nastavku:
Korak 2: Na gornjoj slici možemo uočiti da je stablo neuravnoteženo jer je faktor ravnoteže čvora 30 2. Kako bismo ga učinili AVL stablom, moramo izvesti neke rotacije. Ako izvedemo pravu rotaciju na čvoru 20 tada će se čvor 30 pomaknuti prema dolje, dok će se čvor 20 pomaknuti prema gore, kao što je prikazano u nastavku:
Kao što možemo primijetiti, konačno stablo slijedi svojstvo stabla binarnog pretraživanja i uravnoteženo stablo; dakle, to je AVL stablo.
U slučaju, drvo je bilo lijevo neuravnoteženo stablo, pa izvodimo desnu rotaciju na čvoru.
Korak 1: Prvo stvaramo stablo binarnog pretraživanja kao što je prikazano u nastavku:
ROM
Korak 2: Na gornjoj slici možemo vidjeti da je stablo neuravnoteženo jer je faktor ravnoteže čvora 10 -2. Kako bismo ga učinili AVL stablom, moramo izvesti neke rotacije. Radi se o desnom neuravnoteženom stablu, pa ćemo izvesti lijevu rotaciju. Ako izvedemo lijevu rotaciju na čvoru 20, tada će se čvor 20 pomaknuti prema gore, a čvor 10 prema dolje, kao što je prikazano u nastavku:
Kao što možemo primijetiti, konačno stablo slijedi svojstvo Stablo binarnog pretraživanja i a uravnoteženo drvo ; dakle, to je AVL stablo.
Korak 1: Prvo stvaramo stablo binarnog pretraživanja kao što je prikazano u nastavku:
Korak 2: Na gornjoj slici možemo uočiti da je stablo neuravnoteženo jer je faktor ravnoteže korijenskog čvora 2. Kako bismo ga učinili AVL stablom, moramo izvršiti neke rotacije. Gornji scenarij je lijevo-desno neuravnotežen jer je jedan čvor lijevo od nadređenog čvora, a drugi desno od nadređenog čvora. Prvo ćemo izvršiti lijevu rotaciju, a rotacija se događa između čvorova 10 i 20. Nakon lijeve rotacije, 20 će se pomaknuti prema gore, a 10 će se pomaknuti prema dolje kao što je prikazano u nastavku:
Ipak, stablo je neuravnoteženo, pa izvodimo pravu rotaciju na stablu. Nakon što se izvrši prava rotacija na stablu, stablo bi željelo, kao što je prikazano u nastavku:
Kao što možemo primijetiti u gornjem stablu, stablo slijedi svojstvo stabla binarnog pretraživanja i uravnoteženog stabla; dakle, to je AVL stablo.
java boolean
Korak 1: Prvo stvaramo stablo binarnog pretraživanja, kao što je prikazano u nastavku:
Korak 2: Na gornjoj slici možemo uočiti da je stablo neuravnoteženo jer je faktor ravnoteže korijenskog čvora 2. Kako bismo ga učinili AVL stablom, moramo izvesti neke rotacije. Gornji scenarij je desno-lijevo neuravnotežen jer je jedan čvor desno od svog nadređenog čvora, a drugi čvor je lijevo od svog nadređenog čvora. Prvo ćemo izvesti desnu rotaciju koja se događa između čvorova 30 i 20. Nakon desne rotacije, 20 će se pomaknuti prema gore, a 30 će se pomaknuti prema dolje kao što je prikazano u nastavku:
Ipak, gornje stablo je neuravnoteženo, pa moramo izvesti lijevu rotaciju na čvoru. Nakon što se izvrši lijeva rotacija, čvor 20 će se pomaknuti prema gore, a čvor 10 će se pomaknuti prema dolje kao što je prikazano u nastavku:
Kao što možemo primijetiti u gornjem stablu, stablo slijedi svojstvo stabla binarnog pretraživanja i uravnoteženog stabla; dakle, to je AVL stablo.
Razlike između stabla binarnog pretraživanja i AVL stabla
| Stablo binarnog pretraživanja | AVL stablo |
|---|---|
| Svako binarno stablo pretraživanja je binarno stablo jer oba stabla sadrže najviše dva djeteta. | Svako AVL stablo također je binarno stablo jer AVL stablo također ima najviše dvoje djece. |
| U BST-u ne postoji pojam, kao što je faktor ravnoteže. | U AVL stablu svaki čvor sadrži faktor ravnoteže, a vrijednost faktora ravnoteže mora biti -1, 0 ili 1. |
| Svako stablo binarnog pretraživanja nije AVL stablo jer BST može biti ili uravnoteženo ili neuravnoteženo stablo. | Svako AVL stablo je binarno stablo pretraživanja jer AVL stablo slijedi svojstvo BST-a. |
| Svaki čvor u stablu binarnog pretraživanja sastoji se od tri polja, tj. lijevog podstabla, vrijednosti čvora i desnog podstabla. | Svaki čvor u AVL stablu sastoji se od četiri polja, tj. lijevo podstablo, vrijednost čvora, desno podstablo i faktor ravnoteže. |
| U slučaju stabla binarnog pretraživanja, ako želimo umetnuti bilo koji čvor u stablo tada uspoređujemo vrijednost čvora s korijenskom vrijednošću; ako je vrijednost čvora veća od vrijednosti korijenskog čvora tada se čvor umeće u desno podstablo, inače se čvor umeće u lijevo podstablo. Nakon što je čvor umetnut, nema potrebe za provjerom faktora ravnoteže visine da bi umetanje bilo dovršeno. | U slučaju AVL stabla, prvo ćemo pronaći odgovarajuće mjesto za umetanje čvora. Nakon što je čvor umetnut, izračunat ćemo faktor ravnoteže svakog čvora. Ako je faktor ravnoteže svakog čvora zadovoljen, umetanje je dovršeno. Ako je faktor ravnoteže veći od 1, tada moramo izvršiti neke rotacije kako bismo uravnotežili stablo. |
| U stablu binarnog pretraživanja, visina ili dubina stabla je O(n) gdje je n broj čvorova u stablu binarnog pretraživanja. | U AVL stablu, visina ili dubina stabla je O(logn). |
| Jednostavan je za implementaciju jer moramo slijediti svojstva binarnog pretraživanja da bismo umetnuli čvor. | Složeno je za implementaciju jer u AVL stablu prvo moramo konstruirati AVL stablo, a zatim trebamo provjeriti visinsku ravnotežu. Ako je visina neuravnotežena, tada moramo izvesti neke rotacije kako bismo uravnotežili stablo. |
| BST nije uravnoteženo stablo jer ne slijedi koncept faktora ravnoteže. | AVL stablo je visinski uravnoteženo stablo jer slijedi koncept faktora ravnoteže. |
| Pretraživanje je neučinkovito u BST-u kada je u stablu dostupan veliki broj čvorova jer visina nije uravnotežena. | Pretraživanje je učinkovito u AVL stablu čak i kada postoji veliki broj čvorova u stablu jer je visina uravnotežena. |