AVL Tree Introduction
A AVL tree is a self-balancing binary search tree where the height difference (balance factor) between left and right subtrees is at most 1 for every node. It ensures O(log n) operations even in worst-case.
Balance Factor = height(left) – height(right). Allowed values: -1, 0, 1.
When insertion/deletion violates balance, we perform rotations:
- Left Rotation – for Right-Right case.
- Right Rotation – for Left-Left case.
- Left-Right Rotation – for Left-Right case (first rotate left on left child, then rotate right on node).
- Right-Left Rotation – for Right-Left case.
AVL tree insertion (simplified outline):
private TreeNode insert(TreeNode node, int val) {
// normal BST insert
// update height
int balance = getBalance(node);
// if unbalanced, perform rotations
if (balance > 1 && val < node.left.val) return rightRotate(node);
if (balance < -1 && val > node.right.val) return leftRotate(node);
if (balance > 1 && val > node.left.val) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
if (balance < -1 && val < node.right.val) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
Two Minute Drill
- AVL tree maintains balance factor -1,0,1.
- Rotations (single/double) restore balance.
- Insertion and deletion require O(log n) time.
- Used when frequent lookups and modifications are needed.
Need more clarification?
Drop us an email at career@quipoinfotech.com