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

Groups > comp.programming > #2003 > unrolled thread

Needs help with AVL tree height calculation

Back to article view | Back to comp.programming

Contents

  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

#2003 — Needs help with AVL tree height calculation

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?

Thanks in advance

[toc] | [next] | [standalone]

#2004

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.

[toc] | [prev] | [next] | [standalone]

#2005

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.

[toc] | [prev] | [next] | [standalone]

#2006

Curious George <ollemblomgren@gmail.com> writes:

> 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

Two things:

First, the formula on the Wiki page is wrong.  If you try to find the
reference from which it comes (the link is broken, but something similar
exists) we find:

  log2(n+1) <= height(T) < log_phi(sqtr(5) * (n+2)) - 2

which is 2.55... for n = 2.

> 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

No the height starts from 1.  The formula threw you.

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

The "proper" formula gives 3.01... but here's the second thing.  I this
even an AVL tree?  I thought AVL trees are balanced, and this is not
a balanced 3-node tree.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#2007

On Wednesday, July 25, 2012 3:40:27 PM UTC+2, Ben Bacarisse wrote:
> Curious George writes:
> 
> > 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
> 
> Two things:
> 
> First, the formula on the Wiki page is wrong.  If you try to find the
> reference from which it comes (the link is broken, but something similar
> exists) we find:
> 
>   log2(n+1) <= height(T) < log_phi(sqtr(5) * (n+2)) - 2
> 
> which is 2.55... for n = 2.
> 
> > 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
> 
> No the height starts from 1.  The formula threw you.
> 
> > ---------------------------
> > 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.
> 
> The "proper" formula gives 3.01... but here's the second thing.  I this
> even an AVL tree?  I thought AVL trees are balanced, and this is not
> a balanced 3-node tree.
> 
> -- 
> Ben.
Hi Ben, 

and thanks for helping out. You're right, it is not a properly balanced tree. What I'm doing is implementing an AVL-tree validating function that traverses the whole tree and makes sure it is properly balanced. I use the formula above.

The thing is that your formula results in 3.01 which means that unless I truncate the value into 3.00, you formula isn't working either. Are you aware of this?

Thanks again!

[toc] | [prev] | [next] | [standalone]

#2008

On 2012-07-26, Curious George <ollemblomgren@gmail.com> wrote:
> What I'm doing is implementing an AVL-tree validating function that
> traverses the whole tree and makes sure it is properly balanced.
> I use the formula above.

You don't need the formula to verify whether an AVL tree is properly
balanced. It is sufficient to check that, for every node, the height
of the left and right subtrees of that node differ by atmost 1.
This is just as efficient as computing the height of the tree.

[toc] | [prev] | [next] | [standalone]

#2009

On Thursday, July 26, 2012 10:13:57 AM UTC+2, Ike Naar wrote:
> On 2012-07-26, Curious George wrote:
> > What I'm doing is implementing an AVL-tree validating function that
> > traverses the whole tree and makes sure it is properly balanced.
> > I use the formula above.
> 
> You don't need the formula to verify whether an AVL tree is properly
> balanced. It is sufficient to check that, for every node, the height
> of the left and right subtrees of that node differ by atmost 1.
> This is just as efficient as computing the height of the tree.

Each node has a left depth and a right depth and I act on those to balance the tree. What I want to do now is to double check that the tree is in fact valid. If I have managed to mess up the depth values I can catch such errors by using another way of calculating the validity of the tree.

[toc] | [prev] | [next] | [standalone]

#2012

Curious George <ollemblomgren@gmail.com> writes:

> On Thursday, July 26, 2012 10:13:57 AM UTC+2, Ike Naar wrote:
>> On 2012-07-26, Curious George wrote:
>> &gt; What I&#39;m doing is implementing an AVL-tree validating function that
>> &gt; traverses the whole tree and makes sure it is properly balanced.
>> &gt; I use the formula above.
>> 
>> You don&#39;t need the formula to verify whether an AVL tree is properly
>> balanced. It is sufficient to check that, for every node, the height
>> of the left and right subtrees of that node differ by atmost 1.
>> This is just as efficient as computing the height of the tree.
>
> Each node has a left depth and a right depth and I act on those to
> balance the tree. What I want to do now is to double check that the
> tree is in fact valid. If I have managed to mess up the depth values I
> can catch such errors by using another way of calculating the validity
> of the tree.

An exact way to do this is to know how many nodes there are in the
largest balanced tree of height h: it's 2F(h+1) - 1, the number of nodes
in a Fibonacci Tree of order h (F(n) is the nth Fibonacci number).

(See Knuth at the pages in the Wiki page -- I've edited it since TAOCP
is a more reliable reference than the online notes that were the
original source for the formulae.)

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#2013

On 2012-07-26, Curious George <ollemblomgren@gmail.com> wrote:
> On Thursday, July 26, 2012 10:13:57 AM UTC+2, Ike Naar wrote:
>> On 2012-07-26, Curious George wrote:
>> &gt; What I&#39;m doing is implementing an AVL-tree validating function that
>> &gt; traverses the whole tree and makes sure it is properly balanced.
>> &gt; I use the formula above.
>> 
>> You don&#39;t need the formula to verify whether an AVL tree is properly
>> balanced. It is sufficient to check that, for every node, the height
>> of the left and right subtrees of that node differ by atmost 1.
>> This is just as efficient as computing the height of the tree.
>
> Each node has a left depth and a right depth and I act on those to
> balance the tree. What I want to do now is to double check that the
> tree is in fact valid. If I have managed to mess up the depth values
> I can catch such errors by using another way of calculating the
> validity of the tree.

But the validity check that uses the magic formula is too weak.
Consider the following trees:

     (A)        (B)

      o          o
     /          / \
    o          o   o
   / \        /
  o   o      o

(A) is an invalid AVL tree (the root is skewed), (B) is valid.
Both trees have the same height and the same number of nodes.
Because they have the same number of nodes, the magic formula
will yield the same value for both trees.
So, from the value computed by the magic formula alone, you cannot
tell whether a tree is a valid AVL tree.

[toc] | [prev] | [next] | [standalone]

#2014

Ike Naar <ike@sverige.freeshell.org> writes:

> On 2012-07-26, Curious George <ollemblomgren@gmail.com> wrote:
>> On Thursday, July 26, 2012 10:13:57 AM UTC+2, Ike Naar wrote:
>>> On 2012-07-26, Curious George wrote:
>>> &gt; What I&#39;m doing is implementing an AVL-tree validating function that
>>> &gt; traverses the whole tree and makes sure it is properly balanced.
>>> &gt; I use the formula above.
>>> 
>>> You don&#39;t need the formula to verify whether an AVL tree is properly
>>> balanced. It is sufficient to check that, for every node, the height
>>> of the left and right subtrees of that node differ by atmost 1.
>>> This is just as efficient as computing the height of the tree.
>>
>> Each node has a left depth and a right depth and I act on those to
>> balance the tree. What I want to do now is to double check that the
>> tree is in fact valid. If I have managed to mess up the depth values
>> I can catch such errors by using another way of calculating the
>> validity of the tree.
>
> But the validity check that uses the magic formula is too weak.
<snip diagram>
> (A) is an invalid AVL tree (the root is skewed), (B) is valid.
> Both trees have the same height and the same number of nodes.

Good point.  The OP should replace "such" by "some" in his last
sentence!  Maybe that's enough, since it's an extra test.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#2015

On Thursday, July 26, 2012 4:53:01 PM UTC+2, Ben Bacarisse wrote:
> Ike Naar  writes:
> 
> > On 2012-07-26, Curious George  wrote:
> >> On Thursday, July 26, 2012 10:13:57 AM UTC+2, Ike Naar wrote:
> >>> On 2012-07-26, Curious George wrote:
> >>> > What I'm doing is implementing an AVL-tree validating function that
> >>> > traverses the whole tree and makes sure it is properly balanced.
> >>> > I use the formula above.
> >>> 
> >>> You don't need the formula to verify whether an AVL tree is properly
> >>> balanced. It is sufficient to check that, for every node, the height
> >>> of the left and right subtrees of that node differ by atmost 1.
> >>> This is just as efficient as computing the height of the tree.
> >>
> >> Each node has a left depth and a right depth and I act on those to
> >> balance the tree. What I want to do now is to double check that the
> >> tree is in fact valid. If I have managed to mess up the depth values
> >> I can catch such errors by using another way of calculating the
> >> validity of the tree.
> >
> > But the validity check that uses the magic formula is too weak.
> <snip diagram>
> > (A) is an invalid AVL tree (the root is skewed), (B) is valid.
> > Both trees have the same height and the same number of nodes.
> 
> Good point.  The OP should replace "such" by "some" in his last
> sentence!  Maybe that's enough, since it's an extra test.
> 
> -- 
> Ben.

As Ike has pointed out, this is not the way to validate an AVL tree. I will go about this another way. 

Thanks a lot for clarifying!

[toc] | [prev] | [next] | [standalone]

#2011

Curious George <ollemblomgren@gmail.com> writes:

> On Wednesday, July 25, 2012 3:40:27 PM UTC+2, Ben Bacarisse wrote:
>> Curious George writes:
<snip>
>> &gt; ---------------------------
>> &gt; To me, an AVL tree theat looks like this:
>> &gt;
>> &gt; O           Height 0
>> &gt;  \
>> &gt;   O         Height 1
>> &gt;    \
>> &gt;     O       Height 2
>> &gt;
>> &gt; is invalid. However if a use the algorithm presented here:
>> &gt; http://en.wikipedia.org/wiki/AVL_tree
>> &gt;
>> &gt; it is not. The calculation I make is:
>> &gt; 1.44 * log2(3 + 2) - 1 = 2.343576
>> &gt;
>> &gt; According to the wiki above the height must be less than 2.34, which
>> &gt; it is if I say that the root node is on height 0.
>> 
>> The &quot;proper&quot; formula gives 3.01... but here&#39;s the
>> second thing.  I this even an AVL tree?  I thought AVL trees are
>> balanced, and this is not a balanced 3-node tree.
<snip>
> and thanks for helping out. You're right, it is not a properly
> balanced tree. What I'm doing is implementing an AVL-tree validating
> function that traverses the whole tree and makes sure it is properly
> balanced. I use the formula above.
>
> The thing is that your formula results in 3.01 which means that unless
> I truncate the value into 3.00, you formula isn't working either. Are
> you aware of this?

There is no indication how tight the upper bound is.  The formula maybe
correct even if the upper bound is not tight enough for your purposes.

As has been pointed out, it's an odd way to check an AVL tree (and it
doesn't work for n = 3 though I imagine the bound gets tighter for
larger n).

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#2010

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.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web