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

[Charles Levert]

Thanks for the reference.  Knowing this is
called an AVL tree has allowed me to investigate
further.  Unfortunately, I only own volume 2
of tAoCP.  Using lg() instead of log_2() may be a
computer science notational thing; I haven't seen
it being used when I studied information theory.


* On Tuesday 2005-07-05 at 16:59:09 -0700, Paul Eggert wrote:
> 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,

Unfortunately, in this case I use n for all
nodes, internal and leaves.


> and we assume each internal
> node has exactly 2 children (so that there are N + 1 leaves).

At most N + 1 leaves, which complicates things
in this case (i.e., finding N from n).


>  "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).

I did some more testing using GNU octave.
It turns out the bound only holds when we
consider the n = 2^b points (with b an integer),
and not all values of n.  Otherwise, we would
have in effect to round things up to the nearest
integral b for it to stay an upper bound at
all time.

This is ok, though.  The floor(1.5 * b) formula
is still the best and simplest one we can use,
because we always are in the integral b case.
I just have to work a little more to document it.