Pred razumevanjem Rdeče-črno drevo in AVL drevo razlike, bi morali vedeti o rdeče-črnem drevesu in drevesu AVL ločeno.

Kaj je rdeče-črno drevo?

Rdeče-črno drevo je samouravnovešeno binarno iskalno drevo v katerem vsako vozlišče vsebuje en dodaten bit informacije, ki označuje barvo vozlišča. Barva vozlišča je lahko rdeča ali črna, odvisno od bitnih informacij, ki jih shrani vozlišče.

Lastnosti

Sledijo lastnosti, povezane z rdeče-črnim drevesom:

• Korensko vozlišče drevesa mora biti črno.
• Rdeče vozlišče ima lahko samo črne otroke. Ali pa lahko rečemo, da dve sosednji vozlišči ne moreta biti rdeče barve.
• Če vozlišče nima levega ali desnega otroka, se to vozlišče imenuje listno vozlišče. Torej smo postavili levega in desnega otroka pod listno vozlišče, znano kot nič

Črno globino ali črno višino listnega vozla lahko definiramo kot število črnih, na katere naletimo, ko se premaknemo iz listnega vozla v korensko vozlišče. Ena od ključnih lastnosti rdeče-črnega drevesa je, da mora imeti vsako listno vozlišče enako globino črne barve.

Razumejmo to lastnost na primeru.

V zgornjem drevesu je pet vozlišč, od katerih je eno rdeče, druga štiri vozlišča pa črna. V zgornjem drevesu so trije listni vozli. Zdaj izračunamo črno globino vsakega listnega vozla. Kot lahko opazimo, je črna globina vseh treh listnih vozlov 2; torej je rdeče-črno drevo.

Če drevo ne izpolnjuje nobene od zgornjih treh lastnosti, potem ni rdeče-črno drevo.

Višina rdeče-črnega drevesa

Upoštevajte h kot višino drevesa z n vozlišči. Kakšna bi bila najmanjša vrednost n?. Vrednost n je najmanjša, ko so vsa vozlišča črna. Če drevo vsebuje vsa črna vozlišča, bi bilo drevo popolno binarno drevo. Če je višina celotnega binarnega drevesa h, potem je število vozlišč v drevesu:

n = 2h -1

Kakšna bi bila največja vrednost n?

Vrednost n je največja, če ima vsako črno vozlišče dva rdeča otroka, vendar rdeče vozlišče ne more imeti rdečih otrok, tako da bo imelo črne otroke. Na ta način se izmenjujejo plasti črnih in rdečih otrok. Torej, če je število črnih plasti h, potem je tudi število rdečih plasti h; tako skupna višina drevesa postane 2h. Skupno število vozlišč je:

n = 2*2h-1

Kaj je drevo AVL?

An AVL drevo je samouravnoteženo binarno iskalno drevo, če upoštevamo spodnji primer, ki je binarno iskalno drevo in uravnoteženo drevo.

V zgornjem drevesu je najslabša časovna zahtevnost iskanja elementa O(h), tj. višina drevesa. V zgornjem primeru je število primerjav, izvedenih za iskanje elementa 17, 4 in višina drevesa je prav tako 4.

Če upoštevamo poševno binarno drevo, kot je prikazano spodaj:

V zgornjem desnem poševnem drevesu je število primerjav, opravljenih za iskanje elementa 17, 5 in število elementov, prisotnih v drevesu, je prav tako 5. Zato lahko rečemo, da če je drevo poševno binarno drevo, potem je časovna kompleksnost bi bil O(n).

Zdaj moramo ta poševna drevesa uravnotežiti tako, da bodo imela časovno kompleksnost O(h). Obstaja izraz, znan kot a faktor ravnotežja , ki se uporablja za samouravnoteženje binarnega iskalnega drevesa. Faktor ravnotežja se lahko izračuna kot:

Vrednost faktorja ravnotežja je lahko 1, 0 ali -1. Če ima vsako vozlišče v binarnem drevesu vrednost 1, 0 ali -1, potem je to drevo uravnoteženo binarno drevo ali drevo AVL.

Drevo je znano kot popolnoma uravnoteženo drevo, če je faktor ravnovesja vsakega vozlišča 0. Drevo AVL je skoraj uravnoteženo drevo, ker ima vsako vozlišče v drevesu vrednost faktorja ravnovesja 1, 0 ali -1.

Razlike med rdeče-črnim drevesom in drevesom AVL.

V nadaljevanju so navedene razlike med rdeče-črnim drevesom in drevesom AVL:

Binarno iskalno drevo

Rdeče-črno drevo je binarno iskalno drevo in AVL drevo je prav tako binarno iskalno drevo.

Pravila

V rdeče-črnem drevesu veljajo naslednja pravila:

1. Vozlišče v rdeče-črnem drevesu je rdeče ali črne barve.
2. Barva koreninskega vozlišča mora biti črna.
3. Sosednja vozlišča ne smejo biti rdeča. Z drugimi besedami, lahko rečemo, da rdeče vozlišče ne more imeti rdečih otrok, črno vozlišče pa lahko črne otroke.
4. Na vsaki poti mora biti enako število črnih vozlišč; potem se samo drevo lahko šteje za rdeče-črno drevo.
5. Zunanja vozlišča so ničelna vozlišča, ki so vedno črne barve.

Pravilo drevesa AVL:

Vsako vozlišče mora imeti faktor ravnovesja -1, 0 ali 1.

Primer

Na zgornji sliki moramo preveriti, ali je drevo rdeče-črno drevo ali ne. Da bi to preverili, moramo najprej preveriti, ali je drevo binarno iskalno drevo ali ne. Kot lahko opazimo na zgornji sliki, izpolnjuje vse lastnosti binarnega iskalnega drevesa; zato je binarno iskalno drevo. Drugič, preveriti moramo, ali izpolnjuje zgoraj omenjena pravila ali ne. Zgornje drevo izpolnjuje vseh zgornjih pet pravil; zato sklepa, da je zgornje drevo rdeče-črno drevo.

Na zgornji sliki moramo preveriti, ali je drevo drevo AVL ali ne. Ker ima vsako vozlišče vrednost faktorja ravnovesja -1, 0 ali 1, je to drevo AVL.

Kako lahko drevo štejemo za uravnoteženo drevo ali ne?

Če so v primeru rdeče-črnega drevesa izpolnjena vsa zgornja pravila, pod pogojem, da je drevo binarno iskalno drevo, se za drevo reče, da je rdeče-črno drevo.

'abc's v številkah'

V primeru drevesa AVL, če je faktor ravnotežja -1, 0 ali 1, se za zgornje drevo reče, da je drevo AVL.

Orodja, ki se uporabljajo za uravnoteženje

Če drevo ni uravnoteženo, se za uravnoteženje drevesa v rdeče-črnem drevesu uporabita dve orodji:

Prebarvanje Rotacija

Če drevo ni uravnoteženo, se za uravnoteženje drevesa v drevesu AVL uporabi eno orodje:

Rotacija

Učinkovito za katero operacijo

V primeru rdeče-črnega drevesa sta operaciji vstavljanja in brisanja učinkoviti. Če je drevo uravnoteženo s prebarvanjem, so operacije vstavljanja in brisanja učinkovite v rdeče-črnem drevesu.

V primeru drevesa AVL je operacija iskanja učinkovita, saj zahteva samo eno orodje za uravnoteženje drevesa.

Časovna zapletenost

V primeru rdeče-črnega drevesa je časovna zahtevnost za vse operacije, tj. vstavljanje, brisanje in iskanje, O(logn).

V primeru drevesa AVL je časovna zahtevnost za vse operacije, tj. vstavljanje, brisanje in iskanje, O(logn).

Razumejmo razlike v obliki tabele.