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

Groups > comp.programming > #2010

Re: Needs help with AVL tree height calculation

Show all headers | View raw

Curious George <ollemblomgren@gmail.com> writes:

> 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
>

This tree doesn't satisfy the AVL property.

> I obviously need some help here. Anyone?

Your terminology is a little bit off.  There is a link on the AVL
tree page:  http://en.wikipedia.org/wiki/Tree_data_structure
Briefly, easuring from the top gives 'depth';  measuring from the
(deepest descendent) bottom gives 'height'. 

Example:

             4        depth 0
            / \
           2   5      depth 1
          / \
         1   3        depth 2

   The height of '1' is 0;
   The height of '3' is 0;
   The height of '5' is 0;

   The height of '2' is 1;  (either child has height 0;  1+0 == 1)

   The height of '4' is 2;  (which is 1 + maximum(1,0))

Using this terminology the formula is right.

Also, it probably would help you to draw the "most lopsided"
AVL trees of several small heights, to get an idea for the
shape and the numbers.  Here are a few to get you started:

         O        (height 0,  1 node)

         O        (height 1,  2 nodes)
        /
       O

         O        (height 2,  4 nodes)
        / \
       O   O
      /
     O  

         O        (height 3, 7 nodes)
        / \---\   
       O       O      (I had to jag to make the tree fit)
      / \     /
     O   O   O
    /
   O

Note that the "most lopsided" trees that still satisfy
the AVL property will have the _smallest_ number of
nodes for a given height (ie, subtracting a node must
take away the deepest node, otherwise the AVL
property would be violated).  This observation should
allow you to confirm that the formula is working.

Back to comp.programming | Previous | Next — Previous 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