Есть ли нетривиальный способ посетить каждый красный узел в красном черном дереве?

Question

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

Answer 1

Не существует свойства общего красно-черного дерева, которое позволяло бы вам считать красные узлы за исключением времени O (n). Если по какой-то причине количество красных узлов чрезвычайно важно, вы можете сделать подсчет свойством самого дерева и отслеживать манипуляции во время вставки / удаления перебалансировки.

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