Ответ
Красно-чёрное дерево — это самобалансирующееся бинарное дерево поиска (BST), где каждый узел имеет дополнительный бит цвета (красный или чёрный). Оно гарантирует, что дерево остаётся приблизительно сбалансированным, обеспечивая время выполнения основных операций O(log n) в худшем случае.
Пять строгих свойств:
- Каждый узел — красный или чёрный.
- Корень всегда чёрный.
- Все листья (NIL-узлы) — чёрные.
- У красного узла оба потомка чёрные (красные узлы не могут быть родителями красных узлов).
- Для каждого узла все простые пути от него до листьев-потомков содержат одинаковое количество чёрных узлов (чёрная высота).
Зачем нужно? Эти свойства обеспечивают, что самый длинный путь (чередуя красные и чёрные узлы) не более чем в два раза длиннее самого короткого (только чёрные узлы). Это поддерживает логарифмическую высоту.
Пример структуры узла на Java:
class RBNode<K extends Comparable<K>, V> {
K key;
V value;
RBNode<K, V> left, right, parent;
boolean color; // Например, true = RED, false = BLACK
RBNode(K key, V value) {
this.key = key;
this.value = value;
this.color = Color.RED; // Новые узлы обычно красные
}
}Основные операции (вставка, удаление) требуют перекрашивания и поворотов (левых/правых) для восстановления свойств после нарушения.
Применение: Реализация ассоциативных массивов (например, TreeMap в Java), планировщики в ядрах ОС.
Ответ 18+ 🔞
Да ты посмотри, какая хитрая хуйня придумана, чтобы дерево не превращалось в вырожденную херовину, которая тормозит как чёрт знает что! Красно-чёрное дерево, блядь — это как обычное бинарное дерево поиска, но с прикрученным сверху матанчиком в виде цвета у каждого узла. Суть проста: мы хотим, чтобы операции вставки, удаления и поиска всегда работали за O(log n), даже если кто-то специально пытается запихнуть данные в самом пиздецовом порядке.
Вот пять железных правил, которые нельзя нарушать, иначе всё пиздец:
- Узел либо красный, либо чёрный — третьего не дано, как говорится.
- Корень — всегда чёрный папа, без вариантов. Это аксиома, блядь.
- Все эти пустые листья (NIL-узлы) — тоже считаются чёрными, чтоб не путаться.
- Если узел красный — то его детишки обязаны быть чёрными. Никаких красных семей подряд, иначе баланс нахуй слетит!
- А это самое жёсткое: от любого узла до каждого листа-потомка должно быть одинаковое количество чёрных узлов на пути. Это называется «чёрная высота», и она должна быть везде одинаковая, ёпта!
А нахуя это всё? А затем, что эти правила гарантируют, что дерево не перекосится в одну сторону. Самый длинный путь (где красные и чёрные чередуются) будет не больше, чем в два раза длиннее самого короткого (где одни чёрные). Вот и получается, что высота дерева — логарифмическая, а не линейная, как у ёбаной связанной списканы.
Вот как узел на Java может выглядеть, например:
class RBNode<K extends Comparable<K>, V> {
K key;
V value;
RBNode<K, V> left, right, parent;
boolean color; // Например, true = RED, false = BLACK
RBNode(K key, V value) {
this.key = key;
this.value = value;
this.color = Color.RED; // Новые узлы обычно красные
}
}Основные операции — вставка и удаление — это вообще отдельный цирк. Там после каждого такого действия может нарушиться какое-нибудь из пяти священных правил. И чтобы всё починить, приходится делать перекрашивания и повороты (влево-вправо) — это как джиу-джитсу для дерева, чтобы оно обратно в баланс встало.
Где эту хуйню применяют? Да везде, где нужна предсказуемая скорость! Например, TreeMap в Java — это оно и есть. Или в ядрах операционок планировщики задач на них строят. Короче, штука охуенно полезная, хоть и мозг набекрень ставит, когда её с нуля реализовывать пытаешься.