Как отличить бинарное дерево от красно-черного дерева и чем они отличаются в реализации и свойствах?

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

Отличия:

• Структура:

  • Бинарное дерево — просто узлы с двумя потомками.
  • Красно-черное дерево — бинарное дерево поиска, где каждый узел окрашен в красный или черный цвет.

• Свойства красно-черного дерева:

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

• Балансировка:

  • Обычное бинарное дерево может быть несбалансированным, что ухудшает производительность поиска до O(n).
  • Красно-черное дерево гарантирует балансировку, обеспечивая операции поиска, вставки и удаления за O(log n).

• Реализация:

  • В красно-черном дереве нужно хранить дополнительный бит цвета в каждом узле и реализовывать алгоритмы поворотов и перекраски для поддержания свойств.

Пример узла красно-черного дерева на Java:

class Node {
    int key;
    Node left, right, parent;
    boolean color; // true - красный, false - черный

    Node(int key) {
        this.key = key;
        this.color = true; // новые узлы красные по умолчанию
    }
}

Таким образом, красно-черное дерево — это сбалансированное бинарное дерево поиска с дополнительными правилами для поддержания баланса и эффективного поиска.