Microsoft Interview Question Software Engineer / Developers
if N(d) is the minimum number of nodes for an AVL-tree of depth d, that then
N(d) = N(d - 1) + N(d - 2) + 1.
Thus, the N(d) are very similar to the Fibonacci numbers, and even slightly larger. How does this develop exactly? If we set N(-1) = 0, then we have N(0) = 1, N(1) = 2, N(2) = 4, N(3) = 7, N(4) = 12, N(5) = 20, N(6) = 33, N(7) = 54, N(8) = 88, N(9) = 143, N(10) = 231, ... . We see that these numbers grow fast! Actually, looking at them we get the strong feeling that they grow exponetially, even though they do not double every step.
How can one prove such a fact? In (almost) all such cases, one should use induction. For induction we need an induction hypothesis. The problem here is that we do not know exactly what we want to prove. If we just want to prove that the development is exponential, we can use an underestimate. It is easy to see that we have N(d + 2) > 2 * N(d). So, as an hypothesis we could use N(d) >= sqrt(2)^d. We must check the basis of the induction. This is ok, because sqrt(2)^0 = 1 <= N(0), and sqrt(2)^1 = sqrt(2) <= N(1). After that we must only check that indeed
N(d) = N(d - 1) + N(d - 2) + 1 >= sqrt(2)^{d - 1} + sqrt(2)^{d - 2} >= sqrt(2)^d
This is so, because 1 / sqrt(2) + 1 / 2 +-= 1.207 > 1.
In principle this is good enough. If, however, we want a more accurate estimate, then we can do the following which is a special case of an approach that works in general for estimating the exponential development of a recurrency relation. We assume that the development is as a^d, for the time being we forget about constant factors and additional terms. How big is a? Because the expeonential behavior dominates all other things, we should basically have a^d = a^{d - 1} + a^{d - 2}. Dividing left and right side by a^{d - 2} gives a quadratic equation: a^2 - a - 1 = 0. Solving with the ABC-rule gives a = (1 + sqrt(5)) / 2 +-= 1.618, the famous golden ratio. For the ancient Greeks (particularly the Pyhtagoreans), and throughout the history of art, this number meant utter harmony. For this one can repeat the above induction proof. We are lucky that we have "+ 1" and not "- 1". Otherwise the development would still have been of the same order, but the proof would have been harder. So, we know now that the depth of an AVL tree with a given number of nodes N is at most log_a N = log_2 N / log_2 a = 1.440 * log_2 N. In most cases it will be less, but the main point is that this is logarithmic.
why the fuck do you even answer the moron? he obviously trying to get home work done. you fucking retard!!
Are you trying to get your homework done through this site?
- Anonymous January 30, 2009