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

Groups > comp.programming > #2008

Re: Needs help with AVL tree height calculation

From Ike Naar <ike@iceland.freeshell.org>
Newsgroups comp.programming
Subject Re: Needs help with AVL tree height calculation
Date 2012-07-26 08:13 +0000
Organization A noiseless patient Spider
Message-ID <slrn3vfsk11v25.l9p.ike@iceland.freeshell.org> (permalink)
References <52c12378-c27f-44d2-81aa-d146a9cbfea4@googlegroups.com> <0.2d59d9a4e11cceec7fba.20120725144027BST.871uk0q7qs.fsf@bsb.me.uk> <e4510529-37c9-4b21-8e51-a29fb4c2a2d8@googlegroups.com>

Show all headers | View raw

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.

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