Если у меня есть структура графа, который выглядит следующим образомРасчет уровня вставки на основе размера дерева
a level-1
b c level-2
c d e level-3
e f g h level-4
...... level-n
a points to b and c
b points to c and d
c points to d and e
and so on
, как можно рассчитать п от размера (количество существующих узлов) из граф/дерево?
Количество узлов, присутствующих, если высота ч дается
1 + 2 + 3 + ... + Н = Н (Н + 1)/2
Эта означает, что одним простым вариантом было бы взять общее число узлов n и выполнить простой двоичный поиск, чтобы найти правильное значение h так, чтобы h (h + 1)/2 = n.
В качестве альтернативы, так как п = Н (Н + 1)/2, можно отметить, что
п = Н (Н + 1)/2
2n = ч + Н
0 = ч + ч - 2n
Теперь у вас есть квадратное уравнение (в час), что вы можете с олве, чтобы сразу вернуть значение h. Решение
ч = (-1 & plusmn; √ (1 + 8п))/2
Если взять минус ветку, вы получите обратно отрицательное число, так что вы должны взять на себя положительную ветвь и вычислить
(-1 + √ (1 + 8n))/2
непосредственно получить обратно ч.
Надеюсь, это поможет!
это было потрясающе! благодаря – nightograph
Я удалил теги языка, поскольку ни один из них не имеет отношения к вашему вопросу. Если в конце концов кто-то из них подходит, укажите, как мы можем предоставить целевую информацию. –
Вы ищете высоту? – turbo
@ turbo да, я думаю, вы можете сказать, что – nightograph