Charles Levert <[EMAIL PROTECTED]> writes: > -- Balanced binary trees (at every node, > the depth difference of the two subtrees is > at most 1). > > -- Worst (i.e., maximal) depth d_max(n) of such a > tree as a function of the number n of nodes > in it.
The height of a balanced binary tree with N internal nodes always lies between lg(N + 1) and (1.4404 lg (N + 2) - 0.3277). Here, the "internal nodes" are those with children, and we assume each internal node has exactly 2 children (so that there are N + 1 leaves). "lg N" means the log base 2 of N. This is Theorem A of Knuth vol. 3 section 6.2.3; it is originally due to Adelson-Velsky and Landis (often called "AVL"). > -- Alternatively, worst (i.e., minimal) number > n_min(d) of nodes in such a tree of depth d. > > n_min(0) = 0 > n_min(1) = 1 > n_min(d) = d + n_min(0) + ... n_min(n-2) Assuming you're counting only internal nodes as above, then n_min(d) >= F(d+2) - 1, where F(d) is the d'th Fibonacci number. Therefore n_min(d) is bounded below by ((phi)**(d+2))/(sqrt(5)) - 2, where phi is the golden ratio (sqrt(5) + 1)/2. This result is is used in the proof for the AVL result (as published by Knuth).
