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.

Edellinen teksti on suoraa kopiota wikipediasta, vaikka ihan tuohon malliin sen itsekin ehdin ajatella ;)

Tänään on viimeinkin hengähdyspäivä, vaikka opiskeluhommia onkin pinossa ja jonossa. Retkiromppeiden järjestelyä riittää, uusittu passi pitäisi hakea poliisilaitokselta, ja työpaikallakin olisi aihetta käväistä yms. Wanhan äitini kanssa on akuuttia huolta ja kaikenlaista muutakin kinkkistä löytyy, jos rupeaa laskemaan.

Nyt saan kuitenkin olla aika itseohjautuva. Kovin rauhoittava ajatus se :D

Kuvat ovat edellisiltä hengähdyshetkiltä Lapista. Mukavat raikkaat muistot kontrastina kaikenlaisiin kummallisiin paineisiin, joita tömähtelee sieltä täältä. Väsyneenä on suojaton, mutta nyt on elpyminen alkanut.

Kyllä se kohta löytyy. Se on jämpti niin!