Groups > comp.programming > #2004

Re: Needs help with AVL tree height calculation

Path	csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!eternal-september.org!feeder.eternal-september.org!mx04.eternal-september.org!.POSTED!not-for-mail
From	Ike Naar <ike@sverige.freeshell.org>
Newsgroups	comp.programming
Subject	Re: Needs help with AVL tree height calculation
Date	Wed, 25 Jul 2012 12:13:28 +0000 (UTC)
Organization	A noiseless patient Spider
Lines	44
Message-ID	<slrn3vfsk0von8.3p3.ike@sverige.freeshell.org> (permalink)
References	<52c12378-c27f-44d2-81aa-d146a9cbfea4@googlegroups.com>
Mime-Version	1.0
Content-Type	text/plain; charset=us-ascii
Content-Transfer-Encoding	7bit
Injection-Date	Wed, 25 Jul 2012 12:13:28 +0000 (UTC)
Injection-Info	mx04.eternal-september.org; posting-host="997df6d4337f06c91a3debbd76930da9"; logging-data="14906"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/6cLKTez0X+/8jepsJi2zF"
User-Agent	slrn/0.9.9p1 (NetBSD)
Cancel-Lock	sha1:GaAJBsfrGHTuQwSNOp0cHdpnw3s=
Xref	csiph.com comp.programming:2004

Show key headers only | View raw

On 2012-07-25, Curious George <ollemblomgren@gmail.com> wrote:
> Hi
>
> Let's start with two examples.
>
> 1) Height starts from 1
> ---------------------------
> To me, an AVL tree that looks like this:
>
> O           Height 1
>  \
>   O         Height 2
>
> is valid. However if a use the algorithm presented here:
> http://en.wikipedia.org/wiki/AVL_tree
>
> it is not. The calculation I make is:
> 1.44 * log2(2 + 2) - 1 = 1.880000
>
> According to the wiki above the height must be less than 1.88, which it isn't if I say that the root node is on height 1. So let's try to calculate with the height of the root node being 0.
>
> 2) Height starts from 0
> ---------------------------
> To me, an AVL tree theat looks like this:
>
> O           Height 0
>  \
>   O         Height 1
>    \
>     O       Height 2
>
> is invalid. However if a use the algorithm presented here:
> http://en.wikipedia.org/wiki/AVL_tree
>
> it is not. The calculation I make is:
> 1.44 * log2(3 + 2) - 1 = 2.343576
>
> According to the wiki above the height must be less than 2.34, which it is if I say that the root node is on height 0.
>
> I obviously need some help here. Anyone?

Think of height as a path length: the length of the path
from the root to the most distant leaf; so don't measure the
height in terms of nodes, but in terms of edges.

Thread

Needs help with AVL tree height calculation Curious George <ollemblomgren@gmail.com> - 2012-07-25 02:18 -0700
  Re: Needs help with AVL tree height calculation Ike Naar <ike@sverige.freeshell.org> - 2012-07-25 12:13 +0000
    Re: Needs help with AVL tree height calculation Curious George <ollemblomgren@gmail.com> - 2012-07-25 05:59 -0700
  Re: Needs help with AVL tree height calculation Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-07-25 14:40 +0100
    Re: Needs help with AVL tree height calculation Curious George <ollemblomgren@gmail.com> - 2012-07-26 00:10 -0700
      Re: Needs help with AVL tree height calculation Ike Naar <ike@iceland.freeshell.org> - 2012-07-26 08:13 +0000
        Re: Needs help with AVL tree height calculation Curious George <ollemblomgren@gmail.com> - 2012-07-26 03:54 -0700
          Re: Needs help with AVL tree height calculation Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-07-26 14:38 +0100
          Re: Needs help with AVL tree height calculation Ike Naar <ike@sverige.freeshell.org> - 2012-07-26 14:03 +0000
            Re: Needs help with AVL tree height calculation Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-07-26 15:53 +0100
              Re: Needs help with AVL tree height calculation Curious George <ollemblomgren@gmail.com> - 2012-07-27 05:21 -0700
      Re: Needs help with AVL tree height calculation Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-07-26 13:20 +0100
  Re: Needs help with AVL tree height calculation Tim Rentsch <txr@alumni.caltech.edu> - 2012-07-26 03:59 -0700

csiph-web