Красное-чёрное дерево

Красно-чёрное дерево(англ. red-black tree) - самобалансирующееся бинарное дерево поиска (англ. Binary Search Tree, BST) со следующими свойствами:

• Каждая вершина имеет цвет: красный или чёрный
• Корень дерева - чёрный
• У каждой нелистовой вершины ровно два ребёнка
• Все листья чёрные и фиктивные
• У красной вершины оба ребёнка чёрные
• Чёрная высота каждой вершины определена корректно