← Back to DSA Course | Chapter 11: Trees | Lesson 6 of 10

AVL Tree

In this page:

  1. AVL Idea
  2. Rotations
  3. Four Cases
  4. Double Rotations
  5. AVL Practice

AVL Idea

An AVL tree is a binary search tree that automatically keeps itself balanced, guaranteeing that the height difference between any node's left and right subtrees never exceeds one. This prevents the worst-case degradation a plain BST can suffer when built from sorted input.

Example: AVL Idea

#include <iostream>
using namespace std;
struct Node { int val, height; Node *left, *right; };
int h(Node* n) { return n ? n->height : 0; }
int balance(Node* n) { return n ? h(n->left) - h(n->right) : 0; }
int main() {
    Node l={3,1,nullptr,nullptr}, r={8,1,nullptr,nullptr};
    Node root={5,2,&l,&r};
    cout << "Balance factor: " << balance(&root) << " (must stay in [-1,1])" << endl;
    return 0;
}
public class Main {
    static class Node { int val, height; Node left, right; Node(int v){val=v;height=1;} }
    static int h(Node n) { return n == null ? 0 : n.height; }
    static int balance(Node n) { return n == null ? 0 : h(n.left) - h(n.right); }
    public static void main(String[] args) {
        Node root = new Node(5); root.height = 2;
        root.left = new Node(3); root.right = new Node(8);
        System.out.println("Balance factor: " + balance(root) + " (must stay in [-1,1])");
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.height = 1; self.left = None; self.right = None

def h(n):
    return n.height if n else 0

def balance(n):
    return h(n.left) - h(n.right) if n else 0

root = Node(5); root.height = 2
root.left = Node(3); root.right = Node(8)
print("Balance factor:", balance(root), "(must stay in [-1,1])")
#include <stdio.h>
#include <stddef.h>
struct Node { int val, height; struct Node *left, *right; };
int h(struct Node* n) { return n ? n->height : 0; }
int balance(struct Node* n) { return n ? h(n->left) - h(n->right) : 0; }
int main() {
    struct Node l={3,1,NULL,NULL}, r={8,1,NULL,NULL};
    struct Node root={5,2,&l,&r};
    printf("Balance factor: %d (must stay in [-1,1])\n", balance(&root));
    return 0;
}

Rotations

Whenever an insertion or deletion pushes a subtree's balance out of that allowed range, the tree performs a rotation — a local restructuring of a few nodes — to restore the balance property without changing the tree's overall sorted order.

Example: Rotations

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
Node* rotateLeft(Node* x) {
    Node* y = x->right;
    x->right = y->left;
    y->left = x;
    return y;
}
int main() {
    Node* c = new Node{30, nullptr, nullptr};
    Node* b = new Node{20, nullptr, c};
    Node* newRoot = rotateLeft(b);
    cout << "After left rotation, new subtree root: " << newRoot->val << endl;
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static Node rotateLeft(Node x) {
        Node y = x.right;
        x.right = y.left;
        y.left = x;
        return y;
    }
    public static void main(String[] args) {
        Node b = new Node(20);
        b.right = new Node(30);
        Node newRoot = rotateLeft(b);
        System.out.println("After left rotation, new subtree root: " + newRoot.val);
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

def rotate_left(x):
    y = x.right
    x.right = y.left
    y.left = x
    return y

b = Node(20)
b.right = Node(30)
new_root = rotate_left(b)
print("After left rotation, new subtree root:", new_root.val)
#include <stdio.h>
#include <stdlib.h>
struct Node { int val; struct Node *left, *right; };
struct Node* rotateLeft(struct Node* x) {
    struct Node* y = x->right;
    x->right = y->left;
    y->left = x;
    return y;
}
int main() {
    struct Node* c = malloc(sizeof(struct Node)); c->val=30; c->left=c->right=NULL;
    struct Node* b = malloc(sizeof(struct Node)); b->val=20; b->left=NULL; b->right=c;
    struct Node* newRoot = rotateLeft(b);
    printf("After left rotation, new subtree root: %d\n", newRoot->val);
    return 0;
}

Four Cases

There are four rotation cases depending on which side is unbalanced and where the offending node sits: left-left, right-right, left-right, and right-left, each named for the direction of the imbalance and any zigzag shape involved.

Example: Four Cases

#include <iostream>
using namespace std;
int main() {
    cout << "Left-Left, Right-Right, Left-Right, Right-Left -- named after the path of the two unbalancing insertions" << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        System.out.println("Left-Left, Right-Right, Left-Right, Right-Left -- named after the path of the two unbalancing insertions");
    }
}
print("Left-Left, Right-Right, Left-Right, Right-Left -- named after the path of the two unbalancing insertions")
#include <stdio.h>
int main() {
    printf("Left-Left, Right-Right, Left-Right, Right-Left -- named after the path of the two unbalancing insertions\n");
    return 0;
}

Double Rotations

The left-right and right-left cases are 'double rotations' — they require two separate single rotations performed in sequence to fully restore balance, whereas the left-left and right-right cases only need one rotation each.

Example: Double Rotations

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
Node* rotateRight(Node* y) { Node* x = y->left; y->left = x->right; x->right = y; return x; }
Node* rotateLeft(Node* x) { Node* y = x->right; x->right = y->left; y->left = x; return y; }
int main() {
    Node* c = new Node{25, nullptr, nullptr};
    Node* b = new Node{10, nullptr, c};
    Node* a = new Node{30, b, nullptr};
    a->left = rotateLeft(b);
    Node* newRoot = rotateRight(a);
    cout << "Left-Right case: rotate left on child, then right on root -> " << newRoot->val << endl;
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static Node rotateRight(Node y) { Node x = y.left; y.left = x.right; x.right = y; return x; }
    static Node rotateLeft(Node x) { Node y = x.right; x.right = y.left; y.left = x; return y; }
    public static void main(String[] args) {
        Node a = new Node(30);
        a.left = new Node(10);
        a.left.right = new Node(25);
        a.left = rotateLeft(a.left);
        Node newRoot = rotateRight(a);
        System.out.println("Left-Right case: rotate left on child, then right on root -> " + newRoot.val);
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

def rotate_right(y):
    x = y.left; y.left = x.right; x.right = y
    return x

def rotate_left(x):
    y = x.right; x.right = y.left; y.left = x
    return y

a = Node(30)
a.left = Node(10)
a.left.right = Node(25)
a.left = rotate_left(a.left)
new_root = rotate_right(a)
print("Left-Right case: rotate left on child, then right on root ->", new_root.val)
#include <stdio.h>
#include <stdlib.h>
struct Node { int val; struct Node *left, *right; };
struct Node* rotateRight(struct Node* y) { struct Node* x = y->left; y->left = x->right; x->right = y; return x; }
struct Node* rotateLeft(struct Node* x) { struct Node* y = x->right; x->right = y->left; y->left = x; return y; }
int main() {
    struct Node* c = malloc(sizeof(struct Node)); c->val=25; c->left=c->right=NULL;
    struct Node* b = malloc(sizeof(struct Node)); b->val=10; b->left=NULL; b->right=c;
    struct Node* a = malloc(sizeof(struct Node)); a->val=30; a->left=b; a->right=NULL;
    a->left = rotateLeft(b);
    struct Node* newRoot = rotateRight(a);
    printf("Left-Right case: rotate left on child, then right on root -> %d\n", newRoot->val);
    return 0;
}

AVL Practice

By keeping the tree height at O(log n) no matter what order values are inserted or deleted, AVL trees guarantee that search, insertion, and deletion all stay O(log n) in the worst case — the cost is the extra bookkeeping and occasional rotations on every update.

Example: AVL Practice

#include <iostream>
using namespace std;
int main() {
    cout << "AVL guarantees O(log n) height, so search/insert/delete all run in O(log n)" << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        System.out.println("AVL guarantees O(log n) height, so search/insert/delete all run in O(log n)");
    }
}
print("AVL guarantees O(log n) height, so search/insert/delete all run in O(log n)")
#include <stdio.h>
int main() {
    printf("AVL guarantees O(log n) height, so search/insert/delete all run in O(log n)\n");
    return 0;
}
🔒

Chapter Quiz — Complete all 10 topics to unlock

0/10 topics done

Complete these topics first:

← Previous Lesson BST Insert Delete Search Next Lesson → Height and Diameter of Tree

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.