[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Charles Levert
Subject: Re: src/kwset.c (kwsincr): Replace arbitrary array size by proper value
Date: Thu, 7 Jul 2005 02:51:34 -0400
User-agent: Mutt/1.4.1i

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.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]