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;
}
}