Чем отличается обычное бинарное дерево поиска от красно-черного дерева?

«Чем отличается обычное бинарное дерево поиска от красно-черного дерева?» — вопрос из категории Алгоритмы и структуры данных, который задают на 10% собеседований Java Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Ответ

Красно-черное дерево — это частный случай самобалансирующегося бинарного дерева поиска (BST), решающий главную проблему обычного BST.

Обычное бинарное дерево поиска:

  • Следует базовому правилу: left child < parent < right child.
  • При неудачной последовательности вставок (например, отсортированные данные) может выродиться в линейный список.
  • Худшая временная сложность операций поиска, вставки, удаления: O(n).

Красно-черное дерево (Red-Black Tree):

  • Налагает дополнительные ограничения для поддержания баланса:
    1. Каждый узел имеет цвет: красный или черный.
    2. Корень всегда черный.
    3. Два красных узла не могут быть родителем и потомком (нет двух подряд идущих красных узлов).
    4. Все пути от любого узла до его листьев содержат одинаковое количество черных узлов (черная высота).
  • Эти правила гарантируют, что дерево остается примерно сбалансированным.
  • Гарантированная временная сложность операций: O(log n).

Пример структуры узла и балансировки:

class RBNode {
    int key;
    RBNode left, right, parent;
    boolean isRed; // true для красного, false для черного
}
// При вставке/удалении выполняются вращения и перекрашивания для сохранения свойств.

Итог: Красно-черное дерево жертвует небольшой сложностью операций (из-за перекрашиваний) для гарантии логарифмической производительности, что критично для реализаций TreeMap или TreeSet в Java.