Path: csiph.com!usenet.pasdenom.info!gegeweb.org!eternal-september.org!feeder.eternal-september.org!mx04.eternal-september.org!.POSTED!not-for-mail From: Ike Naar Newsgroups: comp.programming Subject: Re: Needs help with AVL tree height calculation Date: Thu, 26 Jul 2012 14:03:26 +0000 (UTC) Organization: A noiseless patient Spider Lines: 35 Message-ID: References: <52c12378-c27f-44d2-81aa-d146a9cbfea4@googlegroups.com> <0.2d59d9a4e11cceec7fba.20120725144027BST.871uk0q7qs.fsf@bsb.me.uk> <8d5ea643-bcc4-4431-8648-7446763a0b3d@googlegroups.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Injection-Date: Thu, 26 Jul 2012 14:03:26 +0000 (UTC) Injection-Info: mx04.eternal-september.org; posting-host="997df6d4337f06c91a3debbd76930da9"; logging-data="4353"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18f/T/YW57Iya7GE+KWeZFn" User-Agent: slrn/0.9.9p1 (NetBSD) Cancel-Lock: sha1:ZDFyyBoWiOWucmrvmk9qJWwoA9g= Xref: csiph.com comp.programming:2013 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. 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.