Алгоритмы

Расскажите про красно-черное дерево.

Красно-черное дерево - это сбалансированное двоичное дерево поиска, в котором каждый узел имеет дополнительное свойство цвета: красный или черный. Это свойство цвета используется для поддержания баланса дерева при вставке и удалении узлов.

Сложность поиска, вставки и удаления – O(log(n)).

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

Красно-черное дерево обеспечивает балансировку операций вставки, удаления и поиска, что позволяет достичь логарифмической сложности для этих операций в среднем случае.

Пример реализации красно-черного дерева на языке Java:
class Node {
    int value;
    Node parent;
    Node left;
    Node right;
    int color;

    public Node(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
        this.parent = null;
        this.color = 1; // При создании узел считается красным
    }
}

public class RedBlackTree {
    private Node root;
    private Node TNULL;

    // Конструктор
    public RedBlackTree() {
        TNULL = new Node(0);
        TNULL.color = 0;
        TNULL.left = null;
        TNULL.right = null;
        root = TNULL;
    }

    // Вставка узла
    private void insert(int key) {
        Node node = new Node(key);
        node.parent = null;
        node.value = key;
        node.left = TNULL;
        node.right = TNULL;
        node.color = 1; // Вставляемый узел всегда красный

        Node y = null;
        Node x = this.root;

        while (x != TNULL) {
            y = x;
            if (node.value < x.value) {
                x = x.left;
            } else {
                x = x.right;
            }
        }

        node.parent = y;
        if (y == null) {
            root = node;
        } else if (node.value < y.value) {
            y.left = node;
        } else {
            y.right = node;
        }

        if (node.parent == null) {
            node.color = 0; // Если вставленный узел является корнем дерева, он должен быть черным
            return;
        }

        if (node.parent.parent == null) {
            return;
        }

        fixInsert(node);
    }

    // Балансировка после вставки
    private void fixInsert(Node k) {
        Node u;
        while (k.parent.color == 1) {
            if (k.parent == k.parent.parent.right) {
                u = k.parent.parent.left;
                if (u.color == 1) {
                    u.color = 0;
                    k.parent.color = 0;
                    k.parent.parent.color = 1;
                    k = k.parent.parent;
                } else {
                    if (k == k.parent.left) {
                        k = k.parent;
                        rightRotate(k);
                    }
                    k.parent.color = 0;
                    k.parent.parent.color = 1;
                    leftRotate(k.parent.parent);
                }
            } else {
                u = k.parent.parent.right;

                if (u.color == 1) {
                    u.color = 0;
                    k.parent.color = 0;
                    k.parent.parent.color = 1;
                    k = k.parent.parent;
                } else {
                    if (k == k.parent.right) {
                        k = k.parent;
                        leftRotate(k);
                    }
                    k.parent.color = 0;
                    k.parent.parent.color = 1;
                    rightRotate(k.parent.parent);
                }
            }
            if (k == root) {
                break;
            }
        }
        root.color = 0;
    }

    // Левый поворот
    private void leftRotate(Node x) {
        Node y = x.right;
        x.right = y.left;
        if (y.left != TNULL) {
            y.left.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == null) {
            this.root = y;
        } else if (x == x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }
        y.left = x;
        x.parent = y;
    }

    // Правый поворот
    private void rightRotate(Node x) {
        Node y = x.left;
        x.left = y.right;
        if (y.right != TNULL) {
            y.right.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == null) {
            this.root = y;
        } else if (x == x.parent.right) {
            x.parent.right = y;
        } else {
            x.parent.left = y;
        }
        y.right = x;
        x.parent = y;
    }

    // Поиск узла с заданным значением
    private Node searchTree(int k, Node node) {
        if (node == TNULL || k == node.value) {
            return node;
        }

        if (k < node.value) {
            return searchTree(k, node.left);
        }
        return searchTree(k, node.right);
    }

    // Поиск узла с заданным значением
    public boolean search(int k) {
        return searchTree(k, this.root) != TNULL;
    }

    public void inorder() {
        inorderTree(this.root);
    }

    private void inorderTree(Node node) {
        if (node != TNULL) {
            inorderTree(node.left);
            System.out.print(node.value + " ");
            inorderTree(node.right);
        }
    }

    public static void main(String[] args) {
        RedBlackTree tree = new RedBlackTree();

        tree.insert(55);
        tree.insert(40);
        tree.insert(65);
        tree.insert(60);
        tree.insert(75);
        tree.insert(57);

        tree.inorder(); // Выводит 40 55 57 60 65 75
    }
}
В данном примере мы реализуем красно-черное дерево, используя классы Node и RedBlackTree. Мы выполняем вставку нескольких элементов и выводим их в порядке возрастания. Красно-черное дерево автоматически балансируется при вставке новых элементов.

Красно-черное дерево обеспечивает эффективные операции вставки, удаления и поиска элементов. Оно широко применяется в различных областях, таких как базы данных, сортировка и оптимизация алгоритмов.