В чем разница между обычным и красно-черным деревом?

Разница между обычным BST и красно-чёрным деревом

Оба это двоичные деревья поиска, но красно-чёрное дерево (Red-Black Tree) добавляет дополнительные свойства для гарантирования сбалансированности. Это критично для обеспечения logarithmic операций даже в худших случаях.

Обычное двоичное дерево поиска (BST)

Определение: Двоичное дерево, где для каждого узла:

• Все значения в левом поддереве меньше значения узла
• Все значения в правом поддереве больше значения узла

public class BSTNode<T extends Comparable<T>> {
    T value;
    BSTNode<T> left;
    BSTNode<T> right;
}

public class BinarySearchTree<T extends Comparable<T>> {
    private BSTNode<T> root;
    
    // Поиск — O(log n) в среднем, O(n) в худшем
    public BSTNode<T> search(T value) {
        return searchHelper(root, value);
    }
    
    private BSTNode<T> searchHelper(BSTNode<T> node, T value) {
        if (node == null) return null;
        
        int cmp = value.compareTo(node.value);
        if (cmp < 0) {
            return searchHelper(node.left, value);
        } else if (cmp > 0) {
            return searchHelper(node.right, value);
        } else {
            return node;
        }
    }
    
    // Вставка
    public void insert(T value) {
        root = insertHelper(root, value);
    }
    
    private BSTNode<T> insertHelper(BSTNode<T> node, T value) {
        if (node == null) {
            return new BSTNode<>(value);
        }
        
        int cmp = value.compareTo(node.value);
        if (cmp < 0) {
            node.left = insertHelper(node.left, value);
        } else if (cmp > 0) {
            node.right = insertHelper(node.right, value);
        }
        return node;
    }
}

Проблема обычного BST:

Если вставить элементы в отсортированном порядке, дерево вырождается в линейный список!

// Вставляем: 1, 2, 3, 4, 5
// Обычное BST становится:
    1
     \
      2
       \
        3
         \
          4
           \
            5

// Это уже не дерево, а линейный список!
// Поиск, вставка, удаление — O(n) вместо O(log n)

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

Определение: Это самобалансирующееся BST, где каждый узел имеет цвет (красный или чёрный) и соблюдаются следующие свойства:

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

enum Color {
    RED, BLACK
}

public class RBTreeNode<T extends Comparable<T>> {
    T value;
    Color color;
    RBTreeNode<T> left;
    RBTreeNode<T> right;
    RBTreeNode<T> parent;
    
    public RBTreeNode(T value) {
        this.value = value;
        this.color = Color.RED; // новые узлы красные по умолчанию
    }
}

public class RedBlackTree<T extends Comparable<T>> {
    private RBTreeNode<T> root;
    private static final RBTreeNode<?> NIL = new RBTreeNode<>(null);
    
    static {
        ((RBTreeNode<Object>) NIL).color = Color.BLACK;
    }
    
    public void insert(T value) {
        // 1. Вставить как в обычное BST
        RBTreeNode<T> node = insertBST(value);
        
        // 2. Восстановить свойства красно-чёрного дерева
        fixInsert(node);
    }
    
    private void fixInsert(RBTreeNode<T> node) {
        // Исправление после вставки красного узла
        while (node != root && node.parent.color == Color.RED) {
            if (node.parent == node.parent.parent.left) {
                RBTreeNode<T> uncle = node.parent.parent.right;
                
                // Случай 1: дядя красный
                if (uncle != null && uncle.color == Color.RED) {
                    node.parent.color = Color.BLACK;
                    uncle.color = Color.BLACK;
                    node.parent.parent.color = Color.RED;
                    node = node.parent.parent;
                } else {
                    // Случай 2-3: дядя чёрный (требует ротации)
                    if (node == node.parent.right) {
                        node = node.parent;
                        rotateLeft(node);
                    }
                    node.parent.color = Color.BLACK;
                    node.parent.parent.color = Color.RED;
                    rotateRight(node.parent.parent);
                }
            } else {
                // Зеркальные случаи...
            }
        }
        root.color = Color.BLACK;
    }
    
    private void rotateLeft(RBTreeNode<T> node) {
        RBTreeNode<T> rightChild = node.right;
        node.right = rightChild.left;
        
        if (rightChild.left != NIL) {
            rightChild.left.parent = node;
        }
        
        rightChild.parent = node.parent;
        if (node.parent == null) {
            root = rightChild;
        } else if (node == node.parent.left) {
            node.parent.left = rightChild;
        } else {
            node.parent.right = rightChild;
        }
        
        rightChild.left = node;
        node.parent = rightChild;
    }
    
    private void rotateRight(RBTreeNode<T> node) {
        // Зеркальная операция rotateLeft
    }
}

Сравнение

Визуальный пример

// Обычное BST при вставке 1,2,3,4,5:
    1                  
     \            
      2           
       \          
        3         
         \        
          4       
           \      
            5     
Высота: 5, поиск: O(n)

// Красно-чёрное дерево при вставке 1,2,3,4,5:
        2(B)
       / \
      1   4(B)
     (R) / \
        3   5
       (R) (R)
Высота: 3, поиск: O(log n)

Java в реальных приложениях

В Java красно-чёрные деревья используются в:

// HashMap использует красно-чёрные деревья для бакетов
private static final int TREEIFY_THRESHOLD = 8;
private static final int UNTREEIFY_THRESHOLD = 6;

// TreeMap использует красно-чёрное дерево
Map<String, Integer> map = new TreeMap<>();
map.put("apple", 1);     // O(log n)
map.put("banana", 2);    // O(log n)
map.put("cherry", 3);    // O(log n)

Integer value = map.get("apple");    // O(log n)
map.remove("banana");               // O(log n)

// TreeSet тоже использует красно-чёрное дерево
Set<Integer> set = new TreeSet<>();
set.add(5);          // O(log n)
set.add(3);          // O(log n)
set.add(7);          // O(log n)

booleancontains = set.contains(3); // O(log n)

// Итерирование в отсортированном порядке — O(n)
for (Integer num : set) {
    System.out.println(num); // 3, 5, 7
}

Когда какое дерево использовать

Обычное BST:

• Учебные цели
• Уже отсортированные данные (редко)
• Когда нет требований к гарантированной производительности

Красно-чёрное дерево:

• HashMap/TreeMap в Java
• Когда нужны гарантированные O(log n) операции
• Большие наборы данных
• Когда данные приходят в случайном порядке

Другие самобалансирующиеся деревья

Красно-чёрные деревья — не единственный вариант:

• AVL деревья — более строгий баланс, чаще ротации при вставке, быстрее поиск
• B-деревья — для дисковых систем, используются в БД
• Splay деревья — оптимизируют для частого доступа
• 2-3 деревья — основа красно-чёрных деревьев

Вывод

Обычное двоичное дерево поиска имеет серьёзный недостаток — оно может вырождаться в линейный список. Красно-чёрное дерево решает эту проблему с помощью цветов узлов и ротаций, гарантируя O(log n) для всех операций. В Java обычно используются красно-чёрные деревья в TreeMap и TreeSet, что делает их надёжным выбором для приложений, требующих упорядоченной коллекции с гарантированной производительностью.