This is the code for AVL tree. You need to fill in the code for insert that calls balancing methods. You also need to fill in the code for the balancing methods (one in class, and the remaining three in the problem set).

public class AVLNode {
    private AVLNode left, right;
    private Comparable data;
    private int leftHeight;
    private int rightHeight;
    private AVLTree tree; //the tree that the node belongs to
    // 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;
    }

    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 returns 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 returns 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 returns 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;
    }
	
    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("In-order:");
	avl.inOrder();

	System.out.println("Pre-order:");
	avl.preOrder();
    }

}


This is an example from CSci 2101 course.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.