
Blackbams Blog
development – digital arts – internet
Knowledge is free. No one may take possession of it.
4. May 2012
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;
}
}
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.
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
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 : The height method would be : and after any recursive call modifying a child tree (node) you must update the height as follows :
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: