Topic: Data Structures – Trees – Part 3 of 4: Balanced Trees – AVL Trees & Tree Height Management

---

### 1. Why Balance Matters in Trees

In unbalanced trees, especially skewed trees, operations like search, insert, and delete can degrade to O(n) time complexity.
Balanced trees maintain height close to log(n) for efficient performance.

---

### 2. AVL Tree – Introduction

An AVL Tree is a self-balancing Binary Search Tree named after inventors Adelson-Velsky and Landis.

Properties:

• For every node, the balance factor (height of left subtree – height of right subtree) must be -1, 0, or +1
• Automatically re-balances after insertions and deletions

---

### 3. Balance Factor Calculation

balance = height(left subtree) - height(right subtree)

Cases:

• Balance Factor > 1 → Left-heavy
• Balance Factor < -1 → Right-heavy

---

### 4. Rotations in AVL Trees

To restore balance, AVL trees use rotations:

Single Rotations:

• Right Rotation (LL Case)
• Left Rotation (RR Case)

Double Rotations:

• Left-Right Rotation (LR Case)
• Right-Left Rotation (RL Case)

---

### 5. AVL Tree Node Structure

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

---

### 6. Helper Functions

def get_height(node):
    if not node:
        return 0
    return node.height

def get_balance(node):
    if not node:
        return 0
    return get_height(node.left) - get_height(node.right)

def right_rotate(z):
    y = z.left
    T3 = y.right

    y.right = z
    z.left = T3

    z.height = 1 + max(get_height(z.left), get_height(z.right))
    y.height = 1 + max(get_height(y.left), get_height(y.right))

    return y

def left_rotate(z):
    y = z.right
    T2 = y.left

    y.left = z
    z.right = T2

    z.height = 1 + max(get_height(z.left), get_height(z.right))
    y.height = 1 + max(get_height(y.left), get_height(y.right))

    return y

---

### 7. Insertion in AVL Tree

def insert(node, key):
    if not node:
        return Node(key)

    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)
    else:
        return node  # no duplicate keys

    # Update height
    node.height = 1 + max(get_height(node.left), get_height(node.right))

    # Get balance factor
    balance = get_balance(node)

    # Balance the tree
    # Case 1 - Left Left
    if balance > 1 and key < node.left.key:
        return right_rotate(node)

    # Case 2 - Right Right
    if balance < -1 and key > node.right.key:
        return left_rotate(node)

    # Case 3 - Left Right
    if balance > 1 and key > node.left.key:
        node.left = left_rotate(node.left)
        return right_rotate(node)

    # Case 4 - Right Left
    if balance < -1 and key < node.right.key:
        node.right = right_rotate(node.right)
        return left_rotate(node)

    return node

---

### 8. Example AVL Tree Construction

root = None
for val in [10, 20, 30, 40, 50, 25]:
    root = insert(root, val)

After insertion, the AVL Tree balances itself using appropriate rotations.

---

### 9. Traversals

Use any standard traversal to see the output:

def inorder(root):
    if root:
        inorder(root.left)
        print(root.key, end=" ")
        inorder(root.right)

---

### 10. Summary

• AVL Trees ensure that BSTs stay balanced
• Balance is maintained using rotations after insertion
• Time complexity for all operations is O(log n)
• AVL Trees are ideal when frequent insertions and deletions are expected

---

### Exercise

• Build an AVL Tree from a set of values
• Add functions for insert, get_height, get_balance, and inorder
• Test insertions that trigger all four types of rotations
• Bonus: Implement AVL deletion (complex but possible)

---

#DSA #BalancedTree #BinarySearchTree #Python

https://t.iss.one/DataScience