如何找到最小可能的树高？ [英] How to find minimum possible height of tree?

问题描述

树中的节点的扇出被定义为节点具有的子节点数。树的扇出被定义为树中任何节点的最大扇出。假设树T有n个节点，扇出f> 1. T的最小可能高度是多少？

我不知道如何开始这个问题。我解决了第一部分，它是根据高度h和扇出f> 1找到可以是T的最大节点数。我得到（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 。因此，您开始在树中插入节点，一次一个级别。图层已满后，您开始添加另一层。在 n 节点插入这样一棵树后，你停止并检查树的高度。这将是您寻找的最小高度。

或者，您可以进行计算：

  nodes_in_level（1）= 1 
 nodes_in_level（2）= f 
 nodes_in_level（3）= f * f 
 ... 
 nodes_in_level x）= f ^（x-1）
  

这是一个标准 rel =nofollow> ///.wikipedia.org/wiki/Geometric_progression因此，具有高度 x 和扇出 f 的给定树的最大节点是这样的几何级数和找出最小的 x ，节点数大于 n 。

The fan-out of a node in a tree is defined to be the number of children the node has. The fan-out of a tree is defined to be the maximum fan-out of any node in the tree. Assume tree T has n nodes and a fan-out f > 1. What is the minimum possible height of T?

I have no idea how to begin this problem. I solved the first part which is to find the maximum number of nodes that can be T in terms of height h and fan-out f > 1. I got (f^(h+1) -1)/(f-1). I'm thinking you can use this to solve for the question above. Can someone please point me in the correct direction?

Thank you!

解决方案

I would approach this problem by turning it around and trying to find the maximum number of nodes you can pack in a tree with a given height and fan-out T_max(h,f). This way, every other tree T(h,f) is guaranteed to have as much, or less nodes than T_max(h,f). Therefore, if you find such T_max(h,f), that

total_nodes( T_max(h,f) ) > n > total_nodes( T_max(h-1,f))

h will be guaranteed to be the minimum height of a tree with n nodes and f fan-out.

In order to find such a tree, you need to maximize the number of nodes in every layer of a tree. In other words, every node of such a tree needs to have fan-out of f, no less. Therefore you start inserting nodes in a tree, one level at a time. After a layer is full, you start adding another layer. After n nodes are inserted in such a tree, you stop and check the height of the tree. This will be the minimal height you are looking for.

Or, you can do a calculation instead:

nodes_in_level(1) = 1
nodes_in_level(2) = f
nodes_in_level(3) = f * f
...
nodes_in_level(x) = f ^ (x - 1)

This is a standard geometric progression. The maximum nodes of a given tree with height x and fan-out f is therefore the sum of such geometric progression and it shouldn't be too much trouble to figure out the smallest x, for which the number of nodes is greater than n.

这篇关于如何找到最小可能的树高？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！