Een binaire zoekboom die gebruik maakt van een één-bits vlag op elk knooppunt te identificeren van het knooppunt door kleur: rood of zwart. Een aantal beperkingen op knooppunt kleur helpt vormen een ongeveer evenwichtige binaire boom.