Results 1 to 3 of 3

Thread: avl tree java adjust height

  1. #1
    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 ?

    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. #2
    Join Date
    May 2008
    Posts
    2,393

    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:
    / ** 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. #3
    Join Date
    Jan 2008
    Posts
    1,521

    Re: avl tree java adjust height

    It provides:

    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

Similar Threads

  1. How to adjust tab height in Firefox 8
    By Kanesteyn in forum Technology & Internet
    Replies: 4
    Last Post: 03-12-2011, 02:52 PM
  2. Unable to adjust Dell Ultra Sharp 2408WFP Monitor height wise
    By veGANor in forum Monitor & Video Cards
    Replies: 4
    Last Post: 25-11-2010, 01:59 AM
  3. Walking the File Tree in Java
    By DANIEL 602 in forum Software Development
    Replies: 5
    Last Post: 19-02-2010, 03:37 AM
  4. How to use a Tree Expansion Listener in Java?
    By Rob Dizzle in forum Software Development
    Replies: 4
    Last Post: 13-02-2010, 05:03 AM
  5. JAVA binary tree
    By Daren in forum Software Development
    Replies: 4
    Last Post: 29-09-2009, 12:17 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
  •