TechCodeview

Prije razumijevanja Crveno-crno stablo i AVL stablo razlike, trebali bismo znati o crveno-crnom stablu i AVL stablu odvojeno.

Što je crveno-crno stablo?

Crveno-crno drvo je samouravnoteženo binarno stablo pretraživanja u kojem svaki čvor sadrži jedan dodatni bit informacije koji označava boju čvora. Boja čvora može biti crvena ili crna, ovisno o bitnim informacijama koje čvor pohranjuje.

Svojstva

Sljedeća su svojstva povezana s crveno-crnim stablom:

java program

• Korijenski čvor stabla trebao bi biti crn.
• Crveni čvor može imati samo crne potomke. Ili, možemo reći da dva susjedna čvora ne mogu biti crvene boje.
• Ako čvor nema lijevog ili desnog djeteta, tada se za taj čvor kaže da je čvor lista. Dakle, lijevu i desnu djecu stavljamo ispod čvora lista poznatog kao nula

Dubina crne ili visina crne boje lisnog čvora može se definirati kao broj crnih točaka na koje nailazimo kada se krećemo od lisnog čvora do korijenskog čvora. Jedno od ključnih svojstava crveno-crnog stabla je da svaki lisni čvor treba imati istu crnu dubinu.

Razumimo ovo svojstvo kroz primjer.

U gornjem stablu postoji pet čvorova, od kojih je jedan crveni, a ostala četiri crna. Postoje tri lisna čvora u gornjem stablu. Sada izračunavamo crnu dubinu svakog čvora lista. Kao što možemo uočiti da je crna dubina sva tri lisna čvora 2; dakle, to je crveno-crno drvo.

Ako stablo ne ispunjava nijedno od gornja tri svojstva, onda nije crveno-crno stablo.

Visina crveno-crnog stabla

Uzmite h kao visinu stabla koje ima n čvorova. Koja bi bila najmanja vrijednost n?. Vrijednost n je najmanja kada su svi čvorovi crni. Ako stablo sadrži sve crne čvorove, tada bi stablo bilo potpuno binarno stablo. Ako je visina kompletnog binarnog stabla h, tada je broj čvorova u stablu:

n = 2h -1

Koja bi bila najveća vrijednost n?

Vrijednost n je najveća kada svaki crni čvor ima dva crvena djeteta, ali crveni čvor ne može imati crvenu djecu, tako da će imati crnu djecu. Na taj način postoje izmjenični slojevi crne i crvene djece. Dakle, ako je broj crnih slojeva h, tada je i broj crvenih slojeva h; dakle, ukupna visina stabla postaje 2h. Ukupan broj čvorova je:

n = 2*2h-1

Što je AVL stablo?

An AVL stablo je samo-balansirajuće binarno stablo pretraživanja ako promatramo donji slučaj, a to je binarno stablo pretraživanja i uravnoteženo stablo.

U gornjem stablu, najgora vremenska složenost za traženje elementa je O(h), tj. visina stabla. U gornjem slučaju, broj usporedbi napravljenih za pretraživanje 17 elementa je 4, a visina stabla je također 4.

Ako uzmemo u obzir iskrivljeno binarno stablo, kao što je prikazano u nastavku:

U gornjem desnom iskrivljenom stablu, broj usporedbi napravljenih za traženje 17 elementa je 5, a broj elemenata prisutnih u stablu je također 5. Prema tome, možemo reći da ako je stablo iskrivljeno binarno stablo tada vremenska složenost bilo bi O(n).

Sada moramo uravnotežiti ova iskrivljena stabla tako da imaju vremensku složenost O(h). Postoji izraz poznat kao a faktor ravnoteže , koji se koristi za samobalansiranje stabla binarnog pretraživanja. Faktor ravnoteže može se izračunati kao:

Vrijednost faktora ravnoteže može biti 1, 0 ili -1. Ako svaki čvor u binarnom stablu ima vrijednost 1, 0 ili -1, tada se za to stablo kaže da je uravnoteženo binarno stablo ili AVL stablo.

Stablo je poznato kao savršeno uravnoteženo stablo ako je faktor ravnoteže svakog čvora 0. AVL stablo je gotovo uravnoteženo stablo jer svaki čvor u stablu ima vrijednost faktora ravnoteže 1, 0 ili -1.

Razlike između crveno-crnog stabla i AVL stabla.

Sljedeće su razlike između crveno-crnog stabla i AVL stabla:

Binarno stablo pretraživanja

Crveno-crno stablo je binarno stablo pretraživanja, a AVL stablo je također binarno stablo pretraživanja.

Pravila

U crveno-crnom stablu primjenjuju se sljedeća pravila:

1. Čvor u crveno-crnom stablu crvene je ili crne boje.
2. Boja korijenskog čvora trebala bi biti crna.
3. Susjedni čvorovi ne bi trebali biti crveni. Drugim riječima, možemo reći da crveni čvor ne može imati crvenu djecu, ali crni čvor može imati crnu djecu.
4. Treba postojati isti broj crnih čvorova u svakoj stazi; tada se samo stablo može smatrati crveno-crnim stablom.
5. Vanjski čvorovi su nulti čvorovi, koji su uvijek crne boje.

Pravilo AVL stabla:

Svaki čvor treba imati faktor ravnoteže -1, 0 ili 1.

Primjer

Na gornjoj slici moramo provjeriti je li stablo crveno-crno stablo ili nije. Kako bismo ovo provjerili, prvo moramo provjeriti je li stablo binarno stablo pretraživanja ili nije. Kao što možemo vidjeti na gornjoj slici, ono zadovoljava sva svojstva stabla binarnog pretraživanja; dakle, to je binarno stablo pretraživanja. Drugo, moramo provjeriti zadovoljava li gore navedena pravila ili ne. Gore navedeno stablo zadovoljava svih gornjih pet pravila; stoga zaključuje da je gore navedeno stablo crveno-crno stablo.

Na gornjoj slici moramo provjeriti je li stablo AVL stablo ili nije. Budući da svaki čvor ima vrijednost faktora ravnoteže -1, 0 ili 1, to je AVL stablo.

Kako se stablo može smatrati uravnoteženim stablom ili ne?

U slučaju crveno-crnog stabla, ako su sva gornja pravila zadovoljena, pod uvjetom da je stablo binarno stablo pretraživanja, tada se za stablo kaže da je crveno-crno stablo.

U slučaju AVL stabla, ako je faktor ravnoteže -1, 0 ili 1, tada se za gornje stablo kaže da je AVL stablo.

Alati koji se koriste za balansiranje

Ako stablo nije uravnoteženo, tada se koriste dva alata za balansiranje stabla u crveno-crnom stablu:

Prebojavanje Rotacija

Ako stablo nije uravnoteženo, tada se koristi jedan alat za balansiranje stabla u AVL stablu:

Rotacija

Učinkovito za koju operaciju

U slučaju crveno-crnog stabla, operacije umetanja i brisanja su učinkovite. Ako se stablo uravnoteži prebojavanjem, tada su operacije umetanja i brisanja učinkovite u crveno-crnom stablu.

U slučaju AVL stabla, operacija pretraživanja je učinkovita jer zahtijeva samo jedan alat za balansiranje stabla.

Vremenska složenost

U slučaju crveno-crnog stabla, vremenska složenost za sve operacije, tj. umetanje, brisanje i pretraživanje je O(logn).

U slučaju AVL stabla, vremenska složenost za sve operacije, tj. umetanje, brisanje i pretraživanje je O(logn).

Razumimo razlike u tabličnom obliku.