En binær søgning træ, som bruger et én-bit flag på hver node til at identificere noden af farve: enten rød eller sort. Et sæt begrænsninger på node farve hjælper med at danne en ca afbalanceret binært træ.