Results 1 to 3 of 3
  1. #1
    ryuzog is offline Member
    Join Date
    Jan 2010
    Posts
    32
    Rep Power
    0

    Default 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...

  2. #2
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,344
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by ryuzog View Post
    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...
    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);
       }
    }
    kind regards,

    Jos

  3. #3
    ryuzog is offline Member
    Join Date
    Jan 2010
    Posts
    32
    Rep Power
    0

    Default

    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 01:42 PM.

Similar Threads

  1. Width (-1) and height (-1) cannot be <= 0
    By LovJava in forum AWT / Swing
    Replies: 5
    Last Post: 04-24-2010, 12:16 AM
  2. Replies: 0
    Last Post: 04-04-2010, 07:40 AM
  3. height of the image.
    By programmer_007 in forum Java 2D
    Replies: 13
    Last Post: 02-18-2010, 12:17 PM
  4. Adding/removing nodes to tree under TreeViewer
    By Rodrigo Braz in forum SWT / JFace
    Replies: 0
    Last Post: 04-20-2009, 01:02 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •