Как работает красно-черное дерево?
На мой взгляд, каталоги не должны считаться объектами вашего файла makefile, как в техническом, так и в дизайнерском смысле. Вы должны создать файлы , и если для создания файла нужен новый каталог, тогда спокойно создайте каталог в правиле для соответствующего файла.
re, ориентируясь на обычный или «узорный» файл, просто используйте внутреннюю переменную make $(@D), что означает «каталог, в котором находится текущая цель» (cmp. с $@ для цели). Например,
$(OUT_O_DIR)/%.o: %.cpp
@mkdir -p $(@D)
@$(CC) -c $< -o $@
title: $(OBJS)
Затем вы делаете то же самое: создайте каталоги для всех $(OBJS), но вы сделаете это менее сложным способом.
такая же политика (файлы - это цели, каталоги никогда не используются) используется в различных приложениях. Например, система управления версиями git не хранит каталоги.
Примечание. Если вы собираетесь использовать его, может быть полезно ввести удобную переменную и использовать make .
dir_guard=@mkdir -p $(@D)
$(OUT_O_DIR)/%.o: %.cpp
$(dir_guard)
@$(CC) -c $< -o $@
$(OUT_O_DIR_DEBUG)/%.o: %.cpp
$(dir_guard)
@$(CC) -g -c $< -o $@
title: $(OBJS)
1 ответ
Для поиска и обхода он такой же, как любое двоичное дерево.
Для вставок и удалений применяются более сложные алгоритмы, целью которых является обеспечение того, чтобы дерево не было слишком несбалансированным. Это гарантирует, что все одноэлементные операции всегда будут выполняться в наихудшее время O (log n), тогда как в простом двоичном дереве бинарное дерево может стать настолько несбалансированным, что фактически является связанным списком, что дает O (n) производительность в худшем случае для каждая единичная операция.
Основная идея красно-черного дерева состоит в том, чтобы имитировать B-дерево с 3 ключами и 4 дочерними узлами на узел. B-деревья (или варианты, такие как B + деревья) в основном используются для индексов базы данных и для данных, хранящихся на жестком диске.
Каждый узел двоичного дерева имеет «цвет» - красный или черный. Каждый черный узел, по аналогии с B-деревом, является корнем поддерева для поддерева, которое вписывается в этот узел B-дерева. Если у этого узла есть красные дочерние элементы, они также считаются частью того же узла B-дерева. Таким образом, возможно (хотя и не сделано на практике) преобразовать красно-черное дерево в B-дерево и обратно с сохранением (большей части) структуры. Единственно возможная аномалия заключается в том, что, когда у узла B-дерева есть два ключа и три дочерних элемента, у вас есть выбор, какой из ключей следует поместить в черный узел в эквивалентном красно-черном дереве.
Например, для красно-черных деревьев каждая линия от корня до листа имеет одинаковое количество черных узлов. Это правило вытекает из правила B-дерева, согласно которому все конечные узлы находятся на одной глубине.
Несмотря на то, что это основная идея, из которой получены красно-черные деревья, алгоритмы, используемые на практике для вставок и удалений, модифицированы, чтобы обеспечить соблюдение всех правил B-дерева (может быть небольшое исключение - я забыл) во время обновлений , но приспособлены для бинарного дерева. Это означает, что выполнение вставки или удаления красно-черного дерева может привести к иной структуре результата, чем это можно ожидать по сравнению со вставкой или удалением B-дерева.
Для получения более подробной информации перейдите по ссылке Википедии , которую уже предоставил MigDus.