Ein binärer Suchbaum, die ein 1-Bit-Flag auf jedem Knoten verwendet, um den Knoten durch Farbe zu identifizieren: entweder rot oder schwarz. Eine Reihe von Einschränkungen auf Knoten Farbe hilft eine etwa ausgeglichene binäre Struktur zu bilden.