---

AVL Trees – Detailed Explanation

1. Introduction

An AVL Tree is a self-balancing Binary Search Tree (BST).
It was invented by Adelson-Velskii and Landis, hence the name A-V-L.

A BST can become skewed (like a linked list) if elements are inserted in a sorted order, causing search, insert, delete → O(n).
AVL Trees solve this by maintaining balance after every insertion and deletion.

---

2. Balance Factor (BF)

For every node:

[
\text{Balance Factor (BF)} = \text{Height(left subtree)} – \text{Height(right subtree)}
]

For an AVL Tree:

[
\text{BF must be −1, 0, or +1}
]

If BF becomes < −1 or > +1, the tree becomes unbalanced → rotations are required.

---

3. Properties of AVL Trees

1. Binary Search Tree structure
2. Self-balancing via rotations
3. Height = O(log n)
   (Strictly better balanced than normal BST)
4. Supports:
   • Search → O(log n)
   • Insert → O(log n)
   • Delete → O(log n)

---

4. Rotations in AVL Trees

When the tree becomes unbalanced, AVL uses four types of rotations:

---

A. LL Rotation (Single Right Rotation)

Occurs when:

• Node is inserted in left subtree of left child.

    A                     B
   /                     / \
  B        →            C   A
 /
C

---

B. RR Rotation (Single Left Rotation)

Occurs when:

• Node is inserted in right subtree of right child.

A                        B
 \                      / \
  B        →           A   C
   \
    C

---

C. LR Rotation (Left-Right Rotation)

Occurs when:

• Node is inserted in right subtree of left child.

      A                  A                 C
     /                  /                 / \
    B       →          C      →         B   A
     \                /
      C              B

This is a double rotation:
Left rotation on B → Right rotation on A.

---

D. RL Rotation (Right-Left Rotation)

Occurs when:

• Node is inserted in left subtree of right child.

A                       A                     C
 \                       \                   / \
  B          →            C       →         A   B
 /                          \ 
C                            B

This is also a double rotation.

---

5. Insertion in AVL Tree

Steps:

1. Insert the node like normal BST.
2. Update heights.
3. Check balance factors.
4. If balance factor violates AVL property → apply appropriate rotation:
   • LL → Right rotation
   • RR → Left rotation
   • LR → Left-Right rotation
   • RL → Right-Left rotation

Example:

Insert: 30, 20, 10

• Insert 30
• Insert 20
• Insert 10 → Causes LL imbalance
  → Perform Right rotation
  Result becomes:

    20
   /  \
  10  30

---

6. Deletion in AVL Tree

Deletion is similar to BST:

1. Delete the node normally.
2. Update height.
3. Check BF.
4. Apply rotations if needed.

Rotations used:

• LL → Right rotation
• RR → Left rotation
• LR → Left-Right rotation
• RL → Right-Left rotation

Deletion often causes multiple rebalancing operations going upward to the root.

---

7. Applications of AVL Trees

• Databases and indexing
• Memory management
• File systems
• Routing tables
• Situations where fast search is required
• Used inside libraries like C++ STL map/multimap, Java TreeMap, etc.
  (Though some use Red-Black Trees, concept similar)

---

8. Advantages

✔ Always balanced
✔ Guaranteed O(log n) complexity
✔ Faster searching than normal BST

---

9. Disadvantages

✘ Rotation overhead makes insert/delete slower than Red-Black Trees
✘ Slightly more memory required (storing height)

---

10. Summary Chart

Operation	BST	AVL Tree
Worst case Search	O(n)	O(log n)
Worst case Insert	O(n)	O(log n)
Worst case Delete	O(n)	O(log n)
Balancing	No	Yes
Uses	Simple apps	High-performance search

---