Блог

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

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

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

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

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

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

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

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

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

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

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

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

Приветствия!