根据树的大小来计算插入水平

Question

如果我的图形结构看起来像以下

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 

如何从图/树的大小（现有节点的数量）计算n？

Answer 1

如果高度为h，则存在的节点数

给出

1 2 3 ... h = h（h 1）/2

这意味着一个简单的选择是获取节点n的总数并进行简单的二进制搜索以找到h的正确值，以使h（h 1）/2 = n。

另外，由于n = h（h 1）/2，您可以注意到

n = h（h 1）/2

2n = h ² h

0 = h ² h -2n

现在，您拥有一个二次方程式（在H中），您可以求解以直接恢复H的值。解决方案是

h =（-1＆plusmn;＆radic;（1 8n））/2

如果您拿到负分支，您将获得一个负数，因此您应该占据正分支并计算

（-1 ＆radic;（1 8n））/2

直接恢复H。

希望这会有所帮助！