Go Back   TechArena Community > Software > Software Development
Become a Member!
Forgot your username/password?
Register Tags Active Topics RSS Search Mark Forums Read

Sponsored Links



avl tree java adjust height

Software Development


Reply
 
Thread Tools Search this Thread
  #1  
Old 04-06-2009
Member
 
Join Date: Jan 2009
Posts: 66
avl tree java adjust height
  

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.

Reply With Quote
  #2  
Old 04-06-2009
Member
 
Join Date: May 2008
Posts: 2,378
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!
Reply With Quote
  #3  
Old 04-06-2009
Member
 
Join Date: Jan 2008
Posts: 1,513
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
Reply With Quote
Reply

  TechArena Community > Software > Software Development
Tags: ,



Thread Tools Search this Thread
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 02:52 PM
Unable to adjust Dell Ultra Sharp 2408WFP Monitor height wise veGANor Monitor & Video Cards 4 25-11-2010 01:59 AM
Walking the File Tree in Java DANIEL 602 Software Development 5 19-02-2010 03:37 AM
How to use a Tree Expansion Listener in Java? Rob Dizzle Software Development 4 13-02-2010 05: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 01:24 PM.