Un árbol binario de búsqueda que utiliza una bandera de un bit en cada nodo para identificar el nodo en color: rojo o negro. Un conjunto de restricciones en el color del nodo ayuda a formar un árbol binario balanceado aproximadamente.