Инварианты (правила красно‑чёрного дерева):
- Каждый узел либо красный, либо чёрный (поле цвета).
- Корень чёрный.
- Все NIL‑листья считаются чёрными (обычно неявные пустые дети).
- У красного узла оба ребёнка чёрные (нет двух подряд красных).
- Для каждого узла все простые пути до NIL‑листьев содержат одинаковое число чёрных узлов (одинаковая чёрная высота).
Следствия и оценка высоты:
- Обозначая число узлов $n$ и высоту дерева $h$, выполняется верхняя оценка
$$h\le 2{\log }_2(n+1).$$ - Для сравнения, AVL‑дерево имеет более жёсткую оценку высоты: примерно
$$h_{AVL}\approx 1.44{\log }_{2}n,$$ поэтому AVL обычно чуть «выше» сбалансировано (короче) и даёт быстрее операции поиска.
Операции с логарифмической сложностью:
- Поиск произвольного ключа, поиск минимума/максимума, предшественника/наследника: $O(\log n)$.
- Вставка: перестройка (повороты + перекраски) даёт временную сложность $O(\log n)$. Число поворотов ограничено константой (обычно $\le 2$).
- Удаление: тоже $O(\log n)$ времени; операция может потребовать до $O(\log n)$ итераций перекраски и в худшем случае $O(\log n)$ поворотов.
- Память: дополнительное поле цвета (1 бит) на узел.
Где выбирать красно‑чёрное дерево вместо AVL:
- Когда нужны сбалансированные динамические множества/словарь с частыми вставками и удалениями — RB‑дерево обычно требует меньше структурных изменений (меньше поворотов) при обновлениях, поэтому быстрее в режиме интенсивных модификаций.
- Когда важна простота и стабильность реализации: алгоритмы балансировки RB проще в некоторых реализациях и широко стандартизованы (используются в std::map, Java TreeMap, Linux kernel rb_tree).
- Когда небольшая потеря в скорости поиска (из‑за чуть большей высоты по сравнению с AVL) приемлема ради более дешёвых обновлений.
- Если главным является максимальная скорость поисков и почти отсутствуют модификации — AVL может быть предпочтительнее из‑за меньшей высоты.
Коротко: RB сохраняет гарантированную логарифмическую сложность всех основных операций, обеспечивает меньше затрат на переуравнивание при вставке/удалении и потому чаще применяется в общих библиотеках и системных структурах данных; AVL выигрывает в чисто читаемых (read‑heavy) сценариях за счёт жёсткой балансировки.