Динамично установленное значение входа файла [дубликат]

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

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

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

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

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

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

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