TechArena Community - avl tree java adjust height

TechArena Community (http://forums.techarena.in/)

- Software Development (http://forums.techarena.in/software-development/)

- - avl tree java adjust height (http://forums.techarena.in/software-development/1191750.htm)

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.

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!

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