Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #2004

Re: Needs help with AVL tree height calculation

Show all headers | 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.

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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