Дерево двоичного поиска, который использует один битовый флаг на каждом узле для идентификации узла по цвету: красный или черный. Набор ограничений на цвет узла помогает образуют примерно сбалансированным двоичное дерево.