Results 1 to 3 of 3
 11092010, 02:21 AM #1Member
 Join Date
 Jan 2010
 Posts
 32
 Rep Power
 0
How do I determine the height of nodes in a AVL tree?
I need to compare the heights of the nodes to the left and right of my current node.
But since the higher height overrides lower heights, I'd need to create a separate count for each "fork in the road" and then compare them all..
This seem laborious for something like starting from the root.
Either that or each node has a native height variable...which should be increased whenever it has a child...or its child has a child...but if two children of the same height have a child and ones child has a child, but the other doesn't, then node should take into account only the one with the child...
How can height be calculate without all this confusion...
 11092010, 09:08 AM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,815
 Blog Entries
 7
 Rep Power
 21
I think you have it all upside down: the height of the root is 0 and the height of its children (if any) are 1 etc. etc. Do you really want to know the height of every node? In an AVL tree it is sufficient (and necessary) to know whether or not a (sub)tree is balanced; the numbers 1, 0 and 1 would be enough for each node. If you really want to know the height of each node the following recursive method sets the height of each node:
Java Code:public void setHeight(Node root, int height) { if (root != null) { root.height= height; setHeight(root.left, height+1); setHeight(root.right, height+1); } }
Jos
 11092010, 02:34 PM #3Member
 Join Date
 Jan 2010
 Posts
 32
 Rep Power
 0
But wouldn't I need to know the height/(or depth?) to determine whether a node is balanced or not? Now that I think about it "height" isn't used, it's some...other thing similar to height. You have to count up from the bottommost node(s) and take the max...determine whether the difference is greater than one...I have the logic of the trinode restructure down, I just don't know an easy way to determine whether or not a node is unbalanced or not.
p.s. that is some wonderful code though =) , an elegant way to deal with splits.Last edited by ryuzog; 11092010 at 02:42 PM.
Similar Threads

Width (1) and height (1) cannot be <= 0
By LovJava in forum AWT / SwingReplies: 5Last Post: 04242010, 12:16 AM 
Data Structures(Binary Search Tree to AVL Tree)ASAP pls
By jfAdik in forum Forum LobbyReplies: 0Last Post: 04042010, 07:40 AM 
height of the image.
By programmer_007 in forum Java 2DReplies: 13Last Post: 02182010, 01:17 PM 
Adding/removing nodes to tree under TreeViewer
By Rodrigo Braz in forum SWT / JFaceReplies: 0Last Post: 04202009, 01:02 AM
Bookmarks