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

Groups > comp.programming > #2013

Re: Needs help with AVL tree height calculation

Show key headers only | View raw

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.

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