#1
 Hakon Member Join Date: Jan 2009 Posts: 66

hi ,
i am having some issues with understanding an avl tree .i have converted the text book definition of traversals but the problem i am having to adjust the height after traversals....so can some one help me ?

Quote:
 public int getMaxHeight () ( if (isLeaf ()) / / is a leaf, it stops return 1; int hd = 0, hg = 0; if (left! = null) = 1 + hg gauche.getMaxHeight (); if (hd> hg) return hd; return hg; ) / ** Returns the max of 2 branches (recursively!) * public int getMaxHeight () ( int height = 0; AVLNode node = this; while (node.deseq! = 0) ( height + +; if (node.deseq <0) node = node.gauche; else node = node.right; ) return height; ) Obviously, it is invariant in all following instances AVLNode: if left is zero, then: if the right is zero, then: deseq = 0, / / leaf otherwise: deseq> 0, / / right leaning tree end if; else if the right is zero, then : deseq <0, / / left hanging tree otherwise deseq is any sign: two trees left and right non-zero, the longest is indicated by the sign of deseq; end if.
#2
 opaper Member Join Date: May 2008 Posts: 2,383
Re: avl tree java adjust height

a simple loop enough to fall on a leaf, simply by following the loop in each branch the longer determined by the imbalance!

In addition, if the imbalance is not zero, we know that at least one son node side indicated by the sign of imbalance, it is not necessary to test whether it is on a leaf

just replace the following code:
Quote:
 / ** Return the max of 2 branches (recursively!) * public int getMaxHeight () ( if (isLeaf ()) / / is a leaf, it stops return 1; int hd = 0, hg = 0; if (left! = null) = 1 + hg gauche.getMaxHeight (); if (right! = null) = 1 + hd right.getMaxHeight (); if (hd> hg) return hd; return hg; ) / ** Returns the max of 2 branches (recursively!) * public int getMaxHeight () ( int height = 1; AVLNode node = this; while (node.deseq! = 0) ( height + +; if (node.deseq <0) node = node.gauche; else node = node.right; ) return height; ) Obviously, it is invariant in all following instances AVLNode: if left is zero, then: if the right is zero, then: deseq = 0, / / leaf otherwise: deseq> 0, / / right leaning tree end if; else if the right is zero, then : deseq <0, / / left hanging tree otherwise deseq is any sign: two trees left and right non-zero, the longest is indicated by the sign of deseq; end if.
So you have to create all the sheets with deseq = 0 in the constructor, and update in case of insertion to the right or left, or deleting a node in a branch. Accelerated serve this function easily and quickly recalculate the maximum height to which of the branches is longer when there are two sub-trees. This does not require recursion and it will be faster!
#3
 Modifier Member Join Date: Jan 2008 Posts: 1,515
Re: avl tree java adjust height

It provides:

Quote:
 public int getMaxHeight () ( int height = 0; AVLNode node = this; while (node! = null) ( height + +; if (node.deseq> 0) node = noeud.droite; else node = node.gauche; ) return height; )
There is no importance on which branches are followed, just as it is one of the branches in length. Along this branch, nodes can have a zero balance, but it always follows the branch unbalanced when there is one, otherwise a branch arbitrary

 Tags:

 Thread Tools Search this Thread Show Printable Version Email this Page Search this Thread: Advanced Search Similar Threads for: "avl tree java adjust height" Thread Thread Starter Forum Replies Last Post How to adjust tab height in Firefox 8 Kanesteyn Technology & Internet 4 03-12-2011 03:52 PM Unable to adjust Dell Ultra Sharp 2408WFP Monitor height wise veGANor Monitor & Video Cards 4 25-11-2010 02:59 AM Walking the File Tree in Java DANIEL 602 Software Development 5 19-02-2010 04:37 AM How to use a Tree Expansion Listener in Java? Rob Dizzle Software Development 4 13-02-2010 06:03 AM JAVA binary tree Daren Software Development 4 29-09-2009 12:17 AM

All times are GMT +5.5. The time now is 08:13 PM.