Home

Implementing AVL trees in Java

Although there are many different ways to implement AVL trees, as of 2017 there are many c language implementations and few, usually only very similar recursive implementations in Java (the recursive CS textbook version). While the recursive solution is elegant and good for academic purposes, most do not make some optimizations that are simple in an iterative environment (after one single or double rotation on insert rebalancing is complete).

Traditionally, AVL trees are implemented by maintaining or calculating the balance factor at each node: From the Wikipedia

BalanceFactor(N) := Height(RightSubtree(N)) - Height(LeftSubtree(N)) within a specific range BalanceFactor(N) ∈ {–1,0,+1}

Each node in an AVL tree can either store the height of each subtree and continuously calculate the balance factor during rebalancing or each node can store the result of that calculation (-1,0,+1) and increment or decrement that value as necessary during insertions, deletions and rotations.

This project has an AVL tree implementation in Java using balance factor, parent references and no recursion. The code for re-tracing after insertion checks and maintains balance factors in this fashion:

private void fixAfterInsertion(Entry<K, V> x) {
while (x.balance != 0) {
    if (x.balance == 2) { // right heavy by 2?
	if (x.right.balance == 1) {
	    x.balance = 0;
	    x.right.balance = 0;
	    rotateLeft(x);

Later research demonstrated a new way to define and implement AVL trees, instead of balance factor as the difference in height of the child nodes, rank and rank difference are used. Rank is equivalent to height for AVL trees and rank difference is the difference in height with the parent node. All nodes in an AVL tree must have a rank difference of 1 or 2. When rank is stored at each node (equivalent to height for AVL trees) the code for retracing after insertion is fairly simple.

private void fixAfterInsertion(Entry<K, V> x) {
x.rank++;
while (x.parent != null && x.rank + 1 != x.parent.rank) {
    Entry<K, V> p = x.parent;
    if (p.left == x) { // parent's left node == this so check the left side
	if (needToRotateLeftHeavy(p)) {
	    if (x.right != null && (x.rank - x.right.rank) == 1) {
		x.rank--;
		x.right.rank++;
		rotateLeft(x);
	    }
	    p.rank--;
	    rotateRight(p);
	    break;
	}
    } else {
	if (needToRotateRightHeavy(p)) {
	    if (x.left != null && (x.rank - x.left.rank) == 1) {
		x.rank--;
		x.left.rank++;
		rotateRight(x);
	    }
	    p.rank--;
	    rotateLeft(p);
	    break;
	}
    }

    x = x.parent;
    x.rank++;
}
}

However, when one bit per node is used to store the rank difference of 1 or 2 instead of the height, the code for retracing is about 2x longer and requires solid unit testing to verify correctness.

Implementing WAVL trees

WAVL(Weak-AVL) trees are an attempt to get the best characteristics of both AVL and red-black trees. This library offers an implementations of WAVL trees too.