AVL Tree Implementation

Hi,
I am doing a project for one of my courses, and it involves locating a few data structures that meet required complexities. I decided that the best option is to store the data in two separate structures, and use the appropriate structure for each method to provide the user with the correct structure. The two structures I chose are Hashtable, and AVLTree. Hashtable gives me constant time on find, and AVLTree gives me log(n) time on finding the closest after. On insert(Item) with Hashtable, I get constant time, and with AVLTree, I think it is O(n).

I was looking in my texts for implementations of AVLTree, and found that the only method that really differs from BinarySearchTree is the add method, in that after adding the new item to the tree, it has to rebalance the tree. So if each element contains, in addition to its given information, its height in the tree, and pointers to each of its children, how would I go about rebalancing the tree?

I am assuming that I can create the entire tree as in BinarySearchTree, and that I will have to add to the insert method a call to rebalance the tree, but I am stuck on the actual rebalancing. I was looking in the java.util library for a standard AVL tree, but couldn't find one. Am I missing something here?

Thanks in advance.


There are two methods in software design. One is to make the program so simple, there are obviously no errors. The other is to make it so complicated, there are no obvious errors.

Comments

  • Hello,
    From what I remember there are 4 kinds of rotations to rebalance the tree: left-left, left-right, right-right, and right-left.
    7
    /
    4

    5.5
    After inserting 7,4,5.5 in that order you would need to do a left-right rotation, giving you:
    7
    /
    5.5
    /
    4 after the first, left rotation and finally:
    5.5
    /
    4 7

    The right-left is the opposite. I found my old book so tell me if you still want the code.
  • Hi,

    I understand that I have to make 2 rotations whenever a rebalancing is required, but I don't know how to do it. Is there a standard library class that does this, or do you have the code for a normal AVL tree, with each node holding an object that I can specify?

    Thanks for your help.


    There are two methods in software design. One is to make the program so simple, there are obviously no errors. The other is to make it so complicated, there are no obvious errors.

  • : I understand that I have to make 2 rotations whenever a rebalancing is required, but I don't know how to do it. Is there a standard library class that does this, or do you have the code for a normal AVL tree, with each node holding an object that I can specify?

    I don't know of a library that does this but here is what my book says:

    private avlinsert( comparable x, avlnode t) {
    if( t==null)
    t = new avlnode( x,null,null);
    else if( x.compareTo(t.element) < 0 )
    {
    t.left = insert(x,t.left);
    if( height(t.left) - height(t.right) == 2 )
    if(x.compareTo(t.left.element) < 0 )
    t = rotatewithleftchild( t );
    else t = doublewithleftchild;
    }
    else if(x.compareTo( t.element ) > 0 )
    {
    // do same but with right instead of left and > instead of <.
    }
    else; // duplicate element, do nothing
    t.height = max( height( t.left), height(t.right) ) + 1;
    return t;
    }

    private static avlnode rotatewithleftchild( avlnode k2 ){
    avlnode k1 = k2.left;
    k2.left = k1.right;
    k1.right = k2;
    k2.height = max( height( k2.left), height(k2.right) ) +1;
    k1.height = max( height( k1.left), k2.height ) +1;
    return k1;

    }

    private static avlnode doublewithleftchild( avlnode k3 ){
    k3.left= rotatewithrightchild(k3.left);
    return rotatewithleftchild(k3);
    }

  • Thanks


    : : I understand that I have to make 2 rotations whenever a rebalancing is required, but I don't know how to do it. Is there a standard library class that does this, or do you have the code for a normal AVL tree, with each node holding an object that I can specify?
    :
    : I don't know of a library that does this but here is what my book says:
    :
    : private avlinsert( comparable x, avlnode t) {
    : if( t==null)
    : t = new avlnode( x,null,null);
    : else if( x.compareTo(t.element) < 0 )
    : {
    : t.left = insert(x,t.left);
    : if( height(t.left) - height(t.right) == 2 )
    : if(x.compareTo(t.left.element) < 0 )
    : t = rotatewithleftchild( t );
    : else t = doublewithleftchild;
    : }
    : else if(x.compareTo( t.element ) > 0 )
    : {
    : // do same but with right instead of left and > instead of <.
    : }
    : else; // duplicate element, do nothing
    : t.height = max( height( t.left), height(t.right) ) + 1;
    : return t;
    : }
    :
    : private static avlnode rotatewithleftchild( avlnode k2 ){
    : avlnode k1 = k2.left;
    : k2.left = k1.right;
    : k1.right = k2;
    : k2.height = max( height( k2.left), height(k2.right) ) +1;
    : k1.height = max( height( k1.left), k2.height ) +1;
    : return k1;
    :
    : }
    :
    : private static avlnode doublewithleftchild( avlnode k3 ){
    : k3.left= rotatewithrightchild(k3.left);
    : return rotatewithleftchild(k3);
    : }
    :
    :

    There are two methods in software design. One is to make the program so simple, there are obviously no errors. The other is to make it so complicated, there are no obvious errors.

Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories