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

Question

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

Тип вопроса: Архитектура Вероятность: 23% Категория: AQA / Automation

Ответ

Красно-черное дерево (Red-Black Tree) — это тип самобалансирующегося бинарного дерева поиска (BST). Балансировка обеспечивается за счет соблюдения набора правил, касающихся цвета каждого узла («красный» или «черный»), что гарантирует, что дерево остается примерно сбалансированным, а основные операции (вставка, удаление, поиск) выполняются за O(log n) в худшем случае.

Пять обязательных свойств:

Каждый узел либо красный, либо черный.
Корень дерева всегда черный.
Все листья (NIL-узлы) считаются черными.
Правило красного узла: У красного узла оба дочерних узла обязательно черные.
Правило черной высоты: Для каждого узла все простые пути от него до любых листьев-потомков содержат одинаковое количество черных узлов (черная высота).

Эти свойства гарантируют, что самый длинный путь (чередуя красные и черные узлы) не более чем в два раза длиннее самого короткого пути (только черные узлы).

Пример структуры узла на Java:

class RedBlackNode<K extends Comparable<K>, V> {
    K key;
    V value;
    RedBlackNode<K, V> left, right, parent;
    boolean isRed; // true - красный, false - черный

    RedBlackNode(K key, V value) {
        this.key = key;
        this.value = value;
        this.isRed = true; // Новый узел всегда красный
    }
}

Где используется: В реализациях важных структур данных, требующих гарантированного логарифмического времени выполнения, например:

java.util.TreeMap и java.util.TreeSet в Java.
std::map и std::set в C++ (в большинстве реализаций).
Ассоциативные массивы в различных языках.

Ответ 18+ 🔞

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

Вот эти железобетонные правила, которые нельзя нарушать:

Узел — не хамелеон. Или красный, или чёрный. Третьего не дано.
Корень — всегда, блядь, чёрный. Как ночь. Это аксиома.
Все листья (эти NIL-узлы, пустышки) — тоже считаются чёрными. Просто договорились так.
Правило красного узла (самое жёсткое): Если узел красный — его дети обязаны быть чёрными. Никаких двух красных подряд! Иначе пиздец, баланс нарушен.
Правило чёрной высоты (самое хитрое): От любого узла до любого листа-потомка должно быть одинаковое количество чёрных узлов на пути. Это и есть чёрная высота. Благодаря этому, самый длинный путь (где красные и чёрные чередуются) не будет больше, чем в два раза, длиннее самого короткого (где одни чёрные). Вот и весь секрет балансировки, ёпта!

Вот как это примерно выглядит в коде на Java, смотри:

class RedBlackNode<K extends Comparable<K>, V> {
    K key;
    V value;
    RedBlackNode<K, V> left, right, parent;
    boolean isRed; // true - красный, false - черный

    RedBlackNode(K key, V value) {
        this.key = key;
        this.value = value;
        this.isRed = true; // Новый узел всегда красный, потом разберёмся
    }
}

Видишь? Новый узел всегда лезет красненьким, наглец. А потом, в процессе вставки, дерево его начинает вертеть и перекрашивать, чтобы правила не поехали. Иногда такие кульбиты вытворяет — закачаешься!

А где эту хуйню применяют? Да везде, где нужна скорость и надёжность! Например:

java.util.TreeMap и java.util.TreeSet в Java — там внутри именно оно, хитрая жопа.
std::map и std::set в C++ — в большинстве библиотек тоже на нём сидят.
Куча других ассоциативных массивов в разных языках. Короче, вещь серьёзная, хоть и выглядит как ёлка с раскраской.