Determine a self-balanced binary tree height formula knowing its number of node

2
votes

I have been working on determining the height of a self-balanced binary tree knowing its number of nodes(N) and I came with the formula:

height = ceilling[log2(N+1)], where ceilling[x] is the smallest integer not less than x.

The thing is I can't find this formula on the internet and it seems pretty accurate.

  • Is there any case of self-balanced binary tree this formula would fail?

  • What would be the general formula to determine the height of the tree then?

1
algorithmbinary-tree

1 Answers

2
votes

There is a formula on Wikipedia's Self-balancing binary search tree article.

h >= ceilling(log2(n+1) - 1) >= floor(log2(n))

The minimum height is floor(log2(n)). It's worth noting, however, that

the simplest algorithms for BST item insertion may yield a tree with height n in rather common situations. For example, when the items are inserted in sorted key order, the tree degenerates into a linked list with n nodes.

So, your formula is not far off from the "good approximation" formula (just off by 1), but there can be a pretty wide range between n and log2(n) to take into account.