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 tasapainottamiseen.
- Värjäys
- Rotaatio
Värjäys on solmun värin muuttaminen eli jos solmu on punainen, muutetaan se mustaksi ja päinvastoin. On huomattava, että NULL-solmun väri on aina musta. Lisäksi kokeilemme aina ensin värin muuttamista, ja jos värin muuttaminen 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 täytyy lisätä solmu samalla tavalla kuin binääripuussa ja antaa 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 vasen tapaus (LL-kierto):
- Vasemmanpuoleinen oikeanpuoleinen tapaus (LR-kierto):
- Oikea oikea tapaus (RR-kierto):
- Oikea vasen tapaus (RL-kierto):
Nyt näiden kiertojen jälkeen, jos solmupisteiden värit eivät täsmää keskenään, 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 mustan 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, näemme, 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 punamustan puun lisäämistä varten edellä mainitun algoritmin täydellistä toteutusta varten.
Punamusta puu | Sarja 3 (Poista)