4. May 2012
von Blackbam

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.key<p.key) {
    if(p.left==null) {
     p.left = q;
     q.parent = p;
     
     // Node is inserted now, continue checking the balance
     recursiveBalance(p);
    } else {
     insertAVL(p.left,q);
    }
   
   } else if(q.key>p.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<q) {
    removeAVL(p.right,q);
   } else if(p.key==q) {
    // we found the node in the tree.. now lets go on!
    removeFoundNode(p);
   }
  }
 }
 
 /**
  * Removes a node from a AVL-Tree, while balancing will be done if necessary.
  *
  * @param q The node to be removed.
  */

 public void removeFoundNode(AvlNode q) {
  AvlNode r;
  // at least one child of q, q will be removed directly
  if(q.left==null || q.right==null) {
   // the root is deleted
   if(q.parent==null) {
    this.root=null;
    q=null;
    return;
   }
   r = q;
  } else {
   // q has two children --> 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<AvlNode> inorder() {
  ArrayList<AvlNode> ret = new ArrayList<AvlNode>();
  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<AvlNode> 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;
 }

}
Share

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.


Tags: ,

Already 36 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!

Random Student   says:

on 21. November 2012 at 17:31 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 21. November 2012 at 20:51 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 25. December 2012 at 01:47 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 25. December 2012 at 11:53 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 26. December 2012 at 12:31 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 02. January 2013 at 09:58 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 15. January 2013 at 12:21 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 16. January 2013 at 20:05 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 16. January 2013 at 21:23 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 15. February 2013 at 06:22 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 18. February 2013 at 02:56 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 23. February 2013 at 20:54 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 07. March 2013 at 11:31 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 07. March 2013 at 11:54 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 14. March 2013 at 11:24 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 04. April 2013 at 15:20 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 04. April 2013 at 15:25 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 09. April 2013 at 14:16 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 16. April 2013 at 16:01 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 27. April 2013 at 11:23 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 05. May 2013 at 18:08 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 15. May 2013 at 09:39 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 21. May 2013 at 18:13 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 22. May 2013 at 17:43 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 27. May 2013 at 02:47 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 28. May 2013 at 01:45 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 07. June 2013 at 18:13 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 08. June 2013 at 13:15 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 08. June 2013 at 13:16 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 09. June 2013 at 00:07 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 18. June 2013 at 14:46 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 30. December 2013 at 14:53 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 12. May 2014 at 23:44 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 26. February 2015 at 22:43 on clock


Thanks! This really helped me a lot!

Random Student   says:

on 11. April 2015 at 21:46 on clock


Thanks! This really helped me a lot!

Leave a comment: