Advertisements
Home > data structure, Information Technology, programming > AVLTree: JAVA Source Code

AVLTree: JAVA Source Code

In computer science, an AVL tree is a self-balancing binary search tree, and it was the first such data structure to be invented.[1] In an AVL tree, the heights of the two child subtrees of any node differ by at most one; therefore, it is also said to be height-balanced. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.

The AVL tree is named after its two inventors, G.M. Adelson-Velskii and E.M. Landis, who published it in their 1962 paper “An algorithm for the organization of information.”[2]

The balance factor of a node is the height of its left subtree minus the height of its right subtree (sometimes opposite) and a node with balance factor 1, 0, or −1 is considered balanced. A node with any other balance factor is considered unbalanced and requires rebalancing the tree. The balance factor is either stored directly at each node or computed from the heights of the subtrees.

AVL trees are often compared with red-black trees because they support the same set of operations and because red-black trees also take O(log n) time for the basic operations. AVL trees perform better than red-black trees for lookup-intensive applications.[3] The AVL tree balancing algorithm appears in many computer science curricula.

more on Wikipedia

AVLTree.java

public class AvlTree {

AvlNode position;

AvlNode avlTree;

public AvlNode makeEmpty(AvlNode t) {

if(t != null) {

makeEmpty(t.getLeft());

makeEmpty(t.getRight());

t = null;

}

return null;

}

public AvlNode find(int value, AvlNode t) {

if (t == null) {

return null;

}

if (value < t.getValue()) {

return find(value, t.getLeft());

}

else if(value > t.getValue()) {

return find(value, t.getRight());

}

else

return t;

}

public AvlNode findMin(AvlNode t) {

if (t == null) {

return null;

}

else  if(t.getLeft() == null)

return t;

else

return findMin(t.getLeft());

}

public AvlNode findMax(AvlNode t) {

if(t != null)

while(t.getRight() != null)

t = t.getRight();

return t;

}

public static int getHeight (AvlNode position) {

if (position == null)

return -1;

else

return position.getHeight();

}

public static int max (int lhs, int rhs) {

return lhs > rhs ? lhs : rhs;

}

public static AvlNode singleRotateWithLeft (AvlNode k2) {

AvlNode k1;

k1 = k2.getLeft();

k2.setLeft(k1.getRight());

k1.setRight(k2);

k2.setHeight(max(getHeight(k2.getLeft()), getHeight(k2.getRight()))+1);

k1.setHeight(max(getHeight(k1.getLeft()),k2.getHeight())+1);

return k1;

}

public static AvlNode singleRotateWithRight (AvlNode k1) {

AvlNode k2;

k2 = k1.getRight();

k1.setRight(k2.getLeft());

k2.setLeft(k1);

k1.setHeight(max(getHeight(k1.getLeft()), getHeight(k1.getRight()))+1);

k2.setHeight(max(getHeight(k2.getRight()),k1.getHeight())+1);

return k2;

}

public static AvlNode doubleRotateWithLeft (AvlNode k3) {

k3.setLeft(singleRotateWithRight(k3.getLeft()));

return singleRotateWithLeft(k3);

}

public static AvlNode doubleRotateWithRight (AvlNode k1) {

k1.setRight(singleRotateWithLeft(k1.getRight()));

return singleRotateWithRight(k1);

}

public AvlNode insert (int value, AvlNode t) {

if(t == null) {

t = new AvlNode(value);

}

else if(value < t.getValue()) {

t.setLeft(insert(value,t.getLeft()));

if(getHeight(t.getLeft())-getHeight(t.getRight()) == 2)

if(value < t.getLeft().getValue())

t = singleRotateWithLeft(t);

else

t = doubleRotateWithLeft(t);

}

else  if(value > t.getValue()) {

t.setRight(insert(value,t.getRight()));

if(getHeight(t.getRight())-getHeight(t.getLeft()) == 2)

if(value > t.getRight().getValue())

t = singleRotateWithRight(t);

else

t = doubleRotateWithRight(t);

}

t.setHeight(max(getHeight(t.getLeft()), getHeight(t.getRight()))+1);

return t;

}

public int retrieve (AvlNode t) {

return t.getValue();

}

public void preOrder(AvlNode t) {

System.out.println(t.getValue());

if(t.getLeft() != null) {

preOrder(t.getLeft());

}

if(t.getRight() != null) {

preOrder(t.getRight());

}

}

public static void main(String[] args) {

AvlTree at = new AvlTree();

AvlNode t;

AvlNode position;

int i;

int j = 0;

t = at.makeEmpty(null);

for(i=0; i<50; i++, j = (j+7)%50)

t = at.insert(j,t);

for(i=0; i<50; i++)

if((position = at.find(i,t)) == null || at.retrieve(position) != i)

System.out.println(“Error at “+i);

System.out.println(“Min is “+at.retrieve(at.findMin(t))+ ” Max is “+at.retrieve(at.findMax(t))); at.preOrder(t);

}

}

AVLNode.java

public class AvlNode {

private int value;

private AvlNode left;

private AvlNode right;

private int height;

public AvlNode(int value) {

this.value = value;

left = null;

right = null;

height = 0;

}

public int getValue() {

return value;

}

public void setValue(int value) {

this.value = value;

}
public AvlNode getLeft() {

return left;

}
public void setLeft(AvlNode left) {

this.left = left;

}
public AvlNode getRight() {

return right;

}
public void setRight(AvlNode right) {

this.right = right;

}
public int getHeight() {

return height;

}
public void setHeight(int height) {

this.height = height;

}

}

Advertisements
  1. ab
    March 27, 2011 at 9:24 pm

    Wat abt the deletion?

  2. acgpz
    April 4, 2011 at 8:11 pm

    good post!!!!!!

  3. Jables
    December 13, 2011 at 11:55 pm

    public static AvlNode doubleRotateWithLeft (AvlNode k3) {

    k3.setLeft(singleRotateWithRight(k3.getLeft()));

    return singleRotateWithLeft(k3);

    }

    public static AvlNode doubleRotateWithRight (AvlNode k1) {

    k1.setRight(singleRotateWithLeft(k1.getRight()));

    return singleRotateWithRight(k1);

    }

    I don’t understand why you did k3.setLeft and k1.setRight instead of just leaving it like this:

    public static AvlNode doubleRotateWithLeft (AvlNode k3) {

    singleRotateWithRight(k3.getLeft()))

    return singleRotateWithLeft(k3);

    }

    public static AvlNode doubleRotateWithRight (AvlNode k1) {

    singleRotateWithLeft(k1.getRight());

    return singleRotateWithRight(k1);

    }

    What exactly happens in k3.setLeft and k1.setRight?

  4. nandhini
    December 14, 2012 at 7:06 am

    how to run this program please help me
    pleaase

    • February 6, 2013 at 11:03 am

      Wait, you don’t know how to run a JAVA program yet you search for a JAVA program. Why don’t you google it first?

  5. dito26
    May 12, 2013 at 12:29 am

    what about the deletion??

    I almost done all the step, just need delete method

  6. October 3, 2013 at 4:43 pm

    Very nice post.It ids very helpful for my College assignment!!!

  7. Jaypee
    February 26, 2014 at 2:20 am

    It is a succes when i compile it but when i run it .. it Displays :

    Usage: java [-options] class [args…]
    (to execute a class)
    or java [-options] -jar jarfile [args…]
    (to execute a jar file)
    where options include:
    -d32 use a 32-bit data model if available
    -d64 use a 64-bit data model if available
    -client to select the “client” VM
    -server to select the “server” VM
    -hotspot is a synonym for the “client” VM [deprecated]
    The default VM is client.

    -cp
    -classpath
    A ; separated list of directories, JAR archives,
    and ZIP archives to search for class files.
    -D=
    set a system property
    -verbose:[class|gc|jni]
    enable verbose output
    -version print product version and exit
    -version:
    require the specified version to run
    -showversion print product version and continue
    -jre-restrict-search | -no-jre-restrict-search
    include/exclude user private JREs in the version search
    -? -help print this help message
    -X print help on non-standard options
    -ea[:…|:]
    -enableassertions[:…|:]
    enable assertions with specified granularity
    -da[:…|:]
    -disableassertions[:…|:]
    disable assertions with specified granularity
    -esa | -enablesystemassertions
    enable system assertions
    -dsa | -disablesystemassertions
    disable system assertions
    -agentlib:[=]
    load native agent library , e.g. -agentlib:hprof
    see also, -agentlib:jdwp=help and -agentlib:hprof=help
    -agentpath:[=]
    load native agent library by full pathname
    -javaagent:[=]
    load Java programming language agent, see java.lang.instrument
    -splash:
    show splash screen with specified image
    See http://www.oracle.com/technetwork/java/javase/documentation/index.html for more details.

    Process completed.

  8. May 31, 2014 at 5:08 am

    I don’t know if it’s just mee or if eeverybody else encountering issues with your site.
    It looks like some of the written text within your content
    are running off the screen. Can someone else please comment and let me know if this is happening to them as well?

    This might be a isse with my web browser because I’ve
    had thyis happen previously. Thanks

  9. May 22, 2015 at 4:27 pm

    Do not be afraid to sign up for free samples online, it will mean more coupons for the items you use
    and are familiar with. With that said it is clear to see that
    if your business (especially if it’s online) does not have a mobile website is losing customers and
    leaving money on the table. Finding a niche that has about 50,
    000 searches a month is ideal to be able to get good ranking
    and still have a market large enough to be profitable.

  10. May 22, 2015 at 4:37 pm

    It can effectively enhance healthy weight management without the worry of having
    drug side effects. To achieve this, you need to cut the fat so to
    speak and get rid of redundant exercises you don’t realoy need to do.

    Suggestion Concentration acquiring youir carbs in the morning, pre-work out and post-workout.

  11. May 22, 2015 at 4:37 pm

    Some people just don’t realize how important it is to get physical activity
    that raises you heart rate on a regular basis. Overall
    there is no doubt that the Spartacus workout gets results for women. -A light worfkout can be preceded with a light
    snack, but leave more lead time for intense workouts.

  1. November 10, 2013 at 9:49 pm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: