平衡二叉树python [英] Balanced binary tree python

问题描述

# stack_depth is initialised to 0
def find_in_tree(node, find_condition, stack_depth):
    assert (stack_depth < max_stack_depth), 'Deeper than max depth'
    stack_depth += 1
    result = []
    if find_condition(node):
        result += [node]
    for child_node in node.children:
        result.extend(find_in_tree(child_node, find_condition, stack_depth))
    return result

我需要帮助来理解这段代码.我想回答的问题是

I need help understanding this piece of code. The question i want to answer is

上面的Python函数搜索平衡的二叉树的内容. 如果假定上限为1,000,000个节点，则应将max_stack_depth常量设置为什么?

The Python function above searches the contents of a balanced binary tree. If an upper limit of 1,000,000 nodes is assumed what should the max_stack_depth constant be set to?

据我了解，这是一个棘手的问题.如果考虑一下，每次在递归中调用find_in_tree()函数时，stack_depth都会增加.我们试图在树中找到一个特定的节点，因此最坏的情况是我们必须在找到树中的所有节点之前对其进行搜索.因此，max_stack_depth应该为1,000,000?

From what I understand, this is a trick question. If you think about it, stack_depth is incremented every time the find_in_tree() function is called in the recursion. And we are trying to find a particular node in the tree.So the worst case would be when we have to search through all the nodes in the tree before we find it. Hence, max_stack_depth should 1,000,000?

如果您查看 stack_depth 何时递增，那么每次访问节点时我们似乎都会递增.在我们的例子中，我们每次都访问每个节点.因为找到正确的节点后停止算法时没有返回条件.

If you look at when stack_depth increments then it looks like we will increment every time we access a node. And in our case we are accessing every single node every time. Because there is no return condition when stops the algorithm when the correct node is found.

有人可以尝试向我解释他们的思考过程吗?

Can someone please try to explain me their thought process.

推荐答案

您不必添加每层上节点的数量，而要添加它们.例如，前四层中的节点数是1+2+4+8=15，而不是1*2*4*8=64.

Instead of multiplying the number of nodes on each layer, you have to add them. For example, the number of nodes in the first four layers is 1+2+4+8=15, not 1*2*4*8=64.

                #                      1
      #                   #          + 2
  #       #           #       #      + 4
#   #   #   #       #   #   #   #    + 8 = 15

通常，前n层中的节点数为2**(n+1)-1.您可以使用对数来获取正确的幂并获得该数字的下限.如果您希望减少该数字，则还必须从功效中减去1.

In general, the number of nodes in the first n layers is 2**(n+1)-1. You can use logarithms to get the correct power and get the floor of that number. If you want fewer that that number, you would also have to subtract one from the power.

>>> math.floor(math.log(1000000, 2))
19
>>> sum(2**i for i in range(1, 20))
1048574

关于您的是的，每个节点的stack_depth都递增，但是您正在递增 local 变量.增量将携带到子节点(作为参数传递)，但不携带到兄弟节点，即，级别n的所有节点都将被stack_depth == n-1调用(假设它在第一级别以0开头).因此，max_stack_depth应该为19(如果从1开始则为20)，以访问树的前19个层中的〜1,000,000个节点.

Concerning your edit: Yes, stack_depth is incremented with each node, but you are incrementing a local variable. The increment will carry to the child nodes (passed as a parameter) but not to the siblings, i.e. all the nodes at level n will be called with stack_depth == n-1 (assuming it started as 0 on the first level). Thus, max_stack_depth should be 19 (or 20 if it starts with 1) to visit the ~1,000,000 nodes in the first 19 levels of the tree.

这篇关于平衡二叉树python的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！