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

Groups > comp.programming > #2005

Re: Needs help with AVL tree height calculation

Show all headers | View raw

On Wednesday, July 25, 2012 2:13:28 PM UTC+2, Ike Naar wrote:
> On 2012-07-25, Curious George; 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.

But isn't that what I do in my second example? I paste it again below:

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.

Something's still missing.

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