Introduction
An AVL tree is a type of binary search tree (BST). It’s a self-balancing BST. It keeps the balance of the tree by keeping the heights of the two child subtrees of any node differing by no more than one. If, at some point, this condition is violated during an insertion or deletion, the tree is rebalanced using one or more tree operations, named rotations.
The AVL tree guarantees that the insertion, deletion, and search operations all take O(log n) time in the worst case, where n is the number of nodes in the tree.
Properties of AVL Tree
Each node in an AVL tree keeps a value called the balance factor. To determine the balance factor, subtract the height of the right subtree from that of the left subtree. It can be -1, 0, or +1 for the tree to remain balanced.
The tree performs specific rotations to maintain this balance:
- Right Rotation (LL Rotation)
- Left Rotation (RR Rotation)
- Left-Right Rotation (LR Rotation)
- Right-Left Rotation (RL Rotation)
Java Implementation of AVL Tree
Here’s a basic implementation of an AVL tree in Java, focusing on insertion and rebalancing:
public class AVLTree {
private class TreeNode {
int value;
int nodeHeight;
TreeNode leftChild;
TreeNode rightChild;
TreeNode(int val) {
this.value = val;
this.nodeHeight = 1;
}
}
private TreeNode rootNode;
private int computeHeight(TreeNode node) {
if (node == null) return 0;
return node.nodeHeight;
}
private int calculateBalance(TreeNode node) {
if (node == null) return 0;
return computeHeight(node.leftChild) - computeHeight(node.rightChild);
}
private TreeNode rotateR(TreeNode y) {
TreeNode x = y.leftChild;
TreeNode temp = x.rightChild;
x.rightChild = y;
y.leftChild = temp;
y.nodeHeight = 1 + Math.max(computeHeight(y.leftChild), computeHeight(y.rightChild));
x.nodeHeight = 1 + Math.max(computeHeight(x.leftChild), computeHeight(x.rightChild));
return x;
}
private TreeNode rotateL(TreeNode x) {
TreeNode y = x.rightChild;
TreeNode temp = y.leftChild;
y.leftChild = x;
x.rightChild = temp;
x.nodeHeight = 1 + Math.max(computeHeight(x.leftChild), computeHeight(x.rightChild));
y.nodeHeight = 1 + Math.max(computeHeight(y.leftChild), computeHeight(y.rightChild));
return y;
}
private TreeNode addNode(TreeNode node, int newValue) {
if (node == null) {
return new TreeNode(newValue);
}
if (newValue < node.value) {
node.leftChild = addNode(node.leftChild, newValue);
} else if (newValue > node.value) {
node.rightChild = addNode(node.rightChild, newValue);
} else {
// Duplicate values not allowed
return node;
}
node.nodeHeight = 1 + Math.max(computeHeight(node.leftChild), computeHeight(node.rightChild));
int balance = calculateBalance(node);
if (balance > 1 && newValue < node.leftChild.value)
return rotateR(node);
if (balance < -1 && newValue > node.rightChild.value)
return rotateL(node);
if (balance > 1 && newValue > node.leftChild.value) {
node.leftChild = rotateL(node.leftChild);
return rotateR(node);
}
if (balance < -1 && newValue < node.rightChild.value) {
node.rightChild = rotateR(node.rightChild);
return rotateL(node);
}
return node;
}
public void insert(int value) {
rootNode = addNode(rootNode, value);
}
public void displayInOrder() {
traverseInOrder(rootNode);
System.out.println();
}
private void traverseInOrder(TreeNode current) {
if (current != null) {
traverseInOrder(current.leftChild);
System.out.print(current.value + " ");
traverseInOrder(current.rightChild);
}
}
public static void main(String[] args) {
AVLTree avl = new AVLTree();
avl.insert(25);
avl.insert(15);
avl.insert(30);
avl.insert(10);
System.out.print("AVL In-order: ");
avl.displayInOrder(); // Expected Output: 10 15 25 30
}
}
AVL Tree Example Explanation
In the example above, the program builds an AVL tree by inserting the values 30, 20, 40, and 10. As each node is inserted, the tree may perform rotations to ensure balance. The in-order traversal at the end prints the tree contents in sorted order.
Conclusion
AVL trees are a powerful data structure that maintains balance without sacrificing performance. Their automatic rebalancing ensures that operations remain efficient even in the worst case. While the implementation may appear more complex than a standard BST, the performance gains in large-scale applications make it a worthwhile investment.
You can find the example code on Github.