**AVL Tree Tutorial**

This tutorial will cover designing an AVL Tree data structure. An AVL Tree is a self-balancing binary search tree. This means that the heights of a given node's children trees are either the same or they differ by one. This is accomplished by rotating the tree nodes. Because the AVL Tree is self-balancing, all of its operations (insertion, lookup, and removal) all operate in O(log(n)) time.

Let's start by taking a look at the AVLNode class. It is a standard binary tree node, with a height() method, which is used in calculating the balance factor between two subtrees of a parent AVLNode. Also since this is a binary search tree, all the elements must be mutually Comparable, as denoted by the generic parametrization <E extends Comparable<? super E>>.

/** * @author: Michael Levet * @date: 6/20/2011 * * This class represents a Node in an AVLTree, which is a * balanced binary search tree. As such, all the AVLNodes must be * mutually Comparable to properly order the elements. Each AVLNode * also maintains the balance factor for its subtrees. A balance factor * less than 0 indicates more elements to the left of this AVLNode, and a * balance factor greater than 0 indicates more elements to the right of * this AVLNode. * */ public class AVLNode<E extends Comparable<? super E>> { private AVLNode<E> left, right; private E element; //the default constructor used to initialize //this AVLNode with a null element public AVLNode(){ this(null); } /** * @param element: The element this AVLNode is encapsulating * * The left and right children are initialized as empty. ***/ public AVLNode(E element){ this.element = element; left = right = null; } public E getElement(){ return element; } public void setElement(E element){ this.element = element; } public AVLNode<E> getLeft(){ return left; } public AVLNode<E> getRight(){ return right; } //the setLeft() and setRight() functions //simply set the elements for the left and right //AVLNodes. the actual ordering is handled by the //AVLTree class public void setLeft(E element){ if(left == null) this.left = new AVLNode<E>(element); else this.left.setElement(element); } public void setRight(E element){ if(right == null) this.right = new AVLNode<E>(element); else this.right.setElement(element); } public void setLeftNode(AVLNode<E> temp){ this.left = temp; } public void setRightNode(AVLNode<E> temp){ this.right = temp; } public int getBalance(){ int leftHeight = (left == null)?0:left.height(); int rightHeight = (right == null)?0:right.height(); return rightHeight - leftHeight; } private int height(){ int leftHeight = (left == null)?0:left.height(); int rightHeight = (right == null)?0:right.height(); return 1 + Math.max(leftHeight, rightHeight); } public String toString(){ return assemble(this, 0); } private String assemble(AVLNode<E> temp, int offset){ String ret= ""; for(int i = 0; i < offset; i++) ret += "\t"; ret += temp.getElement() + "\n"; if(temp.getLeft() != null){ ret += "Left: " + assemble(temp.getLeft(), offset + 1); } if(temp.getRight() != null){ ret += "Right: " + assemble(temp.getRight(), offset + 1); } return ret; } }

Next, let's take a look at the AVLTree. Like all trees, it supports the three basic operations: insertion, removal, and lookup. These will be the operations covered in this tutorial.

So for the AVLTree has a pretty standard setup for a binary search tree. The elements must be mutually Comparable, and the AVLTree is rooted. One thing to note is that the AVLNode instance field is called "rootAbove." This AVLNode's left child will point to the root node of the tree. Thus, the actual Tree structure being manipulated is actually a subtree of a placeholder node. Since the parent node's pointer is updated after a rotation, having an "invisible" parent for the root node simplifies things.

public class AVLTree<E extends Comparable<? super E>> { private AVLNode<E> rootAbove; public AVLTree(){ rootAbove = new AVLNode<E>(); }

Since balancing is a key component of the AVL Tree, let's examine the rotation functionality used to accomplish this. Binary tree rotations work by moving a child node b up to its parent's level, and making the parent node a child node. When this happens, the new parent node has an extra child, and the new child node has one fewer children. So to fix this, one of the new parent's children is set as a child of the old parent node.

Let's see this in action, with the following Tree:

5 / \ 4 7 / \ 6 9 / 8

Now when this Tree is initially rotated to the right, it looks like:

7 / | \ 5 6 9 | | 4 8

An AVL Tree is a binary search tree though, so each node can have at most two children. The new root (7) has three children, and the old root (5) only has one child. So to satisfy the binary search tree property, the 6 is removed from the 7 and set as the 5 node's right child. The Tree now looks like:

7 / \ 5 9 / \ / 4 6 8

In fact, there are four specific cases to consider when rotating an AVL Tree. The first two include the left or right sides containing both the child and grandchildren nodes. Examples of such trees are shown below. In either of these cases, simply rotating the child node of the root will balance the tree.

//left-left //right-right 5 3 / \ 4 4 / \ 3 5

The other two cases are where the grandchildren nodes are on the opposite sides of the child nodes. That is, in the Trees shown above, in the left tree, the 4 Node would have a right child; and in the right tree, the 4 would have a left child. These cases are balanced by rotating the grandchildren nodes up two levels.

//left-right //right-left 6 6 / \ 4 5 \ / 5 4

Below is the code used to rotate a subtree. Not only is the subtree (rotateBase) important, but the parent of rotateBase is vital because it is used to update its child pointer to the new root of the subtree. Here, cases one and two described above are the base cases of this method. For cases three and four, the double rotations, the first rotation is performed to set the subtree up for either cases one or two. Then a recursive call is made to the rotate() method to have cases one and two executed.

/** * @param rotateBase: The root of the subtree that is being rotated * @param rootAbove: The AVLNode that points to rotateBase * * This method rotates the subtree balancing it to within a margin of |1|. * */ public void rotate(AVLNode<E> rotateBase, AVLNode<E> rootAbove){ int balance = rotateBase.getBalance(); if(Math.abs(balance) < 2){ System.out.println("No rotate"); } //gets the child on the side with the greater height AVLNode<E> child = (balance < 0) ? rotateBase.getLeft() : rotateBase.getRight(); if(child == null) return; int childBalance = child.getBalance(); AVLNode<E> grandChild = null; //both the child and grandchild are on the //left side, so rotate the child up to the root position if(balance < -1 && childBalance < 0){ if(rootAbove != this.rootAbove && rootAbove.getRight() == rotateBase){ rootAbove.setRightNode(child); } else{ rootAbove.setLeftNode(child); } grandChild = child.getRight(); child.setRightNode(rotateBase); rotateBase.setLeftNode(grandChild); return; } //both the child and the grandchild are on the //right side, so rotate the child up to the root position else if(balance > 1 && childBalance > 0){ if(rootAbove != this.rootAbove && rootAbove.getRight() == rotateBase){ rootAbove.setRightNode(child); } else{ rootAbove.setLeftNode(child); } grandChild = child.getLeft(); child.setLeftNode(rotateBase); rotateBase.setRightNode(grandChild); return; } //the child is on the left side, but the grandchild is on the //right side, so rotate the grandchild up to the child position //so the condition of the first if statement is satisfied, //then recurse to have the first if statement evaluated else if(balance < -1 && childBalance > 0){ grandChild = child.getRight(); rotateBase.setLeftNode(grandChild); child.setRightNode(grandChild.getLeft()); grandChild.setLeftNode(child); rotate(rotateBase, rootAbove); return; } //the child is on the right side, but the grandchild is on the //left side, so rotate the grandchild up to the child position //so the condition of the second if statement is satisfied, //then recurse to have the second if statement evaluated else if(balance > 1 && childBalance < 0){ grandChild = child.getLeft(); rotateBase.setRightNode(grandChild); child.setLeftNode(grandChild.getRight()); grandChild.setRightNode(child); rotate(rotateBase, rootAbove); return; } }

The first operation to examine is inserting elements into the tree. AVLTree insertions work exactly like standard binary search tree insertions. Each AVLNode that is recursively traversed according to the relation of the element to insert in comparison to the element of the given AVLNode. Once the bottom of the AVLTree has been reached, the element is inserted. After the actual insertion, the subtrees are recursively rebalanced from the bottom up based on the recursive insert() calls.

/** * @param element: The element to insert into the Tree * * This method invokes a private helper method to insert the element. * It passes the root as the place to start. * */ public void insert(E element){ insert(element, rootAbove.getLeft()); } /** * @param element: The element to insert into the Tree * @param temp: The AVLNode to evaluate for recursive insertion * * This method recursively traverses the Tree, inserting the * element at the appropriate spot and incrementing the balance * factors for the subtrees as it evaluates. The Tree will then * recursively rebalance as necessary. * */ private void insert(E element, AVLNode<E> temp){ if(this.rootAbove.getLeft() == null){ this.rootAbove.setLeftNode(new AVLNode<E>(element)); return; } //travel left or right based on the //comparison of element to temp.element //remember that left means that element <= temp.element //and right means element > temp.element int compare = element.compareTo(temp.getElement()); //travel to the left of the Tree, inserting //if the bottom has been reached if(compare <= 0){ //System.out.println(temp.getLeft()); if(temp.getLeft() == null){ temp.setLeft(element); return; } insert(element, temp.getLeft()); } //otherwise, travelling to the right of the Tree, //inserting if the bottom has been reached else{ if(temp.getRight() == null){ temp.setRight(element); return; } insert(element, temp.getRight()); } //if the root is being evaluated it, rotate if necessary if(temp == rootAbove.getLeft()){ rotate(rootAbove.getLeft(), rootAbove); } //otherwise, rotate the left and right subtrees //as necessary if(temp.getLeft() != null){ rotate(temp.getLeft(), temp); } if(temp.getRight() != null){ rotate(temp.getRight(), temp); } } //end insert

The next operation to examine is the remove() method. It works by traversing the AVLTree in search of the element. Once the element is found, it is removed and replaced with either the farthest right Node on the left hand side of the element, or the farthest left Node on the right-hand side of the element based on whichever side has the greater height. Each of these Nodes can have at most one child, on the opposite side of the traversal (ie., the right Ndoe can have a left child, and vice versa). This helps ensure not only the balance of the subtree, but also that the replacement will be less than the element's right child and greater than its left child.

Let's look at an example to better understand the concept. Below is a basic AVL Tree. In order to remove 60, a successor needs to be found such that 54 is less than it, and 66 is greater than it. Because the left side has the greater weight, the far-right child (57) is the new successor. Since 57 has a child, the 54 right node now points to 55, and 57 becomes the new root.

Before removing 60 60 / \ 54 66 / \ \ 51 57 70 / 55

After removing 60 57 / \ 54 66 / \ \ 51 55 70

Finally, let's examine the code to remove an element from an AVLTree:

/** * @param element: The element to remove from the AVLTree * @param temp: The root node of the subtree * * This method recursively traverses the AVLTree based on * the ordering of the element with respect to the Tree's * elements. If the element is not found, then nothing happens. * Otherwise, the element is removed, and either the far-right * element on its left child or the far left element on its right * child replaces it. ***/ private void remove(E element, AVLNode<E> temp){ if(temp == null) return; int compare = 0; if(temp != rootAbove) compare = element.compareTo(temp.getElement()); boolean direction = (compare > 0 && temp != rootAbove); AVLNode<E> child = direction ? temp.getRight() : temp.getLeft(); if(child == null) return; //if the root is perfectly balanced, slide the left Node up //and reinsert the left.right element if necessary if(temp == rootAbove && child.getBalance() == 0 && child.getElement().equals(element)){ AVLNode<E> newRoot = child.getLeft(); if(newRoot == null){ rootAbove.setLeftNode(null); return; } else{ enactRemoval(temp, child, false); return; } } //if the element is found and the root is not // perfectly balanced, remove it using enactRemoval() else if(element.compareTo(child.getElement()) == 0){ enactRemoval(temp, child, direction); } //otherwise, recursively traverse the tree else{ remove(element, child); } } /** * @param parent: The parent of the element to be removed * @param remove: The element to remove from the Tree * @param direction: false if remove is to the left of parent, true otherwise * * This method physically removes the AVLNode with the element from the * AVLTree, replacing it with the appropriate successor. ***/ private void enactRemoval(AVLNode<E> parent, AVLNode<E> remove, boolean direction){ AVLNode<E> temp = null; AVLNode<E> left = remove.getLeft(); AVLNode<E> right = remove.getRight(); //if the Node to remove is not a leaf, find the appropriate successor if(left != null || right != null){ temp = findSuccessor(remove); } //if remove is the right child of parent, update parent's right node if(direction && (parent != rootAbove)){ parent.setRightNode(temp); } //otherwise, update its left node with the successor else parent.setLeftNode(temp); //and update temp to point to remove's children if(temp != null){ if(temp != left){ temp.setLeftNode(remove.getLeft()); } if(temp != right){ temp.setRightNode(remove.getRight()); } } //and finally, discard those references from remove //so that the removed Node is garbage collected sooner remove.setLeftNode(null); remove.setRightNode(null); } /** * @param root: The element for which to find a successor AVLNode * @return AVLNode<E>: The successor Node ***/ private AVLNode<E> findSuccessor(AVLNode<E> root){ AVLNode<E> temp = root; AVLNode<E> parent = null; //if the balance favors the right, traverse right //otherwise, traverse left boolean direction = (temp.getBalance() > 0); parent = temp; temp = (direction) ? temp.getRight() : temp.getLeft(); if(temp == null) return temp; //and find the farthest left-Node on the right side, //or the farthest right-Node on the left side while((temp.getRight() != null && !direction ) || (temp.getLeft() != null && direction)){ parent = temp; temp = (direction) ? temp.getLeft() : temp.getRight(); } //finally, update the successor's parent's references //to adjust for a left child on the right node, or a right //child on the left-node if(temp == parent.getLeft()){ parent.setLeftNode(temp.getRight()); temp.setRightNode(null); } else{ parent.setRightNode(temp.getLeft()); temp.setLeftNode(null); } return temp; }

The final operation to examine is the simplest one- lookup. The contains() method is a standard binary search tree lookup method, traversing the AVLTree based on element's relations to the various AVLNodes until either a match is found or it hits the bottom of the AVLTree.

/** * @param element: The element to search for in the AVLTree * @return boolean: true if the element is found, false otherwise * * The contains method simply traverses the binary search tree based on * element's relation to the AVLNodes in the Tree until a match is found * or it hits the bottom of the Tree. * */ public boolean contains(E element){ AVLNode<E> temp = rootAbove.getLeft(); while(temp != null){ if(temp.getElement().equals(element)) return true; int balance = element.compareTo(temp.getElement()); temp = (balance < 0) ? temp.getLeft() : temp.getRight(); } return false; }

**Conclusion**

In conclusion, AVL Trees are very simple binary search trees that use a clever technique to rotate the tree and maintain balance, thus allowing for O(log(n)) insertion, removal and lookup time.