Что такое красно-черное дерево и зачем оно используется?

Question

Красно-черное дерево — это самобалансирующееся бинарное дерево поиска.
Оно автоматически поддерживает небольшую высоту дерева.
За счёт этого операции поиска, вставки и удаления выполняются за логарифмическое время.
TreeMap и TreeSet в Java основаны именно на этой структуре.
Главная цель — предсказуемая производительность.

YeaHub · Accepted Answer

Перед тем как говорить о применении, важно понять основную идею структуры.Что такое красно-черное деревоОпределение:Красно-черное дерево — это бинарное дерево поиска, в котором каждый узел имеет цвет (красный или черный), а специальные правила гарантируют балансировку.Основные свойстваУ дерева есть набор инвариантов:Каждый узел либо красный, либо черный.Корень всегда черный.У красного узла не может быть красных потомков.Любой путь от узла до листа содержит одинаковое количество черных узлов.Эти правила не дают дереву сильно перекоситься.Зачем оно используетсяИспользование красно-черного дерева позволяет:Ограничить высоту дерева величиной O(log n).Избежать деградации производительности.Гарантировать стабильное время выполнения операций.Где применяется в JavaВ стандартной библиотеке:TreeMapTreeSetВнутренние структуры HashMap (с Java 8 при большом числе коллизий)Краткий выводКрасно-черное дерево используется для обеспечения логарифмической сложности операций и стабильной производительности при работе с упорядоченными данными.