Красно-Чёрное ДеревоRed-Black Tree

Каждый узел красно-чёрного дерева помечен цветом — красным или чёрным (nil-листья считаются чёрными). Инвариант состоит из четырёх правил: (1) корень чёрный; (2) у красного узла оба ребёнка чёрные (красные узлы не могут идти подряд); (3) каждый путь от узла до любого его nil-потомка содержит одинаковое число чёрных узлов (это число называется чёрной высотой); (4) все листья (nil) чёрные. Из правил 2 и 3 математически следует, что высота дерева не может превысить 2·log₂(n+1) — самый длинный возможный путь (чередование красный-чёрный) не более чем вдвое длиннее самого короткого (все чёрные).Every node in a red-black tree is marked red or black (nil leaves count as black). The invariant has four rules: (1) the root is black; (2) a red node's children are both black (red nodes can't run consecutively); (3) every path from a node to any of its nil descendants contains the same number of black nodes (this count is called the black-height); (4) all leaves (nil) are black. Rules 2 and 3 together mathematically imply the tree's height can't exceed 2·log₂(n+1) — the longest possible path (alternating red-black) is at most twice as long as the shortest (all black).

После вставки новый узел всегда красный (это не нарушает правило 3 — новый узел не добавляет чёрных узлов на путь). Единственное возможное нарушение — правило 2: красный родитель с красным ребёнком. Исправление зависит от цвета "дяди" (брата родителя): если дядя красный — достаточно перекрасить родителя, дядю в чёрный и деда в красный, и продолжить проверку выше (recolor, O(1) работы за уровень, но может пройти до корня); если дядя чёрный или отсутствует — нужна одна или две ротации (в зависимости от того, "прямая" линия дед-родитель-узел или "зигзаг"), после чего нарушение устраняется полностью за один проход, без дальнейшего распространения вверх.After insertion, a new node is always red (this doesn't violate rule 3 — a new node adds no black nodes to the path). The only possible violation is rule 2: a red parent with a red child. The fix depends on the "uncle's" (the parent's sibling's) color: if the uncle is red, it's enough to recolor the parent and uncle to black and the grandparent to red, then keep checking upward (a recolor, O(1) work per level, but may propagate up to the root); if the uncle is black or absent, one or two rotations are needed (depending on whether the grandparent-parent-node line is "straight" or a "zigzag"), after which the violation is fully resolved in one pass, with no further upward propagation.

enum class Color { RED, BLACK };
struct Node {
    int key; Color color = Color::RED;
    Node *left = nullptr, *right = nullptr, *parent = nullptr;
};

// после обычной BST-вставки нового красного узла z:// after a normal BST insertion of a new red node z:
void fix_insert(Node* z) {
    while (z->parent && z->parent->color == Color::RED) {
        Node* gp = z->parent->parent;
        bool parent_is_left = (z->parent == gp->left);
        Node* uncle = parent_is_left ? gp->right : gp->left;

        if (uncle && uncle->color == Color::RED) {           // случай 1: дядя красный// case 1: red uncle
            z->parent->color = Color::BLACK;
            uncle->color = Color::BLACK;
            gp->color = Color::RED;
            z = gp;                                       // нарушение могло уйти выше// violation may have moved up
        } else {                                          // случай 2: дядя чёрный/nil — ротация(и)// case 2: black/nil uncle — rotation(s)
            if (parent_is_left && z == z->parent->right) { z = z->parent; rotate_left(z); }
            if (!parent_is_left && z == z->parent->left)  { z = z->parent; rotate_right(z); }
            z->parent->color = Color::BLACK;
            gp->color = Color::RED;
            parent_is_left ? rotate_right(gp) : rotate_left(gp);
            break;                                     // исправлено окончательно, выше не распространяется// fully fixed, doesn't propagate further
        }
    }
    root->color = Color::BLACK;                           // правило 1 — корень всегда чёрный// rule 1 — the root is always black
}

Вставка проигрывается автоматически: спуск, создание нового красного узла, и если правило "красный не может быть ребёнком красного" нарушено — либо перекраска (голубая вспышка), либо ротация (оранжевая вспышка). Пресеты специально показывают оба случая на одном и том же дереве.Insertion auto-plays: descend, create a new red node, and if "a red node can't be a red node's child" is violated — either a recolor (blue flash) or a rotation (orange flash). The presets specifically show both cases on the same tree.

При вставке AVL иногда требует ротацию, но она всегда одна (после которой высота полностью восстановлена); красно-чёрное дерево может выполнить O(log n) перекрасок подряд, но ротаций требуется не больше двух. Перекраска — это просто запись в поле цвета, на порядок дешевле ротации (которая меняет несколько указателей и, в кэш-недружественных языках, требует более сложной синхронизации при конкурентном доступе). Поэтому C++ std::map, std::set, Java TreeMap/TreeSet и планировщик Linux CFS выбрали красно-чёрные деревья: рабочая нагрузка этих структур — постоянный поток вставок и удалений, где сумма по всем перекраскам обходится дешевле, чем сумма по всем ротациям AVL. AVL остаётся предпочтительным там, где структура строится один раз (или редко) и затем в основном читается — например, статический индекс, построенный из отсортированного набора данных при загрузке.On insertion, AVL sometimes needs a rotation, but always exactly one (after which the height is fully restored); a red-black tree may perform O(log n) recolors in a row, but never more than two rotations. A recolor is just writing a color field, an order of magnitude cheaper than a rotation (which changes several pointers and, in cache-unfriendly languages, requires more complex synchronization under concurrent access). That's why C++ std::map, std::set, Java's TreeMap/TreeSet, and the Linux CFS scheduler chose red-black trees: these structures' workload is a constant stream of insertions and deletions, where the sum over all recolors is cheaper than the sum over all AVL rotations would be. AVL remains preferable where the structure is built once (or rarely) and then mostly read — e.g. a static index built from a sorted dataset at load time.