4. May 2012
von Blackbam

In the course of my studies I had to implement an AVL-Tree (balanced binary search tree) in Java. When learning the basics of algorithms and data structures, one will probably have to learn about this topic. I want to present my implementation with some useful comments here, be free to use it, if you need. If you want to learn more about AVL-Trees, check Wikipedia. There is also a very useful Java-application, to demonstrate AVL-trees and more.

 

import java.util.ArrayList;
/**
* This class is the complete and tested implementation of an AVL-tree.
*/
public class AvlTree {
protected AvlNode root; // the root node
/***************************** Core Functions ************************************/
/**
* Add a new element with key "k" into the tree.
* 
* @param k
*            The key of the new node.
*/
public void insert(int k) {
// create new node
AvlNode n = new AvlNode(k);
// start recursive procedure for inserting the node
insertAVL(this.root,n);
}
/**
* Recursive method to insert a node into a tree.
* 
* @param p The node currently compared, usually you start with the root.
* @param q The node to be inserted.
*/
public void insertAVL(AvlNode p, AvlNode q) {
// If  node to compare is null, the node is inserted. If the root is null, it is the root of the tree.
if(p==null) {
this.root=q;
} else {
// If compare node is smaller, continue with the left node
if(q.keyp.key) {
if(p.right==null) {
p.right = q;
q.parent = p;
// Node is inserted now, continue checking the balance
recursiveBalance(p);
} else {
insertAVL(p.right,q);
}
} else {
// do nothing: This node already exists
}
}
}
/**
* Check the balance for each node recursivly and call required methods for balancing the tree until the root is reached.
* 
* @param cur : The node to check the balance for, usually you start with the parent of a leaf.
*/
public void recursiveBalance(AvlNode cur) {
// we do not use the balance in this class, but the store it anyway
setBalance(cur);
int balance = cur.balance;
// check the balance
if(balance==-2) {
if(height(cur.left.left)>=height(cur.left.right)) {
cur = rotateRight(cur);
} else {
cur = doubleRotateLeftRight(cur);
}
} else if(balance==2) {
if(height(cur.right.right)>=height(cur.right.left)) {
cur = rotateLeft(cur);
} else {
cur = doubleRotateRightLeft(cur);
}
}
// we did not reach the root yet
if(cur.parent!=null) {
recursiveBalance(cur.parent);
} else {
this.root = cur;
System.out.println("------------ Balancing finished ----------------");
}
}
/**
* Removes a node from the tree, if it is existent.
*/
public void remove(int k) {
// First we must find the node, after this we can delete it.
removeAVL(this.root,k);
}
/**
* Finds a node and calls a method to remove the node.
* 
* @param p The node to start the search.
* @param q The KEY of node to remove.
*/
public void removeAVL(AvlNode p,int q) {
if(p==null) {
// der Wert existiert nicht in diesem Baum, daher ist nichts zu tun
return;
} else {
if(p.key>q)  {
removeAVL(p.left,q);
} else if(p.key will be replaced by successor
r = successor(q);
q.key = r.key;
}
AvlNode p;
if(r.left!=null) {
p = r.left;
} else {
p = r.right;
}
if(p!=null) {
p.parent = r.parent;
}
if(r.parent==null) {
this.root = p;
} else {
if(r==r.parent.left) {
r.parent.left=p;
} else {
r.parent.right = p;
}
// balancing must be done until the root is reached.
recursiveBalance(r.parent);
}
r = null;
}
/**
* Left rotation using the given node.
* 
* 
* @param n
*            The node for the rotation.
* 
* @return The root of the rotated tree.
*/
public AvlNode rotateLeft(AvlNode n) {
AvlNode v = n.right;
v.parent = n.parent;
n.right = v.left;
if(n.right!=null) {
n.right.parent=n;
}
v.left = n;
n.parent = v;
if(v.parent!=null) {
if(v.parent.right==n) {
v.parent.right = v;
} else if(v.parent.left==n) {
v.parent.left = v;
}
}
setBalance(n);
setBalance(v);
return v;
}
/**
* Right rotation using the given node.
* 
* @param n
*            The node for the rotation
* 
* @return The root of the new rotated tree.
*/
public AvlNode rotateRight(AvlNode n) {
AvlNode v = n.left;
v.parent = n.parent;
n.left = v.right;
if(n.left!=null) {
n.left.parent=n;
}
v.right = n;
n.parent = v;
if(v.parent!=null) {
if(v.parent.right==n) {
v.parent.right = v;
} else if(v.parent.left==n) {
v.parent.left = v;
}
}
setBalance(n);
setBalance(v);
return v;
}
/**
* 
* @param u The node for the rotation.
* @return The root after the double rotation.
*/
public AvlNode doubleRotateLeftRight(AvlNode u) {
u.left = rotateLeft(u.left);
return rotateRight(u);
}
/**
* 
* @param u The node for the rotation.
* @return The root after the double rotation.
*/
public AvlNode doubleRotateRightLeft(AvlNode u) {
u.right = rotateRight(u.right);
return rotateLeft(u);
}
/***************************** Helper Functions ************************************/
/**
* Returns the successor of a given node in the tree (search recursivly).
* 
* @param q The predecessor.
* @return The successor of node q.
*/
public AvlNode successor(AvlNode q) {
if(q.right!=null) {
AvlNode r = q.right;
while(r.left!=null) {
r = r.left;
}
return r;
} else {
AvlNode p = q.parent;
while(p!=null && q==p.right) {
q = p;
p = q.parent;
}
return p;
}
}
/**
* Calculating the "height" of a node.
* 
* @param cur
* @return The height of a node (-1, if node is not existent eg. NULL).
*/
private int height(AvlNode cur) {
if(cur==null) {
return -1;
}
if(cur.left==null && cur.right==null) {
return 0;
} else if(cur.left==null) {
return 1+height(cur.right);
} else if(cur.right==null) {
return 1+height(cur.left);
} else {
return 1+maximum(height(cur.left),height(cur.right));
}
}
/**
* Return the maximum of two integers.
*/
private int maximum(int a, int b) {
if(a>=b) {
return a;
} else {
return b;
}
}
/** 
* Only for debugging purposes. Gives all information about a node.
* @param n The node to write information about.
*/
public void debug(AvlNode n) {
int l = 0;
int r = 0;
int p = 0;
if(n.left!=null) {
l = n.left.key;
}
if(n.right!=null) {
r = n.right.key;
}
if(n.parent!=null) {
p = n.parent.key;
}
System.out.println("Left: "+l+" Key: "+n+" Right: "+r+" Parent: "+p+" Balance: "+n.balance);
if(n.left!=null) {
debug(n.left);
}
if(n.right!=null) {
debug(n.right);
}
}
private void setBalance(AvlNode cur) {
cur.balance = height(cur.right)-height(cur.left);
}
/**
* Calculates the Inorder traversal of this tree.
* 
* @return A Array-List of the tree in inorder traversal.
*/
final protected ArrayList inorder() {
ArrayList ret = new ArrayList();
inorder(root, ret);
return ret;
}
/**
* Function to calculate inorder recursivly.
* 
* @param n
*            The current node.
* @param io
*            The list to save the inorder traversal.
*/
final protected void inorder(AvlNode n, ArrayList io) {
if (n == null) {
return;
}
inorder(n.left, io);
io.add(n);
inorder(n.right, io);
}
}
/** Here is the AVL-Node class for Completenesse **/
public class AvlNode {
public AvlNode left;
public AvlNode right;
public AvlNode parent;
public int key;
public int balance;
public AvlNode(int k) {
left = right = parent = null;
balance = 0;
key = k;
}
public String toString() {
return "" + key;
}
}
Share

Dieser Eintrag wurde am 4. May 2012 um 22:22 in der Kategorie Java, Programming veröffentlicht. You can book the comments for this article RSS 2.0. Feedback, discussion, commendation and critics are welcome: Write a comment or trackback.


Tags: ,

Warning: Use of undefined constant Ext_related_links - assumed 'Ext_related_links' (this will throw an Error in a future version of PHP) in /home/.sites/609/site1266/web/blackbams-blog/wp-content/themes/SilentWoodsByBlackbam/single.php on line 75

Already 37 comments belonging to "AVL tree implementation in Java":

Kommentare abonnieren (RSS) or URL Trackback

Random Student   says:

on 05. September 2012 at 10:31 on clock


Thanks! This really helped me a lot!

Gil   says:

on 21. November 2012 at 17:31 on clock


There is a typo in the debug helper method: if(n.right!=null) { l = n.right.key; } Should be r - not l

Blackbam     says:

on 21. November 2012 at 20:51 on clock


Thx, you were right.

androw   says:

on 25. December 2012 at 01:47 on clock


where is avlNode class?

Blackbam     says:

on 25. December 2012 at 11:53 on clock


Added it at the bottom of the article.

Maria   says:

on 26. December 2012 at 12:31 on clock


Is there a method to output the AVL tree? as in for e.g 4 3 5 with all the indents and stuff or is it included?

Blackbam     says:

on 02. January 2013 at 09:58 on clock


Hey I think you should just write a class containing a main method to do things like this. The AVL-Tree is working and is my own code, but it was tested in an external framework which I cannot publish here.

YanAbela   says:

on 15. January 2013 at 12:21 on clock


Is updating the tree done in logarithmic time in this example?? if no, how can this be calculated? and if yes can you explain how you checked that it is logarithmic

JOE   says:

on 16. January 2013 at 20:05 on clock


Are the operations done in logarithmic time pls ? If yes , can you explain how do you test this condition?

Blackbam     says:

on 16. January 2013 at 21:23 on clock


Insert operations in an AVL tree can be done in logarithmic time by its definition.

Explanation: The height of the tree is never more than θ log n

eaflores   says:

on 15. February 2013 at 06:22 on clock


Blackbam, do you know C++? If so, could you please help me with my implementation for this in C++? I have re-created your code line by line as C++ code but if fails. Thank You for posting this anyway. I can send you "my" code which is a C++ version of yours.

Blackbam     says:

on 18. February 2013 at 02:56 on clock


Hey there unfortunatly I never had the opportunity of learning C++. But I suppose you have some little mistake which is responsible for the code failing. I just can recommend to debug the class using the "debug" function. A more detailed explanation on this topic you will simply find at Wikipedia.

bhavya   says:

on 23. February 2013 at 20:54 on clock


good post..... helped me a lot.....

min     says:

on 07. March 2013 at 11:31 on clock


Hi Black, i am very new to java.. i know my question is a bit silly. but once we have create the main class.. whats method we should put to call the AVL class ?

min     says:

on 07. March 2013 at 11:54 on clock


I mean how to define main method in this program. Error: Main method not found in class Avltree, please define the main method as: public static void main(String[] args)

Blackbam     says:

on 14. March 2013 at 11:24 on clock


Example:

AvlTree avt1 = new AvlTree();
avt1.insert(15);
avt1.insert(12);
avt1.insert(122);
ArrayList ret = avt1.inorder(); // gives you a list with inorder representation of the tree

and so on. Just write any class "with a main method" which uses the AVL-tree.

Mark Montebello   says:

on 04. April 2013 at 15:20 on clock


how do you display the inorder method by value?

Mark Montebello   says:

on 04. April 2013 at 15:25 on clock


Also do you have an error in your rotations as the root is not shown in inorder?

Blackbam     says:

on 09. April 2013 at 14:16 on clock


Hello Mark, I think this code should be sufficient for own experiments. But if you think there is an error, be free to correct me. I do not think so, but maybe there is one.

Nathan   says:

on 16. April 2013 at 16:01 on clock


Your implementation is NOT log(n). Your height() function recursively iterates over the entire tree in the worst case (on the root node) and this is called several times in insertion/deletion so the worst case time complexity for your insertion/deletion is O(n).

Blackbam     says:

on 27. April 2013 at 11:23 on clock


How would you implement the height function so insertion/deletion are possible in real logarithmic time? You can help me if you show me, how to do better!

Ryno   says:

on 05. May 2013 at 18:08 on clock


thank you for remove method, that's helpfull for me. :)

Abdolsalam   says:

on 15. May 2013 at 09:39 on clock


thank you very much

cnidaria   says:

on 21. May 2013 at 18:13 on clock


how can you use the successor? In the main function I am asking the user to enter an integer to check if it exists in the tree the successor is of type avlnode not integer :/ can you help me please? thank you!!

Blackbam     says:

on 22. May 2013 at 17:43 on clock


The class AvlNode is publicly shown in this tree. You should call System.out.println(AvlNode.key); or something like that.

cnidaria   says:

on 27. May 2013 at 02:47 on clock


thank you!! i mannaged to do it!! :D

cnidaria   says:

on 28. May 2013 at 01:45 on clock


when i'm searching for an int using the successor method. the program is always giving me null.. do you think why this is happening to me?

Ayalasan   says:

on 07. June 2013 at 18:13 on clock


Nice piece of software! Works well. danke! :)

annche   says:

on 08. June 2013 at 13:15 on clock


How to implement AVL tree that left child > parent and right child < parent ? Do you have any suggestion ?

annche   says:

on 08. June 2013 at 13:16 on clock


This site is helpfull :)

Blackbam     says:

on 09. June 2013 at 00:07 on clock


Hello, I do not provide another AVL tree implementation here, but there are a lot of other algorithms you might like for this problems.

You can all check them out here: http://people.ksp.sk/~kuko/bak/

Have fun with implementing ;-)

DarkGab   says:

on 18. June 2013 at 14:46 on clock


To better your implementation and have a logarithmic AVL tree, you must save the height of a node within its fields and only refer to this height not to the method calculating it unless you are updating it, which will require a call the the method. This implies having to update every parent nodes of an added or deleted node, which is logarithmic. the node would be :

public class AvlNode {
public AvlNode left;
public AvlNode right;
public AvlNode parent;
public int key;
public int balance;
public int height;
public AvlNode(int k) {
left = right = parent = null;
balance = 0;
height = 0;
key = k;
}
public String toString() {
return "" + key;
}
}
The height method would be :

private int height(AvlNode cur) {
if(cur==null) {
return -1;
}
if(cur.left==null && cur.right==null) {
return 0;
} else if(cur.left==null) {
return 1+cur.right.height;
} else if(cur.right==null) {
return 1+cur.left.height;
} else {
return 1+maximum(cur.left.height, cur.right.height);
}
}
and after any recursive call modifying a child tree (node) you must update the height as follows :

height = height(this);

houda   says:

on 30. December 2013 at 14:53 on clock


hi co tnkx for this brgrm but i have a pblme always i ts Exception in thread "main" java.lang.StackOverflowError in the méthode setBalance so can u help me pleaaase

manu   says:

on 12. May 2014 at 23:44 on clock


I think you have a mistake in the "public void removeFoundNode (AvlNode q) {" method, because if you have only two elements and eliminates the root, the other element is also deleted. This happens because you compare with the first IF the possibility that the root has a child or none, but it's different when you have a child.

Cth     says:

on 26. February 2015 at 22:43 on clock


what? "we do not use the balance in this class, but the store it anyway" hell, the article's totally pointless without balance checking method.

Blackbam     says:

on 11. April 2015 at 21:46 on clock


Somebody suggested an improvement to balance the tree in the comments.

Random Student   says:

on 04. November 2016 at 01:34 on clock


You have an error in removing a node

Leave a comment: