Charles Levert <[EMAIL PROTECTED]> writes: >> 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, > > Unfortunately, in this case I use n for all > nodes, internal and leaves.
If you have N internal nodes, then you have N + 1 leaf nodes, for a total of 2*N + 1 nodes, so it shouldn't be hard to substitute your variables for Knuth's. But I would stick with Knuth's notation myself; why reinvent the wheel? > This is ok, though. The floor(1.5 * b) formula > is still the best and simplest one we can use, I disagree! You don't have a proof. Knuth does. You should be able to derive your lower bound from Knuth's; if you can't, then there's something really fishy going on.
