Есть много вопросов вокруг красно-черных деревьев, но никто из них не отвечает, как они работают. Почему он называется красно-черным? Как это держит дерево сбалансированным (таким образом увеличивая производительность над неуравновешенным обычным деревом двоичного поиска)? Я просто ищу общий обзор того, как и почему он работает.
Как работает красно-черное дерево?
Ответ 1
Для поисков и обходов он аналогичен любому двоичному дереву.
Для вставок и удалений применяются более сложные алгоритмы, которые направлены на то, чтобы дерево не было слишком неуравновешенным. Они гарантируют, что все операции с одним элементом всегда будут выполняться в наихудшем времени O (log n), тогда как в простом двоичном древе двоичное дерево может стать настолько неуравновешенным, что это эффективно связанный список, что дает O (n) наихудшую производительность для каждая операция с одним элементом.
Основная идея красно-черного дерева заключается в том, чтобы имитировать B-дерево с тремя клавишами и 4 детьми на node. B-деревья (или такие вариации, как деревья B +) в основном используются для индексов базы данных и для данных, хранящихся на жестком диске.
Каждое двоичное дерево node имеет "цвет" - красный или черный. Каждый черный node является в аналогии B-дерева корнем поддерева для поддерева, который помещается внутри этого B-дерева node. Если этот node имеет красных детей, они также считаются частью одного B-дерева node. Таким образом, возможно (хотя и не сделано на практике) преобразовать красно-черное дерево в B-дерево и обратно, сохранив (большинство) структуру. Единственная возможная аномалия заключается в том, что когда B-дерево node имеет две клавиши и три дочерних элемента, у вас есть выбор того, какой ключ находится в черном node в эквивалентном красно-черном дереве.
Например, с красно-черными деревьями каждая строка от корня до листа имеет одинаковое количество черных узлов. Это правило выводится из правила B-дерева, что все листовые узлы находятся на одной глубине.
Хотя это основная идея, из которой производятся красно-черные деревья, алгоритмы, используемые на практике для вставок и удалений, изменяются для обеспечения соблюдения всех правил B-дерева (возможно, небольшое исключение - я забываю) во время обновлений, но настроены для двоичной формы дерева. Это означает, что выполнение вставки или удаления красно-черного дерева может дать другую структуру для результата, чем вы ожидали бы от сравнения с вставкой или удалением B-дерева.
Подробнее см. ссылка Википедии, которую MigDus уже предоставил.
Ответ 2
Красно-черное дерево - это упорядоченное двоичное дерево, где каждая вершина окрашена в красный или черный цвет. Интуиция заключается в том, что красную вершину следует рассматривать как находящуюся на той же высоте, что и ее родительская (т.е. край к красной вершине считается "горизонтальным", а не "нисходящим" ).
[Я не верю, что запись в Википедии делает это ясно.]
Обычные правила для красно-черных деревьев требуют, чтобы красная вершина никогда не указывала на другую красную вершину. Это означает, что возможные вершинные расположения для любого поддерева, укорененного с черной вершиной (bbb, bbr, rbb, rbr - для [left child] [root] [right child]) соответствуют 234 деревьям.
Поиск красно-черного дерева - это то же самое, что и поиск обычного двоичного дерева. Вставка и удаление аналогичны, за исключением того, что в какой-то момент может потребоваться "исправление", чтобы сохранить красно-черный инвариант.
Ура!