Binární vyhledávací strom, který využívá jeden bit příznaku na každém uzlu k identifikaci uzlu podle barvy: červená nebo černá. Sadu omezení uzlu barva pomáhá tvořit přibližně vyrovnaný binární strom.