Uma árvore de busca binária, que usa uma bandeira de um bit em cada nó para identificar o nó pela cor: vermelho ou preto. Um conjunto de restrições na cor do nó ajuda a formar uma árvore binária aproximadamente balanceada.