Punamusta puu

Wikipedia

Punamusta puu on tasapainotettu binäärinen hakupuu. Punamusta puu sisältää solmuja, joista jokaisella voi olla korkeintaan kaksi lapsisolmua. Binäärisestä hakupuusta punamusta puu eroaa ylimääräisen väribitin perusteella: jokainen puun solmu voi olla väriltään joko punainen tai musta. Tämä yksi bitti/solmu on riittävä määrä tietoa, jolla puu voidaan pitää tasapainoisena.

Punamustan puun keksi vuonna 1972 Rudolf Bayer, joka kutsui keksintöään symmetrisiseksi binääripuuksi. Menetelmä on jonkin verran monimutkaisempi kuin AVL-puu tai tavallinen binäärinen hakupuu. Hakurakenteena se on tehokas. Punamustalle puulle voidaan suorittaa hakuja, lisäyksiä ja poistoja pahimmassakin tapauksessa logaritmisessa ajassa suhteessa puuhun talletettujen alkioiden kokonaismäärään.

[muokkaa] Punamustan puun ominaisuuksia

Punamusta puu

Jotta binäärinen hakupuu olisi punamusta puu, tulee sen toteuttaa seuraavat ehdot.

Jokainen solmu on väriltään joko punainen tai musta.
Juurisolmu on musta.
Punaisen solmun molemmat lapsisolmut ovat mustia.
Jokainen polku juuresta tyhjään alipuuhun (NIL) sisältää saman määrän mustia solmuja.

Nämä ehdot takaavat, että punamusta puu on riittävän tasapainoinen, jotta hakurakenteiden perusoperaatiot haku, lisäys ja poisto voidaan tehdä $O ($ log $n)$ ⁽¹ ajassa. Tulos seuraa siitä, että pisin polku juuresta lehteen on korkeintaan kaksi kertaa niin pitkä kuin lyhin polku: Lyhimmässä ja pisimmässä polussa on molemmissa yhtä monta mustaa solmua (ehto 4). Lyhimmässä mahdollisessa polussa on vain mustia solmuja. Pisimmässä mahdollisessa polussa on mustien solmujen lisäksi punaisia, mutta korkeintaan vain joka toinen (ehto 3). Lisäksi polulla ei voi olla muun värisiä solmuja (ehto 1) ja jokaisen polun pituus on vähintään 1 (ehto 2).

Muita punamustan puun ominaisuuksia ovat

Millään polulla juuresta lehteen ei ole kahta punaista solmua peräkkäin (seuraa suoraan ehdosta 3).
Jos tyhjille alipuille (NIL) määritellään väri, niin niiden tulee olla mustia, koska lisättävä uusi solmu tulee olla punainen eikä kahta punaista solmua saa esiintyä peräkkäin.
Punaisella solmulla on joko 0 (se on lehti) tai 2 lasta (jos lapsia olisi vain yksi, tulisi sen olla musta, jotta kahta punaista solmua ei olisi peräkkäin, mutta toisaalta sen pitäisi olla punainen, jotta mustien solmujen määrä kummassakin haarassa olisi sama, eli 1 lapsi johtaisi ristiriitaan).
Mustan yksilapsisen solmun lapsen väri on punainen ja lapsi on lehtisolmu (muutoin ehto 4 ja/tai ehto 3 eivät olisi voimassa).

Kertaluokkamerkinnät iso O -notaatiolla selitetään artikkelissa asymptoottinen suoritusaika.

[muokkaa] Päivitys

Ehdot voidaan pienellä lisätyöllä pitää voimassa hakurakenteeseen kohdistuvien päivitysoperaatioiden aikana. Päivityksen yhteydessä suoritetaan ensin haku, joka määrää mihin kohtaan puuta uusi lisättävä alkio sijoitetaan tai mikä alkio tulee poistaa. Sen jälkeen puuta joudutaan mahdollisesti muokkaamaan, jotta em. ehdot olisivat voimassa myös päivityksen jälkeen. Nämä muutokset voidaan kuitenkin rajoittaa samaan polkuun tai korkeintaan polulla olevien solmujen sisaruksiin, jolla edettiin juuresta lehteen haun yhteydessä.

[muokkaa] Lisäys

Uusi lisättävä solmu x on aina punainen. 1) Jos x:n isä on musta, ei tarvitse tehdä mitään (mikään ehto ei voi mennä rikki; erikoistapauksena ensimmäisen alkion lisäys tyhjään punamustaan puuhun, jolloin x:n väri vaihdetaan mustaksi, koska siitä tulee puun juuri). 2) Jos isäsolmu on punainen tarvitsee tehdä joko värinvaihto tai kierto. 2.1) Jos isä ja sen sisar ovat molemmat punaisia, pelkkä värinvaihto riittää. Lisätty solmu x pysyy punaisena. Värinvaihdossa isä, isän sisar ja isoisä vaihtavat väriä. Koska isoisä oli musta¹⁾, tulee siitä värinvaihdossa punainen ja tasapainotusta täytyy mahdollisesti jatkaa rekursiivisesti kaksi tasoa ylempänä (eli jos isoisoisäkin oli punainen). 2.2) Jos isän sisar oli musta, täytyy tehdä kierto. 2.2.1) Yksinkertaisessa kierrossa lisätty solmu x pysyy edelleen punaisena. Isoisä, jossa kierto tapahtuu, oli musta¹⁾ ja siitä tulee punainen. Vastaavasti solmu, joka kierretään isoisän paikalle, vaihtaa väriä punaisesta mustaksi. 2.2.2) Kaksinkertaisessa kierrossa lisättävä solmu x kiertyy isoisän paikalle ja sen väri vaihtuu punaisesta mustaksi. Isoisästä tulee tällöin x:n lapsi ja isoisän väri vaihtuu vastaavasti punaiseksi¹⁾.

Esimerkkejä: Kuvassa olevaan punamustaan puuhun voitaisiin tehdä seuraavanlaiset lisäykset

1) Alkiot 0, 10, 12, 14 ja 16 voidaan lisätä ilman, että puuta tarvitsee tasapainottaa.

2.1) Alkioiden 21, 23, 26 ja 28 lisääminen edellyttää värinvaihtoa; tasapainotusta tulee jatkaa ylempänä puussa, koska solmu 25 muuttuu punaiseksi ja sen isä (17) on myös punainen. Uusikin tasapainotus voidaan tehdä värinvaihdolla, koska solmun 25 isä (17) ja sen sisar (8) ovat molemmat punaisia. Värinvaihdossa juuri muuttuu punaiseksi ja se täytyy vaihtaa lopuksi takaisin mustaksi (rekursio päättyy).

2.2.1) Alkion 7 lisääminen edellyttää yksinkertaista kiertoa.

2.2.2) Alkion 5 lisääminen edellyttää kaksinkertaista kiertoa.

Lisätty solmu oli punainen. Jotta tasapainotus olisi tarpeen, tulee isänkin olla punainen (jos isä oli musta, ei tasapainotusta tarvitse tehdä, koska kaikki ehdot ovat voimassa). Tällöin isoisän täytyy alun perin olla musta, koska oletamme puun olleen punamusta puu ennen lisäystä.

[muokkaa] Poisto

Poisto voidaan palauttaa lehden tai yksilapsisen solmun poistoksi (ks. Binäärinen hakupuu). Jos tämän jälkeen poistettava solmu on punainen, sen täytyy olla lehti ja sen poistaminen on helppoa: kaikki ehdot ovat myös poiston jälkeen voimassa (esim. kuvan puun solmujen 6, 22 ja 27 poistaminen). Tarkastelemme seuraavassa siis vain mustan solmun poistoa.

1) Jos poistettavalla solmulla on lapsi, sen täytyy olla punainen lehtisolmu. Tässä tapauksessa poisto on helppo tehdä ja samalla punaisen lapsen väri voidaan vaihtaa mustaksi, jolloin puu on jälleen tasapainossa (esim. kuvassa solmun 1 poisto).

2) Jäljelle jää tapaus, jossa poistettavana on musta lehtisolmu. Jos poistettavan solmun sisar on punainen, voidaan isäsolmussa suorittaa yksinkertainen kierto poistettavan alkion suuntaan, jonka seurauksena poistettava solmu ja sen sisar ovat molemmat mustia. Jäljelle jää kaksi tapausta: 2.1) Sisaruksella ei ole punaista lasta. Tällöin suoritetaan sisaren värinvaihto ja tasapainotusta jatketaan ylempänä puussa rekursiivisesti kuten lisäyksen yhteydessä (alipuun musta korkeus on vähentynyt yhdellä). 2.2) Sisaruksella on vähintään yksi punainen lapsi (esim. kuvan solmun 11 tai 15 poisto). Tällöin tehdään kierto. 2.2.1) Yksinkertainen kierto tehdään vain tapauksessa, jossa vasemmanpuoleisella sisaruksella on yksi vasemmanpuoleinen lapsi tai oikeanpuoleisella sisaruksella on vain yksi oikeanpuoleinen lapsi. Solmujen värit pysyvät alkuperäisinä paitsi, jos juuri oli musta, jolloin sisaruksen lapsi vaihtaa väriä punaisesta mustaksi. 2.2.2) Muutoin tehdään kaksinkertainen kierto (sisaruksella on yksi lapsi, joka on sisäpuolella kuten jos poistettaisiin solmua 11 tai jos sisaruksella on kaksi lasta kuten solmun 15 poistossa). Kaksinkertaisessa kierrossa muiden solmujen värit pysyvät ennallaan paitsi vanhalla ja uudella juurisolmulla, joiden väri vaihtuu, jos ne olivat punaisia.