Что такое красно-чёрные деревья? Что это за структура данных? Чем она отличается от обыкновенного бинарного дерева?
https://habr.com/post/330644/ - почитайте вот эту статейку на Хабре, тут неплохо о красно-чёрных деревьях написано.
А вообще, красно черные деревья - это сбалансированные деревья, элементы которых "окрашены" в красный или чёрный цвета. Короче говоря, они имеют поля, обозначающие их цвет.
Вот такие свойства различают бинарное дерево от красно-чёрного:
1) Каждый узел окрашен либо в красный, либо в черный цвет (в структуре данных узла появляется дополнительное поле – бит цвета).
2) Корень окрашен в черный цвет.
3) Листья(так называемые NULL-узлы) окрашены в черный цвет.
4) Каждый красный узел должен иметь два черных дочерних узла. Нужно отметить, что у черного узла могут быть черные дочерние узлы. Красные узлы в качестве дочерних могут иметь только черные.
5) Пути от узла к его листьям должны содержать одинаковое количество черных узлов(это черная высота).