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

Question

Вокруг красно-черных деревьев много вопросов, но никто из них не отвечает, как они работают. Почему это называется красно-черным? Как это поддерживает дерево сбалансированным (таким образом увеличивая производительность по сравнению с несбалансированным нормальным бинарным деревом поиска)? Я просто ищу обзор того, как и почему это работает.

Answer 1

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

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

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

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

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

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

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

Answer 2

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

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

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

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

Ура!