Implementation of the AVL Tree in Java

In computer science, an AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child sub-trees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property.

The following is my implementation of an AVL tree Java library, which supports methods for insertion, deletion, and look-up. The data structure is simple. AVLNode has the following fields:

protected AVLNode left, right, parent;
protected Integer value, height;
private Object object; //An additional field for data to be stored in an AVLNode

And an AVLTree object represents an AVL tree composed of AVLNode objects.

You can download the Java library from http://sites.google.com/site/moderntone/AVLTree.zip




AVLTree.java

package com.avltree;

public class AVLTree {

 private AVLNode root;

 public AVLTree(int... values) {
  for (int value : values)
   insert(value);
 }

 public AVLNode getRoot() {
  return root;
 }

 public void insert(AVLNode node){
  if (root == null)
   root = node;
  else {
   root.insertToLeaf(node);
   AVLNode keyNode = updateHeightsAndDetectKeyNode(node);
   if (keyNode != null) // rotate to adjust the tree
    adjustTreeByRotation(keyNode);
  }
 }
 
 private void insert(int value){
  if (root == null)
   root = new AVLNode(value);
  else {
   AVLNode newNode = new AVLNode(value);
   root.insertToLeaf(newNode);
   AVLNode keyNode = updateHeightsAndDetectKeyNode(newNode);
   if (keyNode != null) // rotate to adjust the tree
    adjustTreeByRotation(keyNode);
  }
 }

 public void delete(AVLNode node){
  int value = node.value;
  delete(value);
 }
 
 public void delete(int value) {
  AVLNode parentOfDeletedLeaf = deleteBeforeAdjustment(value);
  if (parentOfDeletedLeaf != null) {
   AVLNode keyNode = detectKeyNode(parentOfDeletedLeaf);
   if (keyNode != null){
    AVLNode newkeyNode = adjustTreeByRotation(keyNode);
    updateHeights(newkeyNode.parent);
   }
  } else {
   System.out.println("The AVLTree doesn't contain " + value);
  }
 }

 private AVLNode detectKeyNode(AVLNode parentOfDeletedLeaf){
  AVLNode currentNode = parentOfDeletedLeaf;
  while (currentNode != null) {
   int bf = currentNode.getBalanceFactor();
   if (bf == 2 || bf == -2)
    return currentNode;
   else 
    currentNode = currentNode.parent;
  }
  return null;
 }
 
 private AVLNode deleteBeforeAdjustment(int value) {
  AVLNode currentNode = root;
  while (currentNode != null) {
   if (currentNode.value == value)
    break;
   else
    currentNode = value < currentNode.value ? 
     currentNode.left : currentNode.right;
  }

  if (currentNode != null) {
   while (!currentNode.isLeaf()) {
    AVLNode replacement = currentNode.getBalanceFactor() < 0 ? 
     currentNode.right.getLeftmost() : currentNode.left.getRightmost();
    currentNode.value = replacement.value;
    currentNode = replacement;
   }

   AVLNode parent = currentNode.getParent();
   if (parent == null) root = null;
   else if (currentNode == parent.left) 
    parent.setLeft(null);
   else 
    parent.setRight(null);
   updateHeights(parent);
   return parent;
  }
  return null;
 }

 private void updateHeights(AVLNode fromParentOfDeletedLeaf){
  AVLNode currentNode = fromParentOfDeletedLeaf;
  currentNode.adjustHeight();
  while (currentNode != null){
   currentNode.adjustHeight();
   currentNode = currentNode.parent;
  }
 }
 
 /**
  * called by insert(int) keyNode: the node closest to the newly inserted
  * node where |BF|>1
  * @param newNode : newly added leaf AVLNode
  * @return keyNode
  */
 private AVLNode updateHeightsAndDetectKeyNode(AVLNode newNode) {
  AVLNode keyNode = null;
  while (newNode.parent != null) {
   if (newNode.getParent().height - newNode.height != 1) {
    if (keyNode == null) {
     int bf_parent = newNode.getParent().getBalanceFactor();
     if (bf_parent > 1 || bf_parent < -1) {
      keyNode = newNode.getParent();
      break;
     }
    }
    newNode.getParent().height++;
    newNode = newNode.getParent();
   } else
    break;
  }
  return keyNode;
 }

 public AVLNode lookup(int value) {
  AVLNode currentNode = root;
  while (currentNode != null) {
   if (currentNode.value == value)
    return currentNode;
   else
    currentNode = value < currentNode.value ? 
     currentNode.left : currentNode.right;
  }
  System.out.println("The AVLTree doesn't contain " + value);
  return null;
 }

 /**
  * LL or LR type if balance factor == 2; rotateRight for keyNode if bf of
  * keyNode.left == -1, it's LR type; rotateLeft for keyNode.left first RR or
  * RL type if balance factor == -2; rotateLeft for keyNode if bf of
  * keyNode.right == 1, it's RL type; rotateRight for keyNode.right first
  * 
  * @param keyNode
  */
 private AVLNode adjustTreeByRotation(AVLNode keyNode) {
  AVLNode newKeyNode = null;
  int bf_keyNode = keyNode.getBalanceFactor();
  if (bf_keyNode == 2) {
   if (keyNode.left.getBalanceFactor() == -1) // LR
    keyNode.setLeft(keyNode.left.rotateLeft());
   newKeyNode = keyNode.rotateRight();
  } else if (bf_keyNode == -2) {
   if (keyNode.right.getBalanceFactor() == 1) // RL
    keyNode.setRight(keyNode.right.rotateRight());
   newKeyNode = keyNode.rotateLeft();
  } else {
   new Exception("There are some bugs").printStackTrace();
  }

  if (keyNode.parent == null) {
   root = newKeyNode;
   root.parent = null;
  }
  else {
   if (keyNode == keyNode.parent.left)
    keyNode.parent.setLeft(newKeyNode);
   else
    keyNode.parent.setRight(newKeyNode);
   newKeyNode.parent.adjustHeight();
  }
  return newKeyNode;
 }

 public void print(Order order) {
  switch (order) {
  case PREORDER:
   root.print_preorder();
   break;
  case INORDER:
   root.print_inorder();
   break;
  case POSTORDER:
   root.print_postorder();
   break;
  }
 }
}

AVLNode.java

package com.avltree;

public class AVLNode {

 protected AVLNode left, right, parent;
 protected Integer value, height;
 private Object object; //enable the AVLTree to store additional info
 
 public AVLNode(int value){
  this.value = value;
  this.height = 0;
 }
 
 public AVLNode(int value, Object object){
  this.value = value;
  this.height = 0;
  this.object = object;
 }
 
 public AVLNode(AVLNode node){
  this.value = node.value;
  this.height = node.height;
  this.left = node.left;
  this.right = node.right;
 }
 
 public Object getObject() {
  return object;
 }

 public void setObject(Object object) {
  this.object = object;
 }
 
 public int getValue(){
  return value;
 }
 
 public AVLNode getParent() {
  return parent;
 }
 
 public AVLNode getLeft() {
  return left;
 }
 
 protected void setLeft(AVLNode left){
  this.left = left;
  if (left != null)
   left.parent = this;
 }
 
 public AVLNode getRight() {
  return right;
 }
 
 protected void setRight(AVLNode right){
  this.right = right;
  if (right != null)
   right.parent = this;
 }
 
 public int getHeight() {
  return height;
 }
 
 public int getLevel(){
  int level = 0;
  AVLNode currentNode = this;
  while ((currentNode = currentNode.parent) != null)
   level++;
  return level;
 }
 
 protected int getBalanceFactor(){
  int leftHeight = getLeftHeight();
  int rightHeight = getRightHeight();
  return leftHeight - rightHeight;
 }
 
 protected void insertToLeaf(AVLNode node){
  if (node.value == value){
   System.out.println("Duplicate node " + value);
   return;
  }
  else {
   if (node.value < value){
    if (left == null)   setLeft(node);
    else left.insertToLeaf(node);
   }
   else {
    if (right == null) setRight(node);
    else right.insertToLeaf(node);
   }
  }
 }
 
 
 /**rotate right
  * change of height should be added;
  * applies to the LL type situation 
  */
 protected AVLNode rotateRight(){
  AVLNode newRight = new AVLNode(this);
  newRight.height = getRightHeight() + 1;
  newRight.setLeft(left.right);
  left.setRight(newRight);
  left.adjustHeight();
  return left;
 }

 /**
  * rotate left
  * change of height should be added;
  * applies to the LL type situation 
  */
 protected AVLNode rotateLeft(){
  AVLNode newLeft = new AVLNode(this);
  newLeft.height = getLeftHeight() + 1;
  newLeft.setRight(right.left);
  right.setLeft(newLeft);
  right.adjustHeight();
  return right;
 }
 
 protected void adjustHeight(){
  int leftHeight = getLeftHeight();
  int rightHeight = getRightHeight();
  height = (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
 } 
 
 protected int getLeftHeight(){
  return left == null ? -1 : left.height; 
 }
 
 protected int getRightHeight(){
  return right == null ? -1 : right.height;
 }
 
 protected boolean isLeaf(){
  return left == null && right == null;
 }
 
 protected AVLNode getLeftmost(){
  AVLNode leftmost = this;
  while (leftmost.left != null)
   leftmost = leftmost.left;
  return leftmost;
 }
 
 protected AVLNode getRightmost(){
  AVLNode rightmost = this;
  while (rightmost.right != null)
   rightmost = rightmost.right;
  return rightmost;
 }
 
 
 //////////
 protected void print_preorder(){
  System.out.print(value + " ");
  if (left != null) left.print_preorder();
  if (right != null) right.print_preorder();
 }

 protected void print_inorder(){
  if (left != null) left.print_inorder();
  System.out.print(value + " ");
  if (right != null) right.print_inorder();
 }
 
 protected void print_postorder(){
  if (left != null) left.print_postorder();
  if (right != null) right.print_postorder();
  System.out.print(value + " ");
 }
}

Order.java

package com.avltree;

public enum Order{
 PREORDER, INORDER, POSTORDER
}

Test.java

package com.test;

import com.avltree.*;

public class Test {

 public static void main(String[] args) {

//  int[] values = new int[] {23, 18, 12, 8, 14, 20, 44, 52 };
  
  AVLTree tree = new AVLTree(23,18,44,12,20,52,4,14,16); //LR
//  AVLTree tree = new AVLTree(18,12,44,23,52,20,20); //RL 
//  AVLTree tree = new AVLTree(18,20,12,14,8,4); //LL
//  AVLTree tree = new AVLTree(14,12,20,18,23,44); //RR
//  AVLTree tree = new AVLTree(23,18,12);   //simple LL
  
//  AVLTree tree = new AVLTree(50, 20, 80, 10, 30, 60, 90, 70); //test delete
  
  AVLNode root = tree.getRoot();
  System.out.println(root.getValue() + ", with height " + root.getHeight());
  System.out.println(root.getLeft().getValue() + ", with height " + root.getLeft().getHeight());
  System.out.println(root.getRight().getValue() + ", with height " + root.getRight().getHeight());

  System.out.println(root.getLeft().getLeft().getValue() + ", with height " + root.getLeft().getLeft().getHeight());
  System.out.println(root.getRight().getRight().getValue() + ", with height " + root.getRight().getRight().getHeight());

  int toBeDeleted = 90;
  System.out.println("After deleting " + toBeDeleted);
  tree.delete(toBeDeleted);
  System.out.println(root.getValue() + ", with height " + root.getHeight());
  System.out.println(root.getRight().getValue() + ", with height " + root.getRight().getHeight());
//  System.out.println(root.getRight().getRight().getValue() + ", with height " + root.getRight().getRight().getHeight());
//  System.out.println(root.getRight().getLeft().getValue() + ", with height " + root.getRight().getLeft().getHeight());
//  System.out.println(root.getLeft().getRight() == null);
  
  tree.print(Order.PREORDER);

 }
}