943,568 Members | Top Members by Rank

Ad:
  • C++ Discussion Thread
  • Unsolved
  • Views: 1641
  • C++ RSS
Sep 23rd, 2009
0

Avl Tree

Expand Post »
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 .
Similar Threads
Reputation Points: 13
Solved Threads: 3
Junior Poster
Gaiety is offline Offline
110 posts
since Sep 2009
Sep 23rd, 2009
0

Re: Avl Tree

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 Nick Evan; Sep 23rd, 2009 at 7:59 am.
Moderator
Featured Poster
Reputation Points: 4142
Solved Threads: 394
Industrious Poster
Nick Evan is offline Offline
4,132 posts
since Oct 2006
Sep 23rd, 2009
0

Re: Avl Tree

If you understand the concepts and have written the insert function, then this should not be all that difficult to understand. Just for reference:
Quote ...
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.
Reputation Points: 10
Solved Threads: 3
Junior Poster
Barefootsanders is offline Offline
165 posts
since Oct 2006

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in C++ Forum Timeline: glut still not working... much
Next Thread in C++ Forum Timeline: error reading file





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC