Time analysis of binary search tree operations
I read about binary search trees that if it is a complete tree (all nodes except leaf nodes have two children) having n nodes, then no path can have more than 1+log n nodes.
Here is the calculation I did... can you show me where did I go wrong....
the first level of bst has only one node(i.e. the root)-->2^0
the second level have 2 nodes(the children of root)---->2^1
the third level has 2^3=8 nodes
.
.
the (x+1)th level has 2^x nodes
so开发者_StackOverflow中文版 the total number of nodes =n = 2^0 +2^1 +2^2 +...+2^x = 2^(x+1)-1
so, x=log(n+1)-1
now as it is a 'complete' tree...the longest path(which has most no of nodes)=x
and so the nodes experienced in this path is x+1= log(n+1)
Then how did the number 1+log n come up...?
Shorter answer: the number x
of levels in a complete (or perfect) binary tree is log2(n+1)
, where n
is the number of nodes (alternatively, n = 2^(x-1)
). A tree with x
levels has height x-1
. The longest path from the root to any node contains x = log2(n+1)
nodes (and x-1
edges).
Now because n+1
is a power of 2, we have that log2(n+1) = 1 + floor(log2(n))
. In other words, 1 + log2(n)
is a correct upper-bound, but it is never an integer.
It is unclear to me whether the x
in your computation refers to the height or the number of levels.
精彩评论