Howdy, Stranger!

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

Categories

AVL Tree Implementation

nightsurfernightsurfer Member Posts: 272
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

  • dontknow82dontknow82 Member Posts: 11
    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.
  • nightsurfernightsurfer Member Posts: 272
    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.

  • dontknow82dontknow82 Member Posts: 11
    : 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);
    }

  • nightsurfernightsurfer Member Posts: 272
    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.

  • Justin BibJustin Bib USAMember Posts: 0

    ________ \ http://forcoder.org \ free video tutorials and ebooks about [ PHP Visual Basic .NET Scratch Delphi C# Swift PL/SQL C++ R C Python Java Perl Go MATLAB Assembly Visual Basic Objective-C Ruby JavaScript Hack F# Clojure Transact-SQL Julia Prolog Bash D VBScript Scheme Apex Kotlin Lua ML Crystal Erlang FoxPro Logo Lisp COBOL SAS Ada Fortran ABAP Rust Scala Dart LabVIEW Awk Alice ] _______

Sign In or Register to comment.