Edellisessä postauksessa keskustelimme punamustien puiden esittelystä. Tässä postauksessa käsitellään lisäystä. AVL-puiden lisäyksessä käytimme rotaatiota työkaluna tasapainottamisen tekemiseen lisäyksen jälkeen. Punamustassa puussa käytämme kahta työkalua tasapainotuksen tekemiseen.
- Värjäys
- Rotaatio
Värjäys on solmun värin muuttaminen eli jos se on punainen, muutetaan se mustaksi ja päinvastoin. On huomattava, että NULL-solmun väri on aina musta. Lisäksi kokeilemme aina ensin uudelleenvärjäystä, ja jos se ei onnistu, siirrymme kiertämiseen. Seuraavassa on yksityiskohtainen algoritmi. Algoritmeissa on pääasiassa kaksi tapausta, jotka riippuvat sedän väristä. Jos setä on punainen, värjätään uudelleen. Jos setä on musta, tehdään kierto ja/tai uudelleenväritys.
Esitys, jolla työskentelemme, on seuraava:
Tämä esitys perustuu X
Logiikka:
Aluksi lisätään solmu samalla tavalla kuin binääripuussa ja annetaan sille punainen väri. Jos solmu on juurisolmu, vaihda sen väri mustaksi, mutta jos se ei ole juurisolmu, tarkista vanhemman solmun väri. Jos sen väri on musta, älä muuta väriä, mutta jos se ei ole, eli se on punainen, tarkista solmun sedän väri. Jos solmun sedän väri on punainen, vaihda solmun vanhemman ja sedän väri mustaksi ja isoisän väri punaiseksi ja toista sama prosessi solmun (eli isoisän) osalta.
Mutta jos solmun sedällä on musta väri, on 4 mahdollista tapausta:
- Vasemmanpuoleinen vasemmanpuoleinen tapaus (LL-kierto):
- Vasemmanpuoleinen oikeanpuoleinen tapaus (LR-kierto):
- Oikea Oikea Oikea tapaus (RR-kierto):
- Oikea Vasen Oikea tapaus (RL-kierto):
Nyt näiden kiertojen jälkeen, jos solmujen värit eivät sovi yhteen, niin sitten värjätään ne uudelleen.
Algoritmi:
Olkoon x vastikään lisätty solmu.
- Toteuta tavallinen BST-lisäys ja tee vastikään lisättyjen solmujen väriksi PUNAINEN.
- Jos x on juuri, vaihda x:n väriksi MUSTA (koko puun musta korkeus kasvaa 1:llä).
- Toteuta seuraavaa, jos x:n vanhemman väri ei ole MUSTA ja x ei ole juuri.
a) Jos x:n setä on PUNAINEN (Isovanhemman on täytynyt olla musta ominaisuudesta 4)
(i) Muuta vanhemman ja sedän väri mustaksi.
(ii) Muutetaan isovanhemman väri PUNAISEKSI.
(iii) Muuta x = x:n isovanhempi, toista vaiheet 2 ja 3 uudelle x:lle.b) Jos x:n setä on MUSTA, x:lle voi olla neljä konfiguraatiota, x:n vanhempi (p) ja x:n isovanhempi (g) (Tämä on samanlainen kuin AVL-puu)
(i) Vasen vasen tapaus (p on g:n vasen lapsi ja x on p:n vasen lapsi)
(ii) Vasen oikea tapaus (p on g:n vasen lapsi ja x on p:n oikea lapsi)
(iii) Oikea oikea tapaus (Tapauksen i peili)
(iv) Oikea vasen tapaus (Tapauksen ii peili)
Esimerkki: Luodaan punamusta puu, jonka elementit ovat 3, 21, 32 ja 17, tyhjään puuhun.
Ratkaisu:
Kun ensimmäinen elementti lisätään, se lisätään juurisolmuksi ja koska juurisolmulla on musta väri, niin se saa värin musta.
Uusi elementti lisätään aina punaisella värillä ja koska 21 > 3, niin siitä tulee juurisolmun oikeanpuoleisen alipuun osa.
Nyt, kun lisäämme 32:n, huomaamme, että siinä on punainen isä-lapsi-pari, joka rikkoo puna-mustan puun sääntöä, joten joudumme kääntämään sen. Lisäksi näemme RR-kierron ehdot (juurisolmun nollasolmun katsominen mustaksi), joten kierron jälkeen juurisolmu ei voi olla punainen, joten meidän on värjättävä puu uudelleen, jolloin tuloksena on yllä esitetty puu.
Nyt kun lisäämme uuden elementin, vanhemman ja lapsen solmut, joilla on punainen väri, näkyvät jälleen ja tässä meidän on värjättävä ne uudelleen. Näemme, että sekä vanhemman solmun että enon solmun väri on punainen, joten muutamme yksinkertaisesti niiden värin mustaksi ja isoisän värin punaiseksi. Koska isoisä on juurisolmu, muutamme sen värin jälleen mustaksi, jolloin tuloksena on yllä esitetty puu.
Lopullinen puurakenne:
Lopullinen puu näyttää tältä
Katsokaa C-ohjelma puna-mustan puun lisäämistä varten edellä mainitun algoritmin täydellistä toteutusta varten.
Puna-musta puu | Sarja 3 (Poista)