在树中的节点的扇出被定义为儿童的节点的数量。 树的扇出被定义为最大扇出树中的任何节点的。 假设树T有n个节点和一个风扇,输出F> 1.什么是T的最小可能的高度?
我不知道如何开始这个问题。 我解决这是找到可以为T在高度h和扇输出F> 1的条件我得到的节点的最大数目的第一部分(F ^(H + 1)-1)/(F-1) 。 我想,你可以用它来解决上面的问题。 可有人请点我在正确的方向?
谢谢!
在树中的节点的扇出被定义为儿童的节点的数量。 树的扇出被定义为最大扇出树中的任何节点的。 假设树T有n个节点和一个风扇,输出F> 1.什么是T的最小可能的高度?
我不知道如何开始这个问题。 我解决这是找到可以为T在高度h和扇输出F> 1的条件我得到的节点的最大数目的第一部分(F ^(H + 1)-1)/(F-1) 。 我想,你可以用它来解决上面的问题。 可有人请点我在正确的方向?
谢谢!
我会被扭转,并试图找到您可以在树与给定的高度和扇出包节点的最大数量解决这个问题T_max(h,f)
这样,每隔一个树T(h,f)
被保证有尽可能多,或小于节点T_max(h,f)
因此,如果你找到了这样T_max(h,f)
即
total_nodes( T_max(h,f) ) > n > total_nodes( T_max(h-1,f))
h
将被保证是与树的最小高度n
节点和f
扇出。
为了找到这样的树,你需要最大限度地在树的每一层节点的数量。 换句话说,这样的树的每个节点都需要有扇出的f
,毫不逊色。 因此,你开始插入一个树节点,一次一个水平。 后的A层是满的,你开始增加另一层。 之后n
节点插入这样一棵树,你停下来检查树的高度。 这将是你正在寻找的最小高度。
或者,你可以做一个计算,而不是:
nodes_in_level(1) = 1
nodes_in_level(2) = f
nodes_in_level(3) = f * f
...
nodes_in_level(x) = f ^ (x - 1)
这是一个标准几何级数 。 随高度的给定树的最大节点x
和扇出f
因此是这样的几何级数的总和与它不应该太麻烦找出最小的x
,为此,节点的数目大于n
。