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

Для поиска и обхода это то же самое, что и любое двоичное дерево.

Для вставок и удалений применяются более сложные алгоритмы, которые направлены на то, чтобы дерево не было слишком несбалансированным. Это гарантирует, что все операции с одним элементом всегда будут выполняться в худшем случае за время O(log n), тогда как в простом двоичном дереве двоичное дерево может стать настолько несбалансированным, что фактически становится связанным списком, что дает производительность O(n) в худшем случае для каждой операции с одним элементом.

Основная идея красно-черного дерева состоит в том, чтобы имитировать B-дерево с 3 ключами и 4 потомками на узел. B-деревья (или разновидности, такие как деревья B+) в основном используются для индексов базы данных и для данных, хранящихся на жестком диске.

Каждый узел бинарного дерева имеет «цвет» — красный или черный. Каждый черный узел, по аналогии с B-деревом, является корнем поддерева для поддерева, которое соответствует этому узлу B-дерева. Если у этого узла есть красные дочерние элементы, они также считаются частью одного и того же узла B-дерева. Таким образом, возможно (хотя это и не делается на практике) преобразовать красно-черное дерево в B-дерево и обратно с сохранением (большинства) структуры. Единственная возможная аномалия состоит в том, что, когда узел B-дерева имеет два ключа и трех дочерних элементов, у вас есть выбор, какой ключ использовать в черном узле в эквивалентном красно-черном дереве.

Например, в красно-черных деревьях каждая линия от корня до листа имеет одинаковое количество черных узлов. Это правило получено из правила B-дерева, согласно которому все конечные узлы находятся на одной глубине.

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

Для получения более подробной информации перейдите по ссылке на Википедию, которую MigDus уже предоставил.

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

[Я не верю, что статья в Википедии ясно объясняет этот момент.]

Обычные правила для красно-черных деревьев требуют, чтобы красная вершина никогда не указывала на другую красную вершину. Это означает, что возможные расположения вершин для любого поддерева с черной вершиной (bbb, bbr, rbb, rbr -- для [левого потомка][корня][правого потомка]) соответствуют 234 деревьям.

Поиск красно-черного дерева аналогичен поиску обычного бинарного дерева. Вставка и удаление аналогичны, за исключением того, что в какой-то момент может потребоваться «исправленное» вращение для сохранения красно-черного инварианта.

Ваше здоровье!