Ответ
Красно-черное дерево — это самобалансирующееся бинарное дерево поиска, где каждый узел имеет дополнительный атрибут — цвет (красный или черный). Оно поддерживает баланс при вставке и удалении, гарантируя логарифмическую сложность операций.
Основные свойства:
- Каждый узел — либо красный, либо черный.
- Корень всегда черный.
- Все листья (NIL) — черные.
- У красного узла оба потомка черные.
- Пути от узла до любых листьев содержат одинаковое количество черных узлов.
Пример структуры узла:
class Node {
constructor(value, color = 'RED') {
this.value = value;
this.left = null;
this.right = null;
this.parent = null;
this.color = color;
}
}Балансировка достигается поворотами и перекрашиванием узлов при нарушениях свойств. Используется в реализациях TreeMap и TreeSet в Java, map и set в C++.
Ответ 18+ 🔞
Ну, слушай, вот есть такая штука — красно-черное дерево. Представь себе обычное бинарное дерево поиска, но с прикрученной, блядь, системой балансировки, чтобы оно не превращалось в кривую палку, на которую только бельё вешать. Каждый узел там, понимаешь, либо красный, либо чёрный, как на светофоре, только без жёлтого.
Основные правила, которые оно свято блюдёт, а иначе пиздец:
- Узел — либо красный, либо чёрный. Никаких полутонов, ёпта.
- Корень — всегда чёрный, как моя душа после дедлайна. Это аксиома.
- Все эти пустые листья (NIL) — тоже чёрные. Просто договорились так.
- Если узел красный — его детишки обязаны быть чёрными. Два красных подряд — это уже нарушение, как пьяный дебош в общежитии.
- А вот это самое хитрожопое правило: от любого узла до любого листа должно быть одинаковое количество чёрных узлов. Это чтобы все пути были примерно равны, и дерево не перекашивало на один бок.
Вот, смотри, как узел примерно выглядит в коде, чтоб ты понимал масштаб:
class Node {
constructor(value, color = 'RED') {
this.value = value;
this.left = null;
this.right = null;
this.parent = null;
this.color = color;
}
}А балансируют его, когда что-то вставляют или удаляют, с помощью поворотов и перекрашиваний. Представь, ты вставил узел — бац, правило №4 нарушилось, два красных рядом. Дерево такое: «Опа, щас всё починю!» — делает поворот, перекрашивает, и опять красота. Вся магия в этих операциях, они и не дают ему развалиться.
Используется эта конструкция, между прочим, в серьёзных местах — в TreeMap в Java, в map и set в C++. Там, где надёжность и скорость нужны, а не какой-нибудь костыль на один раз.