Punamusta puu
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 symmetriseksi 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.
Jotta binäärinen hakupuu olisi punamusta puu, tulee sen toteuttaa seuraavat ehdot.Nämä ehdot takaavat, että punamusta puu on riittävän tasapainoinen, jotta hakurakenteiden perusoperaatiot haku, lisäys ja poisto voidaan tehdä formula_1log formula_2 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
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ä.
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.
Kuvassa olevaan punamustaan puuhun voitaisiin tehdä seuraavanlaiset lisäyksetPoisto 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 (esimerkiksi kuvan puun solmujen 6, 22 ja 27 poistaminen). Tarkastelemme seuraavassa siis vain mustan solmun poistoa.