Re: src/kwset.c (kwsincr): Replace arbitrary array size by proper value

[Paul Eggert]

Charles Levert <address@hidden> 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).