This is the code for AVL tree. Contains only one balancing method so far.
public class AVLNode {
private AVLNode left, right;
private Comparable data;
private int leftHeight;
private int rightHeight;
private AVLTree tree;
// true if running in a testing mode, false otherwise
// if false, no priting will be done
private boolean testing = true;
public AVLNode(Comparable data, AVLTree tree){
this.data = data;
this.tree = tree;
}
public AVLNode getLeft(){
return left;
}
public AVLNode getRight(){
return right;
}
public void setLeft(AVLNode left){
this.left = left;
}
public void setRight(AVLNode right){
this.right = right;
}
public Comparable getData() {
return data;
}
// not sure if we need it
public void setData(Comparable data) {
this.data = data;
}
public void inOrder() {
if (left != null) left.inOrder();
System.out.println(data);
if (right != null) right.inOrder();
}
public void preOrder() {
System.out.println(data);
if (left != null) left.preOrder();
if (right != null) right.preOrder();
}
public int getBalance() {
// the absolute value of the height difference
return Math.abs(leftHeight - rightHeight);
}
// recursive insert. Takes a parent node. Returns the height of the
// tree rooted at this node
// Performs all necessary rebalancing
public int insert(Comparable data, AVLNode parent) {
if (data.compareTo(this.data) < 0) {
if (left != null) {
leftHeight = left.insert(data, this);
} else {
// left is null, inserting the node at the left
left = new AVLNode(data, tree);
leftHeight = 1;
}
} else {
if (right != null) {
rightHeight = right.insert(data, this);
} else {
// right is null, inserting the node at the right
right = new AVLNode(data, tree);
rightHeight = 1;
}
}
// rebalance the tree if needed
if (getBalance() == 2) {
testPrint("Need to rebalance");
// figure out which of the four cases take place
if (data.compareTo(this.data) < 0) {
testPrint("data = " + data + " this.data = " +
this.data + " left.data " + left.getData());
// if the data was inserted to the left
if (data.compareTo(left.getData()) < 0) {
// single R rotation
testPrint("single R");
return singleR(data, parent);
} else {
// zigzag: LR rotation
testPrint("double LR");
return doubleLR(data, parent);
}
} else {
// if the data was inserted to the right
if (data.compareTo(right.data) > 0) {
// single L rotation
testPrint("single L");
return singleL(data, parent);
} else {
// zigzag: RL rotation
testPrint("double RL");
return doubleRL(data, parent);
}
}
}
return 1 + Math.max(leftHeight,rightHeight);
}
// performs a single right rotation
// returns the height of the new subtree
// Assume that this is the rotation that needs to be performed
private int singleR(Comparable data, AVLNode parent) {
// saving away a reference to the left node
AVLNode myleft = left;
// rearranging the tree
left = left.right;
myleft.right = this;
// resetting the heights of the changed nodes
leftHeight = myleft.rightHeight;
myleft.rightHeight = Math.max(leftHeight, rightHeight) + 1;
// if this node is not the root, reset the parent's
// reference and height
if (parent != null) {
// we don't know if this node is the left child of its parent or
// the right one, need both cases
if (parent.left == this) {
// if this node is the left child of its parent
parent.left = myleft;
parent.leftHeight = Math.max(myleft.leftHeight,
myleft.rightHeight) + 1;
} else {
// this node is the right child of its parent
parent.right = myleft;
parent.rightHeight = Math.max(myleft.leftHeight,
myleft.rightHeight) + 1;
}
} else {
// this node is the root, has no parent
// need to reset the root reference of the tree
tree.setRoot(myleft);
}
// the height of the tree rooted at myleft (new root)
return 1 + Math.max(myleft.leftHeight,myleft.rightHeight);
}
private int singleL(Comparable data, AVLNode parent) {
// this stub needs to be replaced by real code
// now it reurns the height of the tree rooted at this node
return 1 + Math.max(leftHeight,rightHeight);
}
private int doubleLR(Comparable data, AVLNode parent) {
// this stub needs to be replaced by real code
// now it reurns the height of the tree rooted at this node
return 1 + Math.max(leftHeight,rightHeight);
}
private int doubleRL(Comparable data, AVLNode parent) {
// this stub needs to be replaced by real code
// now it reurns the height of the tree rooted at this node
return 1 + Math.max(leftHeight,rightHeight);
}
// prints only when in testing mode
private void testPrint(String s) {
if (testing) {
System.out.println(s);
}
}
}
public class AVLTree {
private AVLNode root;
public AVLTree() {
}
public boolean isEmpty() {
return (root == null);
}
public AVLNode getRoot(){
return root;
}
public AVLNode search(Comparable data) {
AVLNode node = root;
while (node != null && data.compareTo(node.getData()) != 0){
if (data.compareTo(node.getData()) < 0){
node = node.getLeft();
} else {
node = node.getRight();
}
}
return node;
}
// recursive insert
public int insert(Comparable data) {
if (root == null) {
root = new AVLNode(data, this);
return 1;
}
return root.insert(data, null);
}
public void setRoot(AVLNode newroot) {
root = newroot;
}
/*
// insert the data into the binary serach tree
// return the reference to the new node containing data
// if there already is such a node, return null
public AVLNode insert(Comparable data) {
if(!isEmpty()){
AVLNode parent = getRoot();
AVLNode child;
if (data.compareTo(parent.getData()) == 0) {
return null;
}
if(data.compareTo(parent.getData()) < 0){
child = parent.getLeft();
} else {
child = parent.getRight();
}
while(child != null){
if(data.compareTo(child.getData()) < 0){
parent = child;
child = child.getLeft();
}
else if (data.compareTo(child.getData()) > 0) {
parent = child;
child = child.getRight();
}
else return null;
}
AVLNode node = new AVLNode(data);
if(data.compareTo(parent.getData()) > 0 ){
parent.setRight(node);
}
else{
parent.setLeft(node);
}
return node;
}
// if the tree is empty
AVLNode node = new AVLNode(data);
root = node;
return node;
}*/
public void inOrder() {
if (root != null) root.inOrder();
}
public void preOrder() {
if (root != null) root.preOrder();
}
}
public class AVLTest {
public static void main(String [] args) {
AVLTree avl = new AVLTree();
String [] strings = {"tomatoes", "strawberries","oranges", "kiwi", "apples"
//"grapes", "cucumbers", "apples", "kiwi", "tomatoes"
//"strawberries", "bananas", "oranges",
//"pumpkins"
};
for (int i = 0; i < strings.length; ++i) {
System.out.println(avl.insert(strings[i]));
}
/*
System.out.println("Searching....");
for (int i = 0; i < strings.length; ++i) {
System.out.println(avl.search(strings[i]).getData());
}*/
System.out.println("In-order:");
avl.inOrder();
System.out.println("Pre-order:");
avl.preOrder();
}
}
This is an example from CSci 2101 course.