-2
В a red-black tree с n узлами, каково максимальное количество красных узлов (при условии, что корень черный)?Максимальное количество красных узлов в красном черном дереве
Это O(n)?
A
ответ
0
Если у дерева есть n узлов, а корень черный, то есть n - 1 узлов слева и n - 1 = O(n), поэтому вы правы.
Если вы хотите точнее подсчитать/связать количество красных узлов в дереве, вам нужно знать топологию этого дерева.
Например, если дерево представляет собой полное двоичное дерево, в соответствии с определением красно-черного дерева, он может вообще не иметь красных узлов.
+0
@ Dukeling да, в моем первом предложении я написал, что максимум O (n) – pkacprzak
+0
В красно-черном дереве красный узел не может иметь красного ребенка, поэтому не может быть красных узлов «n-1» (кроме 'n <= 3'). – Dukeling
+0
@ Dukeling Да, конечно, но 'O (n)' не означает 'n - 1'. Я имею в виду, что каждое число меньше или равно 'n - 1' равно' O (n) '. – pkacprzak
O (n) является (или, по крайней мере, кажется,) скорее ленивым догадком. Покажите нам аргумент, который вы сделали, чтобы определить это. Немного визуализации (рисовать дерево, цвет узлов) должно помочь вам в этом. Вы можете застрять в какой-то момент, но для этого мы здесь, а не для вашего размышления. – Dukeling