DaniWeb Forum Index > Software Development > C++

C++ RSS

Avl Tree

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: Sep 2009

Posts: 76

Reputation: Gaiety is an unknown quantity at this point

Solved Threads: 2

Gaiety

Offline

Junior Poster in Training

Avl Tree

Sep 23rd, 2009

Hi,
Please suggest me how to check a given tree is balanced using the height of tree.
we need to use the avl tree concept.

i.e, the difference between height of any left or right subtree is atmost 1.

i have written the code for inserting the node, but this one i can't understand .

Minds are like parachutes - they only work when they are open
Gaiety

•

Join Date: Oct 2006

Posts: 2,839

Reputation: niek_e has a reputation beyond repute

Solved Threads: 298

niek_e

Offline

Roasting Maven

Re: Avl Tree

Sep 23rd, 2009

Can't explain it as good as Narue does here, so you should take an hour or two to read the article. Everything will be clear afterwards

Last edited by niek_e; Sep 23rd, 2009 at 7:59 am.

•

Join Date: Oct 2006

Posts: 164

Reputation: Barefootsanders is an unknown quantity at this point

Solved Threads: 3

Barefootsanders Barefootsanders is offline

Offline

Junior Poster

Re: Avl Tree

Sep 23rd, 2009

If you understand the concepts and have written the insert function, then this should not be all that difficult to understand. Just for reference:

•

In an AVL tree, the heights of the two child subtrees of any node differ by at most one

So one solution would be to write a function that takes a node, at any given point in the tree, and can calculate its height (might involve recursion depending on how you determine it). Then you can pass child of the root to this function and determine if its a proper AVL tree or not.

Below is some scrappy pseudocode:
if heightLeftSubTree - heightRightSubTree is between -1 and 1
--this tree is an AVL tree
else
--this tree is NOT an AVL tree
end

Hope that helps (without giving to much away

)

Last edited by Barefootsanders; Sep 23rd, 2009 at 9:48 am.