Встречается на собеседованиях • сегодня

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

Красно-черное дерево — это самобалансирующееся бинарное дерево поиска, где каждый узел имеет цвет (красный или черный). Оно гарантирует логарифмическую сложность операций (вставка, удаление, поиск) за счет соблюдения правил:

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

Пример вставки в Java (упрощенно):

java

class Node {
    int data;
    Node left, right, parent;
    boolean color; // true - красный, false - черный
}

void insertFixup(Node z) {
    while (z.parent.color == RED) {
        if (z.parent == z.parent.parent.left) {
            Node y = z.parent.parent.right;
            if (y.color == RED) {
                z.parent.color = BLACK;
                y.color = BLACK;
                z.parent.parent.color = RED;
                z = z.parent.parent;
            } else {
                if (z == z.parent.right) {
                    z = z.parent;
                    leftRotate(z);
                }
                z.parent.color = BLACK;
                z.parent.parent.color = RED;
                rightRotate(z.parent.parent);
            }
        }
        // аналогично для правого случая
    }
    root.color = BLACK;
}

Софи собрала все вопросы. Тренируйся и получай
офферы быстрее!

Попробовать бесплатно

Следующий вопрос

Это единственный вопрос по вашему фильтру

как отвечать на вопрос

пример собеседования

фреймворки на собеседовании

типичные вопросы junior

интервью вопросы и ответы