Results 1 to 3 of 3
- 11-09-2010, 02:21 AM #1
Member
- 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...
- 11-09-2010, 09:08 AM #2
- Join Date
- Sep 2008
- Location
- Voorschoten, the Netherlands
- Posts
- 14,422
- Blog Entries
- 7
- Rep Power
- 29
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
- 11-09-2010, 02:34 PM #3
Member
- 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 tri-node 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; 11-09-2010 at 02:42 PM.
Similar Threads
-
Width (-1) and height (-1) cannot be <= 0
By LovJava in forum AWT / SwingReplies: 5Last Post: 04-24-2010, 01:16 AM -
Data Structures(Binary Search Tree to AVL Tree)ASAP pls
By jfAdik in forum Forum LobbyReplies: 0Last Post: 04-04-2010, 08:40 AM -
height of the image.
By programmer_007 in forum Java 2DReplies: 13Last Post: 02-18-2010, 01:17 PM -
Adding/removing nodes to tree under TreeViewer
By Rodrigo Braz in forum SWT / JFaceReplies: 0Last Post: 04-20-2009, 02:02 AM
Bookmarks