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

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

Да, красно-чёрное дерево является бинарным деревом поиска (Binary Search Tree, BST). Более точно, это самобалансирующееся бинарное дерево поиска, которое гарантирует логарифмическую высоту благодаря специальным правилам раскраски узлов в красный и чёрный цвета.

Что такое бинарное дерево поиска?

// Бинарное дерево — это дерево, где каждый узел имеет макс. 2 потомка
public class TreeNode<T extends Comparable<T>> {
    T value;
    TreeNode<T> left;   // Левый потомок
    TreeNode<T> right;  // Правый потомок
    
    public TreeNode(T value) {
        this.value = value;
    }
}

// Свойство BST: для каждого узла:
// - все значения в левом поддереве < значение узла
// - все значения в правом поддереве > значение узла

//        50
//       /  \
//      30   70
//     / \   / \
//   20  40 60  80

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

Красно-чёрное дерево (Red-Black Tree, RBT) — это бинарное дерево поиска с дополнительными свойствами, обеспечивающими баланс:

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

Структура узла красно-чёрного дерева

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

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

//        50(B)           Черный узел
//       /    \          
//      30(R) 70(B)      Красный узел
//     / \    / \
//  20(B) 40(R) 60(B) 80(R)
//
// Свойства:
// - Корень (50) чёрный
// - Красные узлы (30, 40, 80) не соседствуют с красными родителями
// - Пути до листьев имеют одинаковую чёрную высоту (2)

Операции в красно-чёрном дереве

1. Поиск (Search)

public class RedBlackTree<T extends Comparable<T>> {
    private RedBlackNode<T> root;
    
    // Поиск использует стандартный BST алгоритм
    public RedBlackNode<T> search(T value) {
        return searchHelper(root, value);
    }
    
    private RedBlackNode<T> searchHelper(RedBlackNode<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; // Найдено
        }
    }
    
    // Временная сложность: O(log n) благодаря балансу
}

2. Вставка (Insertion)

public void insert(T value) {
    RedBlackNode<T> newNode = new RedBlackNode<>(value);
    
    if (root == null) {
        root = newNode;
        root.color = Color.BLACK;
        return;
    }
    
    // Вставляем как в обычное BST
    RedBlackNode<T> current = root;
    RedBlackNode<T> parent = null;
    
    while (current != null) {
        parent = current;
        if (value.compareTo(current.value) < 0) {
            current = current.left;
        } else {
            current = current.right;
        }
    }
    
    newNode.parent = parent;
    if (value.compareTo(parent.value) < 0) {
        parent.left = newNode;
    } else {
        parent.right = newNode;
    }
    
    // Восстанавливаем свойства красно-чёрного дерева
    fixInsert(newNode);
}

private void fixInsert(RedBlackNode<T> node) {
    // Проверяем и исправляем нарушения свойств
    // Может потребоваться несколько операций ротации и перекраски
    while (node.parent != null && node.parent.color == Color.RED) {
        if (node.parent == node.parent.parent.left) {
            // Левое поддерево
            RedBlackNode<T> uncle = node.parent.parent.right;
            
            if (uncle != null && uncle.color == Color.RED) {
                // Случай 1: дядя красный - перекраска
                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; // Корень всегда чёрный
}

3. Ротации

// Левая ротация
private void rotateLeft(RedBlackNode<T> node) {
    //     x                y
    //    / \              / \
    //   a   y    -->     x   c
    //      / \          / \
    //     b   c        a   b
    
    RedBlackNode<T> y = node.right;
    node.right = y.left;
    
    if (y.left != null) {
        y.left.parent = node;
    }
    
    y.parent = node.parent;
    
    if (node.parent == null) {
        root = y;
    } else if (node == node.parent.left) {
        node.parent.left = y;
    } else {
        node.parent.right = y;
    }
    
    y.left = node;
    node.parent = y;
}

// Правая ротация
private void rotateRight(RedBlackNode<T> node) {
    //       y                x
    //      / \              / \
    //     x   c    -->     a   y
    //    / \                  / \
    //   a   b                b   c
    
    RedBlackNode<T> x = node.left;
    node.left = x.right;
    
    if (x.right != null) {
        x.right.parent = node;
    }
    
    x.parent = node.parent;
    
    if (node.parent == null) {
        root = x;
    } else if (node == node.parent.right) {
        node.parent.right = x;
    } else {
        node.parent.left = x;
    }
    
    x.right = node;
    node.parent = x;
}

Временная сложность

Использование в Java

// TreeMap использует красно-чёрные деревья
import java.util.TreeMap;

public class TreeMapExample {
    public static void main(String[] args) {
        // TreeMap внутри использует красно-чёрное дерево
        TreeMap<Integer, String> map = new TreeMap<>();
        
        map.put(5, "Five");
        map.put(3, "Three");
        map.put(7, "Seven");
        map.put(2, "Two");
        map.put(4, "Four");
        
        // Автоматически балансируется
        System.out.println(map); // {2=Two, 3=Three, 4=Four, 5=Five, 7=Seven}
        
        // Все операции O(log n)
        String value = map.get(3); // O(log n)
        map.remove(3);             // O(log n)
    }
}

// TreeSet также использует красно-чёрные деревья
import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>();
        set.add(50);
        set.add(30);
        set.add(70);
        set.add(20);
        set.add(80);
        
        System.out.println(set); // [20, 30, 50, 70, 80] - отсортировано
        System.out.println("Contains 30: " + set.contains(30)); // O(log n)
    }
}

Почему красно-чёрное дерево?

1. Гарантированная высота — всегда логарифмическая (макс. 2*log(n))
2. Быстрые операции — O(log n) для всех базовых операций
3. Меньше ротаций — чем AVL дерево, более эффективно для вставок
4. Балансировка автоматическая — не требует ручной реализации
5. Практичное использование — используется в TreeMap, TreeSet, HashMap (для длинных цепочек коллизий)

Key Takeaway

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