---
description: What are AVL Trees? AVL trees are binary search trees in which the difference between the height of the left and right subtree is either -1, 0, or +1. AVL trees are also called a self-balancing binar
title: AVL Trees: Rotations, Insertion, Deletion with C++ Example
image: https://www.guru99.com/images/avl-trees.png
---

 

[Skip to content](#main) 

**⚡ Smart Summary**

AVL Trees are self-balancing binary search trees where the height difference between the left and right subtrees of every node stays within -1, 0, or +1, guaranteeing O(log n) search performance.

* 🌲 **Definition:** A binary search tree in which the balance factor of every node lies in {-1, 0, +1}, named after inventors Adelson-Velsky and Landis.
* ⚖️ **Balance Factor:** Computed as height(left) − height(right); values outside {-1, 0, +1} trigger a rotation to restore balance.
* 🔄 **Rotations:** Four cases — LL, RR, LR, and RL — realign nodes after unbalanced insertions or deletions to keep the tree logarithmic in height.
* ➕ **Insertion:** Standard BST insert followed by an upward walk that recomputes balance factors and performs at most one single or double rotation.
* ➖ **Deletion:** Same as BST deletion but may cascade multiple rotations up the tree because subtree height can shrink at every ancestor.
* 🚀 **Applications:** Databases, in-memory indexes, filesystem metadata, and AI search structures use AVL Trees for fast ordered lookups.

[ Read More ](javascript:void%280%29;) 

![AVL Trees]()

## What are AVL Trees?

**AVL Trees** are binary search trees in which the height difference between the left and right subtree of every node is -1, 0, or +1\. They are self-balancing BSTs that maintain logarithmic search time, named after inventors Adelson-Velsky and Landis (AVL).

## How does AVL Tree work?

To understand why AVL Trees exist, look at what goes wrong with a plain [Binary Search Tree](https://www.guru99.com/binary-search-tree-data-structure.html). Consider these keys inserted in the given order:

[](https://www.guru99.com/images/2/063020%5F0727%5FAVLTreesRot1.png)

_AVL tree visualization_

The tree grows linearly when keys arrive in increasing order, degenerating search to O(n). That defeats the purpose of a BST — only a balanced tree keeps search logarithmic. Now look at the same keys inserted in a different order.

[](https://www.guru99.com/images/2/063020%5F0727%5FAVLTreesRot2.png)

Same keys, different insertion order produces a shallower shape, so every search runs in O(log n). AVL Trees enforce that shape by watching the height on every insertion and correcting imbalance without breaking BST ordering.

## Balance Factor in AVL Trees

The balance factor (BF) tracks each node’s height so the tree can self-balance on the fly.

### Properties of Balance Factor

[](https://www.guru99.com/images/2/063020%5F0727%5FAVLTreesRot3.png)

_Balance factor AVL tree_

* The balance factor is the difference between the height of the left subtree and the height of the right subtree.
* `Balance factor(node) = height(node->left) − height(node->right)`
* The only allowed values are −1, 0, and +1.
* A value of −1 means the right subtree contains one extra level — the node is right-heavy.
* A value of +1 means the left subtree contains one extra level — the node is left-heavy.
* A value of 0 means both sides have equal height — the node is perfectly balanced.

## AVL Rotations

Rotations run whenever an insertion or deletion breaks the balance factor rule. The four cases are LL, RR, LR, and RL.

### Left – Left Rotation

This rotation is performed when a new node is inserted at the left child of the left subtree.

[](https://www.guru99.com/images/2/063020%5F0727%5FAVLTreesRot4.png)

_AVL Tree Left – Left Rotation_

A single right rotation is performed. This case fires when a node has BF +2 and its left child has BF +1.

### Right – Right Rotation

This rotation is performed when a new node is inserted at the right child of the right subtree.

[](https://www.guru99.com/images/2/063020%5F0727%5FAVLTreesRot5.png)

A single left rotation is performed. This case fires when a node has BF −2 and its right child has BF −1.

### Right – Left Rotation

This rotation is performed when a new node is inserted at the left child of the right subtree.

[](https://www.guru99.com/images/2/063020%5F0727%5FAVLTreesRot6.png)

Fires when BF(node) = −2 and BF(right-child) = +1\. Right-rotate the right child, then left-rotate the node.

### Left – Right Rotation

This rotation is performed when a new node is inserted at the right child of the left subtree.

[](https://www.guru99.com/images/2/063020%5F0727%5FAVLTreesRot7.png)

Fires when BF(node) = +2 and BF(left-child) = −1\. Left-rotate the left child, then right-rotate the node.

## Insertion in AVL Trees

Insertion is almost identical to a plain BST insert. After every insert, the tree walks up and re-balances. Insert runs in O(log n) worst-case time.

[](https://www.guru99.com/images/2/063020%5F0727%5FAVLTreesRot8.png)

_AVL tree insertion implementation_

**Step 1:** Insert the node using the standard BST algorithm. In the example above, insert 160.

**Step 2:** Update the balance factor of every ancestor along the insertion path.

**Step 3:** If any ancestor violates the balance factor range, perform the matching rotation. In the example, node 350’s balance factor is violated, so an LL rotation restores balance.

1. If `BF(node) = +2` and `BF(left-child) = +1`, perform LL rotation.
2. If `BF(node) = −2` and `BF(right-child) = −1`, perform RR rotation.
3. If `BF(node) = −2` and `BF(right-child) = +1`, perform RL rotation.
4. If `BF(node) = +2` and `BF(left-child) = −1`, perform LR rotation.

### RELATED ARTICLES

* [Circular Linked List: Advantages and Disadvantages ](https://www.guru99.com/circular-linked-list.html "Circular Linked List: Advantages and Disadvantages")
* [B Tree in Data Structure: Search, Insert, Delete ](https://www.guru99.com/b-tree-example.html "B Tree in Data Structure: Search, Insert, Delete")
* [How to Solve 3×3 Magic Square Puzzle in C & Python ](https://www.guru99.com/magic-square-math-puzzle.html "How to Solve 3×3 Magic Square Puzzle in C & Python")
* [7 BEST Data Structures and Algorithms Courses (2026) ](https://www.guru99.com/best-data-structures-and-algorithms-courses.html "7 BEST Data Structures and Algorithms Courses (2026)")

## Deletion in AVL Trees

Deletion follows the same logic as a plain BST and re-balances afterwards.

**Step 1:** Find the element in the tree.

**Step 2:** Delete the node using standard BST deletion.

**Step 3:** Two cases are possible.

**Case 1:** Deleting from the right subtree.

* **1A.** If `BF(node) = +2` and `BF(left-child) = +1`, perform LL rotation.
* **1B.** If `BF(node) = +2` and `BF(left-child) = −1`, perform LR rotation.
* **1C.** If `BF(node) = +2` and `BF(left-child) = 0`, perform LL rotation.

[](https://www.guru99.com/images/2/063020%5F0727%5FAVLTreesRot9.png)

**Case 2:** Deleting from the left subtree.

* **2A.** If `BF(node) = −2` and `BF(right-child) = −1`, perform RR rotation.
* **2B.** If `BF(node) = −2` and `BF(right-child) = +1`, perform RL rotation.
* **2C.** If `BF(node) = −2` and `BF(right-child) = 0`, perform RR rotation.

[](https://www.guru99.com/images/2/063020%5F0727%5FAVLTreesRot10.jpg)

## C++ Example of AVL Trees

Below is a [C++](https://www.guru99.com/cpp-tutorial.html) program implementing AVL Trees:

#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

struct node {
    struct node *left;
    int data;
    int height;
    struct node *right;
};

class AVL {
public:
    struct node *root;

    AVL() {
        this->root = NULL;
    }

    int calheight(struct node *p) {
        if (p->left && p->right) {
            if (p->left->height < p->right->height)
                return p->right->height + 1;
            else
                return p->left->height + 1;
        }
        else if (p->left && p->right == NULL) {
            return p->left->height + 1;
        }
        else if (p->left == NULL && p->right) {
            return p->right->height + 1;
        }
        return 0;
    }

    int bf(struct node *n) {
        if (n->left && n->right)
            return n->left->height - n->right->height;
        else if (n->left && n->right == NULL)
            return n->left->height;
        else if (n->left == NULL && n->right)
            return -n->right->height;
        return 0;
    }

    struct node *llrotation(struct node *n) {
        struct node *p = n;
        struct node *tp = p->left;
        p->left = tp->right;
        tp->right = p;
        return tp;
    }

    struct node *rrrotation(struct node *n) {
        struct node *p = n;
        struct node *tp = p->right;
        p->right = tp->left;
        tp->left = p;
        return tp;
    }

    struct node *rlrotation(struct node *n) {
        struct node *p = n;
        struct node *tp = p->right;
        struct node *tp2 = p->right->left;
        p->right = tp2->left;
        tp->left = tp2->right;
        tp2->left = p;
        tp2->right = tp;
        return tp2;
    }

    struct node *lrrotation(struct node *n) {
        struct node *p = n;
        struct node *tp = p->left;
        struct node *tp2 = p->left->right;
        p->left = tp2->right;
        tp->right = tp2->left;
        tp2->right = p;
        tp2->left = tp;
        return tp2;
    }

    struct node *insert(struct node *r, int data) {
        if (r == NULL) {
            r = new struct node;
            r->data = data;
            r->left = r->right = NULL;
            r->height = 1;
            return r;
        }
        if (data < r->data)
            r->left = insert(r->left, data);
        else
            r->right = insert(r->right, data);

        r->height = calheight(r);

        if (bf(r) == 2 && bf(r->left) == 1)       r = llrotation(r);
        else if (bf(r) == -2 && bf(r->right) == -1) r = rrrotation(r);
        else if (bf(r) == -2 && bf(r->right) == 1)  r = rlrotation(r);
        else if (bf(r) == 2 && bf(r->left) == -1)   r = lrrotation(r);

        return r;
    }

    void levelorder_newline() {
        if (this->root == NULL) {
            cout << "\nEmpty tree\n";
            return;
        }
        levelorder_newline(this->root);
    }

    void levelorder_newline(struct node *v) {
        queue<struct node *> q;
        struct node *cur;
        q.push(v);
        q.push(NULL);
        while (!q.empty()) {
            cur = q.front();
            q.pop();
            if (cur == NULL && q.size() != 0) {
                cout << "\n";
                q.push(NULL);
                continue;
            }
            if (cur != NULL) {
                cout << " " << cur->data;
                if (cur->left != NULL)  q.push(cur->left);
                if (cur->right != NULL) q.push(cur->right);
            }
        }
    }

    struct node *deleteNode(struct node *p, int data) {
        if (p->left == NULL && p->right == NULL) {
            if (p == this->root) this->root = NULL;
            delete p;
            return NULL;
        }
        struct node *q;
        if (p->data < data)      p->right = deleteNode(p->right, data);
        else if (p->data > data) p->left  = deleteNode(p->left, data);
        else {
            if (p->left != NULL) {
                q = inpre(p->left);
                p->data = q->data;
                p->left = deleteNode(p->left, q->data);
            } else {
                q = insuc(p->right);
                p->data = q->data;
                p->right = deleteNode(p->right, q->data);
            }
        }

        if (bf(p) == 2 && bf(p->left) == 1)         p = llrotation(p);
        else if (bf(p) == 2 && bf(p->left) == -1)    p = lrrotation(p);
        else if (bf(p) == 2 && bf(p->left) == 0)     p = llrotation(p);
        else if (bf(p) == -2 && bf(p->right) == -1)  p = rrrotation(p);
        else if (bf(p) == -2 && bf(p->right) == 1)   p = rlrotation(p);
        else if (bf(p) == -2 && bf(p->right) == 0)   p = rrrotation(p);

        return p;
    }

    struct node *inpre(struct node *p) {
        while (p->right != NULL) p = p->right;
        return p;
    }

    struct node *insuc(struct node *p) {
        while (p->left != NULL) p = p->left;
        return p;
    }

    ~AVL() {}
};

int main() {
    AVL b;
    int c, x;
    do {
        cout << "\n1.Display levelorder on newline";
        cout << "\n2.Insert";
        cout << "\n3.Delete\n";
        cout << "\n0.Exit\n";
        cout << "\nChoice: ";
        cin >> c;
        switch (c) {
        case 1: b.levelorder_newline(); break;
        case 2:
            cout << "\nEnter no. "; cin >> x;
            b.root = b.insert(b.root, x);
            break;
        case 3:
            cout << "\nWhat to delete? "; cin >> x;
            b.root = b.deleteNode(b.root, x);
            break;
        case 0: break;
        }
    } while (c != 0);
}

Running example of the code above:

1. Copy the code above and save it in a file named `avl.cpp`.
2. Compile the code:

g++ avl.cpp -o run

1. Run the code.

./run

[](https://www.guru99.com/images/2/063020%5F0727%5FAVLTreesRot11.png)

## Advantages of AVL Trees

* The height of the AVL Tree is always balanced and never grows beyond log N.
* Search is faster than a plain Binary Search Tree because the tree cannot degenerate.
* Self-balancing is automatic — no rebuild step is required.
* Deterministic performance suits real-time systems and in-memory indexes.

## FAQs

🌲 What is an AVL Tree in data structure?

An AVL Tree is a self-balancing binary search tree where the balance factor of every node stays in {-1, 0, +1}. Rotations restore this invariant on every insert or delete, keeping search, insert, and delete at O(log n).

⚖️ How is the balance factor calculated?

The balance factor of a node equals height(left subtree) minus height(right subtree). Values must lie in {-1, 0, +1}. A balance factor of +2 or -2 signals that an insertion or deletion has unbalanced that node and a rotation is required.

🔄 What are the four rotations in an AVL Tree?

The four rotations are LL, RR, LR, and RL. LL uses a single right rotation, RR uses a single left rotation, and LR and RL are double rotations that combine one rotation on the child with an opposite rotation on the node.

➕ How does insertion work in an AVL Tree?

Insertion follows the standard BST rule, then the tree walks back up updating heights. If any ancestor breaks the balance rule, one single or double rotation restores balance. At most one rotation per insert is ever needed.

🌐 What is the difference between AVL Tree and Red-Black Tree?

AVL Trees are strictly balanced with a balance factor of at most one, giving faster lookups. Red-Black Trees allow looser balance, which makes insert and delete cheaper but search slightly slower. Databases prefer red-black for write-heavy loads.

🚀 Where are AVL Trees used in real applications?

AVL Trees power in-memory database indexes, filesystem metadata, priority queues, phonebook lookups, spell checkers, and any workload that needs deterministic O(log n) search plus in-order traversal for range queries.

🤖 Are AVL Trees used in AI and machine learning workloads?

Yes. AI systems use AVL Trees for symbol tables, ordered feature stores, k-d tree balancing, and nearest-neighbour lookups on structured data. They also underpin ranked retrieval indexes in intelligent search pipelines.

🛠️ Can AI Copilot generate an AVL Tree implementation automatically?

Yes. GitHub Copilot and similar AI assistants scaffold insert, delete, and rotation routines in C++, Java, or Python, and generate unit tests that verify the balance factor invariant on every operation.

#### Summarize this post with:

ChatGPT Perplexity Grok Google AI 

**Stay Updated on AI** **Get Weekly AI Skills, Trends, Actionable Advice.** 

##### Sign up for the newsletter

Subscribe for Free 

You have successfully subscribed.  
Please check your inbox. 

![AI-Newsletter]() Chosen by over **350,000+** professionals 

[Scroll to top ](#wrapper)Scroll to top 

× 

Toggle Menu Close 

Search for: 

Search

```json
{"@context":"https://schema.org","@graph":[{"@type":"Organization","@id":"https://www.guru99.com/#organization","name":"Guru99","sameAs":["https://www.facebook.com/Guru99Official","https://twitter.com/guru99com"],"logo":{"@type":"ImageObject","@id":"https://www.guru99.com/#logo","url":"https://www.guru99.com/images/guru99-logo-v1-150x59.png","contentUrl":"https://www.guru99.com/images/guru99-logo-v1-150x59.png","caption":"Guru99","inLanguage":"en-US"}},{"@type":"WebSite","@id":"https://www.guru99.com/#website","url":"https://www.guru99.com","name":"Guru99","publisher":{"@id":"https://www.guru99.com/#organization"},"inLanguage":"en-US"},{"@type":"ImageObject","@id":"https://www.guru99.com/images/avl-trees.png","url":"https://www.guru99.com/images/avl-trees.png","width":"700","height":"250","caption":"AVL Trees","inLanguage":"en-US"},{"@type":"BreadcrumbList","@id":"https://www.guru99.com/avl-tree.html#breadcrumb","itemListElement":[{"@type":"ListItem","position":"1","item":{"@id":"https://www.guru99.com","name":"Home"}},{"@type":"ListItem","position":"2","item":{"@id":"https://www.guru99.com/design-algorithm","name":"Algorithm"}},{"@type":"ListItem","position":"3","item":{"@id":"https://www.guru99.com/avl-tree.html","name":"AVL Trees: Rotations, Insertion, Deletion with C++ Example"}}]},{"@type":"WebPage","@id":"https://www.guru99.com/avl-tree.html#webpage","url":"https://www.guru99.com/avl-tree.html","name":"AVL Trees: Rotations, Insertion, Deletion with C++ Example","dateModified":"2026-07-06T13:34:10+05:30","isPartOf":{"@id":"https://www.guru99.com/#website"},"primaryImageOfPage":{"@id":"https://www.guru99.com/images/avl-trees.png"},"inLanguage":"en-US","breadcrumb":{"@id":"https://www.guru99.com/avl-tree.html#breadcrumb"}},{"@type":"Person","@id":"https://www.guru99.com/author/sarah","name":"Sarah Chen","description":"I'm Sarah Chen, a Senior Algorithm Engineer, dedicated to guiding you through the intricacies of algorithm engineering with clear, concise advice.","url":"https://www.guru99.com/author/sarah","image":{"@type":"ImageObject","@id":"https://www.guru99.com/images/sarah-chen-author.png","url":"https://www.guru99.com/images/sarah-chen-author.png","caption":"Sarah Chen","inLanguage":"en-US"},"worksFor":{"@id":"https://www.guru99.com/#organization"}},{"articleSection":"Algorithm","headline":"AVL Trees: Rotations, Insertion, Deletion with C++ Example","description":"What are AVL Trees? AVL trees are binary search trees in which the difference between the height of the left and right subtree is either -1, 0, or +1. AVL trees are also called a self-balancing binar","keywords":"bigdata, programming, database, server","speakable":{"@type":"SpeakableSpecification","cssSelector":[".entry-title",".summary"]},"@type":"Article","author":{"@id":"https://www.guru99.com/author/sarah","name":"Sarah Chen"},"dateModified":"2026-07-06T13:34:10+05:30","image":{"@id":"https://www.guru99.com/images/avl-trees.png"},"copyrightYear":"2026","name":"AVL Trees: Rotations, Insertion, Deletion with C++ Example","subjectOf":[{"@type":"FAQPage","mainEntity":[{"@type":"Question","name":"What is an AVL Tree in data structure?","acceptedAnswer":{"@type":"Answer","text":"An AVL Tree is a self-balancing binary search tree where the balance factor of every node stays in {-1, 0, +1}. Rotations restore this invariant on every insert or delete, keeping search, insert, and delete at O(log n)."}},{"@type":"Question","name":"How is the balance factor calculated?","acceptedAnswer":{"@type":"Answer","text":"The balance factor of a node equals height(left subtree) minus height(right subtree). Values must lie in {-1, 0, +1}. A balance factor of +2 or -2 signals that an insertion or deletion has unbalanced that node and a rotation is required."}},{"@type":"Question","name":"What are the four rotations in an AVL Tree?","acceptedAnswer":{"@type":"Answer","text":"The four rotations are LL, RR, LR, and RL. LL uses a single right rotation, RR uses a single left rotation, and LR and RL are double rotations that combine one rotation on the child with an opposite rotation on the node."}},{"@type":"Question","name":"How does insertion work in an AVL Tree?","acceptedAnswer":{"@type":"Answer","text":"Insertion follows the standard BST rule, then the tree walks back up updating heights. If any ancestor breaks the balance rule, one single or double rotation restores balance. At most one rotation per insert is ever needed."}},{"@type":"Question","name":"What is the difference between AVL Tree and Red-Black Tree?","acceptedAnswer":{"@type":"Answer","text":"AVL Trees are strictly balanced with a balance factor of at most one, giving faster lookups. Red-Black Trees allow looser balance, which makes insert and delete cheaper but search slightly slower. Databases prefer red-black for write-heavy loads."}},{"@type":"Question","name":"Where are AVL Trees used in real applications?","acceptedAnswer":{"@type":"Answer","text":"AVL Trees power in-memory database indexes, filesystem metadata, priority queues, phonebook lookups, spell checkers, and any workload that needs deterministic O(log n) search plus in-order traversal for range queries."}},{"@type":"Question","name":"Are AVL Trees used in AI and machine learning workloads?","acceptedAnswer":{"@type":"Answer","text":"Yes. AI systems use AVL Trees for symbol tables, ordered feature stores, k-d tree balancing, and nearest-neighbour lookups on structured data. They also underpin ranked retrieval indexes in intelligent search pipelines."}},{"@type":"Question","name":"Can AI Copilot generate an AVL Tree implementation automatically?","acceptedAnswer":{"@type":"Answer","text":"Yes. GitHub Copilot and similar AI assistants scaffold insert, delete, and rotation routines in C++, Java, or Python, and generate unit tests that verify the balance factor invariant on every operation."}}]}],"@id":"https://www.guru99.com/avl-tree.html#schema-1133337","isPartOf":{"@id":"https://www.guru99.com/avl-tree.html#webpage"},"publisher":{"@id":"https://www.guru99.com/#organization"},"inLanguage":"en-US","mainEntityOfPage":{"@id":"https://www.guru99.com/avl-tree.html#webpage"}}]}
```