Punamusta puu
tasapainotettu binäärinen hakupuu / From Wikipedia, the free encyclopedia
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.
Tähän artikkeliin tai osioon ei ole merkitty lähteitä, joten tiedot kannattaa tarkistaa muista tietolähteistä. Voit auttaa Wikipediaa lisäämällä artikkeliin tarkistettavissa olevia lähteitä ja merkitsemällä ne ohjeen mukaan. |
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.