问题描述:

How can I calculate the ideal height of a tree structure?

When I have this tree

I know the height is 4.

There's a formula that says that the ideal height of a tree is 2 ^ height - 1 but that doesn't make sense to me (since it would be 15).

Can someone please explain?

网友答案:

Well, first of all, that formula applies only to binary trees. Second, the ideal number of nodes in the tree will be 2^height-1. For a saturated binary tree of height 4, the number of nodes will be 15.

网友答案:

That formula is for the maximum number of nodes that can be included in a binary tree of that height. Assuming you want the tree to be as shallow as possible, you want to know the minimum height of such a tree given the number of nodes. So you simply invert:

nodes = 2^height - 1

to get

height = log2(nodes + 1)

rounded up.

网友答案:

Height of the tree is the maximum height among all the nodes in the tree. Now say you have a tree

                                         1
                                       /   \
                                       2    3
                                      /  \  / \
                                      4  5  6  7

the height of the tree is 3(since all path lengths are same so lets say 1-2-5 is maximum) now as there are three levels so no of node at each level

                                          1         =2^0
                                       /   \   
                                       2    3      =2^1
                                      /  \  / \
                                      4  5  6  7    =2^2

total =2^0 +2^1+2^2= clearly its a gp with sum 2^3-1 ,hence the number of nodes =2^height-1 if you talk about levels(as they start from 0) no of nodes= 2^(level+1)-1

相关阅读:
Top