4. May 2012

# || AVL tree implementation in Java

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);
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 #### 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 #### 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