Что такое красно-черное дерево

Красно-черное дерево — это самобалансирующееся бинарное дерево поиска, где каждый узел имеет дополнительный атрибут — цвет (красный или черный). Оно поддерживает баланс при вставке и удалении, гарантируя логарифмическую сложность операций.

Основные свойства:

1. Каждый узел — либо красный, либо черный.
2. Корень всегда черный.
3. Все листья (NIL) — черные.
4. У красного узла оба потомка черные.
5. Пути от узла до любых листьев содержат одинаковое количество черных узлов.

Пример структуры узла:

class Node {
  constructor(value, color = 'RED') {
    this.value = value;
    this.left = null;
    this.right = null;
    this.parent = null;
    this.color = color;
  }
}

Балансировка достигается поворотами и перекрашиванием узлов при нарушениях свойств. Используется в реализациях TreeMap и TreeSet в Java, map и set в C++.