TechCodeview

Ennen kuin ymmärrät Puna-musta puu ja AVL-puu eroista, meidän pitäisi tietää punamusta-puusta ja AVL-puusta erikseen.

Mikä on puna-musta puu?

Punamusta puu on itse tasapainoinen binäärihakupuu jossa jokainen solmu sisältää yhden ylimääräisen bitin informaatiota, joka ilmaisee solmun värin. Solmun väri voi olla joko punainen tai musta riippuen solmun tallentamasta bittitiedosta.

Ominaisuudet

Seuraavat ovat punamustapuuhun liittyvät ominaisuudet:

• Puun juurisolmun tulee olla musta.
• Punaisella solmulla voi olla vain mustia lapsia. Tai voimme sanoa, että kaksi vierekkäistä solmua eivät voi olla punaisia.
• Jos solmulla ei ole vasenta tai oikeaa lasta, tämän solmun sanotaan olevan lehtisolmu. Joten laitamme vasemman ja oikean lapsen lehtisolmun alle nolla

Lehtisolmun mustan syvyys tai mustan korkeus voidaan määritellä mustan määräksi, jonka kohtaamme siirryttäessä lehden solmupisteestä juurisolmuun. Yksi Red-Black-puun tärkeimmistä ominaisuuksista on, että jokaisella lehtisolmulla tulee olla sama mustan syvyys.

Ymmärretään tämä ominaisuus esimerkin avulla.

Yllä olevassa puussa on viisi solmua, joista yksi on punainen ja muut neljä solmua ovat mustia. Yllä olevassa puussa on kolme lehtisolmua. Nyt laskemme jokaisen lehtisolmun mustan syvyyden. Kuten voimme havaita, että kaikkien kolmen lehtisolmun mustan syvyys on 2; siksi se on punamusta puu.

Jos puu ei täytä mitään yllä olevista kolmesta ominaisuudesta, se ei ole punamusta puu.

Punamustan puun korkeus

Oletetaan h sen puun korkeudeksi, jossa on n solmua. Mikä olisi n:n pienin arvo?. Arvo n on pienin, kun kaikki solmut ovat mustia. Jos puu sisältää kaikki mustat solmut, puu olisi täydellinen binääripuu. Jos täydellisen binääripuun korkeus on h, niin puun solmujen lukumäärä on:

n = 2h-1

Mikä olisi n:n suurin arvo?

N:n arvo on suurin, kun jokaisella mustalla solmulla on kaksi punaista lasta, mutta punaisella solmulla ei voi olla punaisia ​​lapsia, joten sillä on mustia lapsia. Tällä tavalla on vuorotellen mustia ja punaisia ​​lapsia. Joten jos mustien kerrosten lukumäärä on h, niin punaisten kerrosten lukumäärä on myös h; siksi puun kokonaiskorkeudeksi tulee 2h. Solmujen kokonaismäärä on:

n = 2*2h-1

Mikä on AVL-puu?

An AVL puu on itsetasapainottava binäärihakupuu, jos tarkastelemme alla olevaa tapausta, joka on binäärihakupuu ja tasapainotettu puu.

Yllä olevassa puussa pahin aikamonimutkaisuus elementin etsimiselle on O(h), eli puun korkeus. Yllä olevassa tapauksessa 17 elementin hakuun tehtyjen vertailujen lukumäärä on 4 ja puun korkeus on myös 4.

Jos tarkastelemme vinoa binääripuuta, kuten alla on esitetty:

Yllä olevassa oikeanpuoleisessa vinossa puussa 17 elementin etsimiseen tehtyjen vertailujen määrä on 5 ja puussa olevien elementtien määrä on myös 5. Näin ollen voidaan sanoa, että jos puu on vino binääripuu, niin aika monimutkaisuus olisi O(n).

Nyt meidän on tasapainotettava nämä vinopuut niin, että niillä on aikamonimutkaisuus O(h). On olemassa termi, joka tunnetaan nimellä a tasapainotekijä , jota käytetään binäärihakupuun tasapainottamiseen. Tasapainokerroin voidaan laskea seuraavasti:

Tasapainotekijän arvo voi olla joko 1, 0 tai -1. Jos jokaisen binaaripuun solmun arvo on joko 1, 0 tai -1, niin puun sanotaan olevan tasapainotettu. binäärinen puu tai AVL-puu.

Puu tunnetaan täydellisesti tasapainotettuna puuna, jos kunkin solmun tasapainokerroin on 0. AVL-puu on lähes tasapainoinen puu, koska puun jokaisella solmulla on tasapainotekijän arvo joko 1, 0 tai -1.

Erot punamusta-puun ja AVL-puun välillä.

Seuraavassa on erot punamusta-puun ja AVL-puun välillä:

Binäärihakupuu

Puna-musta puu on binäärihakupuu ja AVL-puu on myös binäärihakupuu.

säännöt

Seuraavia sääntöjä sovelletaan punamustapuussa:

1. Punamustan puun solmu on väriltään joko punainen tai musta.
2. Juurisolmun värin tulee olla musta.
3. Vierekkäiset solmut eivät saa olla punaisia. Toisin sanoen voidaan sanoa, että punaisella solmulla ei voi olla punaisia ​​lapsia, mutta mustalla solmulla voi olla mustia lapsia.
4. Jokaisessa polussa tulisi olla sama määrä mustia solmuja; silloin vain puuta voidaan pitää puna-mustana puuna.
5. Ulkoiset solmut ovat nollasolmuja, jotka ovat aina mustia.

AVL-puun sääntö:

Jokaisen solmun tasapainokertoimen tulee olla joko -1, 0 tai 1.

Esimerkki

Yllä olevassa kuvassa meidän on tarkistettava, onko puu punainen-musta puu vai ei. Tämän tarkistamiseksi meidän on ensin tarkistettava, onko puu binäärihakupuu vai ei. Kuten voimme havaita yllä olevasta kuvasta, se täyttää kaikki binäärihakupuun ominaisuudet; siksi se on binäärihakupuu. Toiseksi meidän on tarkistettava, täyttääkö se edellä mainitut säännöt vai ei. Yllä oleva puu täyttää kaikki edellä mainitut viisi sääntöä; siksi se päättelee, että yllä oleva puu on punamusta puu.

Yllä olevassa kuvassa meidän on tarkistettava, onko puu AVL-puu vai ei. Koska jokaisella solmulla on tasapainotekijän arvo joko -1, 0 tai 1, se on AVL-puu.

Kuinka puuta voidaan pitää tasapainoisena puuna vai ei?

Punamustan puun tapauksessa, jos kaikki yllä olevat säännöt täyttyvät, edellyttäen että puu on binäärihakupuu, puun sanotaan olevan punamusta puu.

AVL-puun tapauksessa, jos tasapainokerroin on -1, 0 tai 1, niin yllä olevan puun sanotaan olevan AVL-puu.

Tasapainotukseen käytetyt työkalut

Jos puu ei ole tasapainossa, käytetään kahta työkalua puun tasapainottamiseen puna-mustassa puussa:

Uudelleenvärjäys Kierto

Jos puu ei ole tasapainossa, käytetään yhtä työkalua puun tasapainottamiseen AVL-puussa:

Kierto

Tehokas mihin toimintoon

Puna-mustan puun tapauksessa lisäys- ja poistotoiminnot ovat tehokkaita. Jos puu tasapainottuu uudelleenvärjäyksen myötä, niin lisäys- ja poistotoiminnot ovat tehokkaita punamustaisessa puussa.

AVL-puun tapauksessa hakutoiminto on tehokas, koska se vaatii vain yhden työkalun puun tasapainottamiseen.

Aika monimutkaisuus

Puna-musta-puutapauksessa kaikkien toimintojen, eli lisäyksen, poiston ja haun, aikamonimutkaisuus on O(logn).

AVL-puun tapauksessa kaikkien toimintojen, ts. lisäyksen, poiston ja haun, aikamonimutkaisuus on O(logn).

aakkoset ja numerot

Ymmärrämme erot taulukkomuodossa.