Balanced Binary Search Trees | Advanced Data Structures

LEARNING GOALS

🎯 Learning Objectives

After completing this level, you should be able to:

Explain how an ordinary BST can degrade to a linear chain.
Calculate height and balance factor.
Recognize LL, RR, LR and RL rotation cases.
Insert keys into AVL, Red–Black and Splay Trees.
Trace rotations and Red–Black recolouring.
Explain zig, zig–zig and zig–zag splaying.
Compare strict, relaxed and amortized balancing.
Select a balanced tree for a real application.

THE HEIGHT PROBLEM

📏 1. Why Must a BST Be Balanced?

BST operations take O(h), where h is tree height. Inserting sorted keys into an ordinary BST can produce height n−1 and O(n) search. A balanced BST keeps height proportional to log n.

Balanced Shape

Height remains O(log n), so search and updates stay efficient.

Degenerate Shape

A one-sided chain behaves like a linked list and needs O(n) comparisons.

Local Repair

Rotations change shape without changing inorder key order.

Different Guarantees

AVL is strict, Red–Black is relaxed, and Splay provides amortized efficiency.

BST operation cost: Search, insertion and deletion are O(h). Balancing aims to keep h = O(log n).

ORDER-PRESERVING RESTRUCTURE

🔄 2. Tree Rotations

A rotation changes a few parent-child links while preserving the BST inorder sequence.

LL

Right Rotation

The new key entered the left subtree of the left child.

RR

Left Rotation

The new key entered the right subtree of the right child.

LR

Left + Right

First rotate the left child left, then the node right.

RL

Right + Left

First rotate the right child right, then the node left.

Important: rotation names describe the heavy/insertion direction. LL is repaired by a right rotation; RR is repaired by a left rotation.

STRICT HEIGHT BALANCE

🌿 3. AVL Trees

An AVL Tree stores a height at every node. Its balance factor must remain −1, 0 or 1.

Balance Factor BF(v) = height(left(v)) − height(right(v)). Rebalance whenever |BF| > 1.

Search

Guaranteed O(log n) because the height is tightly controlled.

Insertion

Insert as BST, update heights upward and repair the first imbalance.

Deletion

Delete as BST and possibly rebalance several ancestors.

Best Fit

Read-heavy systems where predictable fast searches matter.

Algorithm — AVL Search

Start at the root.
Compare the target with the current key.
Return the node when equal; otherwise move left or right.
Repeat the loop condition until found or NULL.

Algorithm — AVL Insertion

Insert using ordinary BST recursion.
Update every returning node's height.
Compute its balance factor.
Apply LL, RR, LR or RL rotation when required.

Algorithm — AVL Deletion

Locate and delete as in a BST.
For two children, copy the inorder successor and delete it.
Update heights while recursion returns.
Rebalance every affected ancestor.

💻 Complete C Program — AVL Tree InsertionView program

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int key;
    int height;
    struct Node *left;
    struct Node *right;
} Node;

int maxInt(int first, int second) {
    return first > second ? first : second;
}

int nodeHeight(Node *node) {
    return node == NULL ? 0 : node->height;
}

Node *createNode(int key) {
    Node *node = malloc(sizeof(Node));
    node->key = key;
    node->height = 1;
    node->left = node->right = NULL;
    return node;
}

void updateHeight(Node *root) {
    root->height = 1 + maxInt(nodeHeight(root->left),
                              nodeHeight(root->right));
}

int balanceFactor(Node *root) {
    return nodeHeight(root->left) - nodeHeight(root->right);
}

Node *rotateRight(Node *oldRoot) {
    Node *newRoot = oldRoot->left;
    Node *middle = newRoot->right;
    newRoot->right = oldRoot;
    oldRoot->left = middle;
    updateHeight(oldRoot);
    updateHeight(newRoot);
    return newRoot;
}

Node *rotateLeft(Node *oldRoot) {
    Node *newRoot = oldRoot->right;
    Node *middle = newRoot->left;
    newRoot->left = oldRoot;
    oldRoot->right = middle;
    updateHeight(oldRoot);
    updateHeight(newRoot);
    return newRoot;
}

Node *insertAVL(Node *root, int key) {
    if (root == NULL) return createNode(key); /* avl create */

    if (key < root->key) { /* avl go left */
        root->left = insertAVL(root->left, key);
    } else if (key > root->key) { /* avl go right */
        root->right = insertAVL(root->right, key);
    } else {
        return root;
    }

    updateHeight(root); /* avl update height */
    int balance = balanceFactor(root); /* avl balance */

    if (balance > 1 && key < root->left->key)
        return rotateRight(root); /* avl LL */

    if (balance < -1 && key > root->right->key)
        return rotateLeft(root); /* avl RR */

    if (balance > 1 && key > root->left->key) {
        root->left = rotateLeft(root->left);
        return rotateRight(root); /* avl LR */
    }

    if (balance < -1 && key < root->right->key) {
        root->right = rotateRight(root->right);
        return rotateLeft(root); /* avl RL */
    }

    return root;
}

void preorder(Node *root) {
    if (root == NULL) return;
    printf("%d ", root->key);
    preorder(root->left);
    preorder(root->right);
}

int main(void) {
    int n, key;
    Node *root = NULL;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &key);
        root = insertAVL(root, key); /* avl insert call */
        /* avl insertion complete */
    }
    /* avl complete */
    preorder(root);
    return 0;
}

Sample Input

7
30 20 10 25 28 40 50

Sample Output (Preorder)

28 20 10 25 40 30 50

RELAXED BALANCE WITH COLOURS

🔴 4. Red–Black Trees

A Red–Black Tree stores one colour bit per node. It permits more height variation than AVL while keeping height O(log n).

Rule 1

Every node is red or black.

Rule 2

The root is black.

Rule 3

Every null leaf is treated as black.

Rule 4

A red node cannot have a red child.

Rule 5

Every path from a node to a null leaf has equal black-height.

Height Bound

Height is at most 2 log₂(n+1).

Why popular? Relaxed balance usually means fewer rotations during frequent insertions and deletions. Many ordered maps and sets use a Red–Black Tree.

Algorithm — Red–Black Search

Use ordinary BST comparison.
Recheck the loop condition before every comparison.
Move left for a smaller key and right for a larger key.
Stop at the key or the NIL leaf.

Algorithm — Red–Black Insertion

Attach the new node as red by BST order.
While its parent is red, inspect the uncle.
Recolour for a red uncle; otherwise rotate inner then outer shapes.
Force the root to black.

Algorithm — Red–Black Deletion

Delete using BST transplant and remember the removed colour.
If a black node was removed, enter the double-black fix loop.
Handle red-sibling, black-nephew and red-nephew cases.
Finish by colouring the replacement black.

💻 Complete C Program — Red–Black Tree InsertionView program

#include <stdio.h>
#include <stdlib.h>

typedef enum { RED, BLACK } Color;

typedef struct Node {
    int key;
    Color color;
    struct Node *left;
    struct Node *right;
    struct Node *parent;
} Node;

Node *createNode(int key) {
    Node *node = malloc(sizeof(Node));
    node->key = key;
    node->color = RED;
    node->left = node->right = node->parent = NULL;
    return node;
}

void rotateLeft(Node **root, Node *pivot) {
    Node *child = pivot->right;
    pivot->right = child->left;
    if (child->left != NULL) child->left->parent = pivot;
    child->parent = pivot->parent;
    if (pivot->parent == NULL) *root = child;
    else if (pivot == pivot->parent->left) pivot->parent->left = child;
    else pivot->parent->right = child;
    child->left = pivot;
    pivot->parent = child;
}

void rotateRight(Node **root, Node *pivot) {
    Node *child = pivot->left;
    pivot->left = child->right;
    if (child->right != NULL) child->right->parent = pivot;
    child->parent = pivot->parent;
    if (pivot->parent == NULL) *root = child;
    else if (pivot == pivot->parent->left) pivot->parent->left = child;
    else pivot->parent->right = child;
    child->right = pivot;
    pivot->parent = child;
}

Node *insertRedBlack(Node *root, int key) {
    Node *parent = NULL;
    Node *current = root;
    while (current != NULL) { /* rb compare */
        parent = current;
        current = key < current->key ? current->left : current->right;
    }

    Node *node = createNode(key); /* rb new red */
    node->parent = parent;
    if (parent == NULL) root = node;
    else if (key < parent->key) parent->left = node;
    else parent->right = node;

    while (node != root && node->parent->color == RED) { /* rb fix loop */
        Node *parentNode = node->parent;
        Node *grand = parentNode->parent;
        if (parentNode == grand->left) {
            Node *uncle = grand->right;
            if (uncle != NULL && uncle->color == RED) {
                parentNode->color = BLACK;
                uncle->color = BLACK;
                grand->color = RED;
                node = grand; /* rb recolor left */
            } else {
                if (node == parentNode->right) {
                    node = parentNode;
                    rotateLeft(&root, node); /* rb inner left */
                }
                parentNode = node->parent;
                grand = parentNode->parent;
                parentNode->color = BLACK;
                grand->color = RED;
                rotateRight(&root, grand); /* rb outer left */
            }
        } else {
            Node *uncle = grand->left;
            if (uncle != NULL && uncle->color == RED) {
                parentNode->color = BLACK;
                uncle->color = BLACK;
                grand->color = RED;
                node = grand; /* rb recolor right */
            } else {
                if (node == parentNode->left) {
                    node = parentNode;
                    rotateRight(&root, node); /* rb inner right */
                }
                parentNode = node->parent;
                grand = parentNode->parent;
                parentNode->color = BLACK;
                grand->color = RED;
                rotateLeft(&root, grand); /* rb outer right */
            }
        }
    }

    root->color = BLACK; /* rb root black */
    return root;
}

void preorder(Node *root) {
    if (root == NULL) return;
    printf("%d%c ", root->key, root->color == RED ? 'R' : 'B');
    preorder(root->left);
    preorder(root->right);
}

int main(void) {
    int n, key;
    Node *root = NULL;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &key);
        root = insertRedBlack(root, key); /* rb insert call */
    }
    /* rb complete */
    preorder(root);
    return 0;
}

Sample Input

8
30 15 45 10 20 40 50 5

Sample Output (Preorder)

30B 15R 10B 5R 20B 45B 40R 50R

SELF-ADJUSTING ACCESS

🟣 5. Splay Trees

A Splay Tree stores no height or colour. Every successful insertion or access moves the relevant key to the root.

1

Zig

One rotation when the node's parent is the root.

2

Zig–Zig

Two rotations in the same direction for LL or RR.

3

Zig–Zag

Two opposite rotations for LR or RL.

4

Locality

Frequently accessed keys remain near the top.

Amortized cost: O(log n) per operation over a sequence, although one individual operation can take O(n).

Algorithm — Splay Search

Search by BST order, remembering the last visited node.
If found, splay that node to the root.
If absent, splay the last visited node.
Repeated access therefore becomes cheaper.

Algorithm — Splay Insertion

Attach the key as a BST leaf.
While it has a parent, choose zig, zig–zig or zig–zag.
Rotate and return to the while condition.
Stop only when the inserted node becomes root.

Algorithm — Splay Deletion

Search and splay the target to the root.
Detach its left and right subtrees.
Splay the maximum node of the left subtree.
Attach the original right subtree to the new root.

💻 Complete C Program — Splay Tree InsertionView program

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int key;
    struct Node *left;
    struct Node *right;
    struct Node *parent;
} Node;

Node *createNode(int key) {
    Node *node = malloc(sizeof(Node));
    node->key = key;
    node->left = node->right = node->parent = NULL;
    return node;
}

void rotateLeft(Node **root, Node *pivot) {
    Node *child = pivot->right;
    pivot->right = child->left;
    if (child->left != NULL) child->left->parent = pivot;
    child->parent = pivot->parent;
    if (pivot->parent == NULL) *root = child;
    else if (pivot == pivot->parent->left) pivot->parent->left = child;
    else pivot->parent->right = child;
    child->left = pivot;
    pivot->parent = child;
}

void rotateRight(Node **root, Node *pivot) {
    Node *child = pivot->left;
    pivot->left = child->right;
    if (child->right != NULL) child->right->parent = pivot;
    child->parent = pivot->parent;
    if (pivot->parent == NULL) *root = child;
    else if (pivot == pivot->parent->left) pivot->parent->left = child;
    else pivot->parent->right = child;
    child->right = pivot;
    pivot->parent = child;
}

void splay(Node **root, Node *node) {
    while (node->parent != NULL) { /* splay loop */
        Node *parent = node->parent;
        Node *grand = parent->parent;
        if (grand == NULL) {
            if (node == parent->left)
                rotateRight(root, parent); /* splay zig right */
            else
                rotateLeft(root, parent); /* splay zig left */
        } else if (node == parent->left && parent == grand->left) {
            rotateRight(root, grand);
            rotateRight(root, parent); /* splay zig-zig right */
        } else if (node == parent->right && parent == grand->right) {
            rotateLeft(root, grand);
            rotateLeft(root, parent); /* splay zig-zig left */
        } else if (node == parent->right && parent == grand->left) {
            rotateLeft(root, parent);
            rotateRight(root, grand); /* splay zig-zag LR */
        } else {
            rotateRight(root, parent);
            rotateLeft(root, grand); /* splay zig-zag RL */
        }
    }
}

Node *insertSplay(Node *root, int key) {
    Node *parent = NULL;
    Node *current = root;
    while (current != NULL) { /* splay compare */
        parent = current;
        current = key < current->key ? current->left : current->right;
    }
    Node *node = createNode(key);
    node->parent = parent;
    if (parent == NULL) root = node;
    else if (key < parent->key) parent->left = node;
    else parent->right = node; /* splay attach */
    splay(&root, node);
    return root;
}

void preorder(Node *root) {
    if (root == NULL) return;
    printf("%d ", root->key);
    preorder(root->left);
    preorder(root->right);
}

int main(void) {
    int n, key;
    Node *root = NULL;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &key);
        root = insertSplay(root, key); /* splay insert call */
        /* splay insertion complete */
    }
    /* splay complete */
    preorder(root);
    return 0;
}

Sample Input

6
40 20 60 10 30 50

Sample Output (Preorder)

50 30 10 20 40 60

TREE SELECTION

⚖️ 6. Complete Comparison

Tree	Balancing Rule	Search	Insert/Delete	Stored Metadata	Best Use
AVL	\|BF\| ≤ 1	Worst O(log n)	Worst O(log n)	Height/balance	Search-heavy workloads
Red–Black	Colour and black-height rules	Worst O(log n)	Worst O(log n)	One colour bit	General ordered maps/sets
Splay	Move accessed node to root	Amortized O(log n)	Amortized O(log n)	No balance metadata	Locality and repeated access
Ordinary BST	None	Average O(log n), worst O(n)	Average O(log n), worst O(n)	None	Simple/random small data

INTERACTIVE ALGORITHM VISUALIZATION

🎬 7. Premium Balanced BST Visualizer

Load AVL, Red–Black or Splay search, insertion or deletion into one shared visualizer and watch every comparison, loop check, rotation and recolouring step.

CodeBhavya

Initial KeysTarget KeyTreeOperation

Choose a sequence and tree, then click Load Visualizer.

COMBINED C PROGRAM TRACER

🔍 8. Program Tracing — Every Core Operation

Select a tree and operation, then click Load Program Tracer. Only executable C statements are highlighted; loop conditions are revisited on every iteration before the body runs again.

Initial KeysTarget KeyTreeOperation

Selection alone does not execute the program. Click Load Program Tracer.

PRACTICAL DECISIONS

💡 9. Which Balanced Tree Should You Choose?

Read-heavy index

Choose AVL for tighter height and consistently fast lookup.

Frequent mixed updates

Choose Red–Black for robust logarithmic operations with fewer rotations.

Strong access locality

Choose Splay when recently accessed keys are likely to be accessed again.

Language library map/set

Red–Black Trees are a common general-purpose implementation.

Small simple dataset

An ordinary BST may be sufficient if worst-case degeneration is controlled.

Need strict worst-case lookup

Use AVL or Red–Black, not a Splay Tree's per-operation worst case.

AVOID THESE ERRORS

⚠️ 10. Common Mistakes

❌ Wrong balance sign

State whether BF is left−right or right−left and use it consistently.

❌ Rotation loses subtree

Save and reconnect the middle subtree during every rotation.

❌ Stale AVL heights

Update the lower node before the new subtree root.

❌ Red root remains

Force the Red–Black root to black after fix-up.

❌ Red–Red violation

Check both parent and uncle before choosing recolouring or rotation.

❌ Treating amortized as worst case

One Splay operation may be O(n), although a sequence averages O(log n).

CONCEPT CHECK

✍️ 11. Practice Problems

Solve each problem before opening the hint or answer. Answers are hidden initially.

1. What is the worst-case height of an ordinary BST with n keys?

2. Compute BF when left height is 4 and right height is 2.

3. Which rotation repairs insertion 30, 20, 10?

4. Which rotation repairs insertion 10, 20, 30?

5. Which rotations repair insertion 30, 10, 20?

6. Which rotations repair insertion 10, 30, 20?

7. What balance factors are permitted in an AVL Tree?

8. Why must AVL heights be updated after insertion?

9. Can a Red–Black root be red?

10. May a red node have a red child?

11. What happens when parent and uncle are both red?

12. What is Red–Black Tree worst-case search time?

13. What does a Splay Tree do after a successful access?

14. When is a single zig rotation used?

15. Distinguish zig–zig and zig–zag.

16. What is one Splay operation's worst-case time?

17. What is Splay Tree amortized operation time?

18. Which tree normally performs fewer update rotations: AVL or Red–Black?

19. Which tree gives the tighter height bound?

20. Does a rotation change the inorder sequence?

QUICK RECALL

📝 12. Quick Revision

BST operation cost depends on height.
Rotations preserve inorder key order.
AVL maintains balance factor −1, 0 or 1.
LL/RR need one rotation; LR/RL need two.
Red–Black Trees use colour and black-height rules for O(log n) height.
A red node cannot have a red child.
Splay Trees move an inserted or accessed key to the root.
Splay operations are O(log n) amortized, not per-operation worst-case.
AVL suits lookup-heavy work; Red–Black suits mixed updates; Splay suits locality.

🌲 Balanced Binary Search Trees

🎯 Learning Objectives

📏 1. Why Must a BST Be Balanced?

🔄 2. Tree Rotations

Right Rotation

Left Rotation

Left + Right

Right + Left

🌿 3. AVL Trees

Search

Insertion

Deletion

Best Fit

Algorithm — AVL Search

Algorithm — AVL Insertion

Algorithm — AVL Deletion

Sample Input

Sample Output (Preorder)

🔴 4. Red–Black Trees

Algorithm — Red–Black Search

Algorithm — Red–Black Insertion

Algorithm — Red–Black Deletion

Sample Input

Sample Output (Preorder)

🟣 5. Splay Trees

Zig

Zig–Zig

Zig–Zag

Locality

Algorithm — Splay Search

Algorithm — Splay Insertion

Algorithm — Splay Deletion

Sample Input

Sample Output (Preorder)

⚖️ 6. Complete Comparison

🎬 7. Premium Balanced BST Visualizer

🌳 Live Tree State

🔍 8. Program Tracing — Every Core Operation

💻 C Program

🧠 What is happening?

📊 Live Variables

Tree State

Output

💡 9. Which Balanced Tree Should You Choose?

Read-heavy index

Frequent mixed updates

Strong access locality

Language library map/set

Small simple dataset

Need strict worst-case lookup

⚠️ 10. Common Mistakes

❌ Wrong balance sign

❌ Rotation loses subtree

❌ Stale AVL heights

❌ Red root remains

❌ Red–Red violation

❌ Treating amortized as worst case

✍️ 11. Practice Problems

1. What is the worst-case height of an ordinary BST with n keys?

2. Compute BF when left height is 4 and right height is 2.

3. Which rotation repairs insertion 30, 20, 10?

4. Which rotation repairs insertion 10, 20, 30?

5. Which rotations repair insertion 30, 10, 20?

6. Which rotations repair insertion 10, 30, 20?

7. What balance factors are permitted in an AVL Tree?

8. Why must AVL heights be updated after insertion?

9. Can a Red–Black root be red?

10. May a red node have a red child?

11. What happens when parent and uncle are both red?

12. What is Red–Black Tree worst-case search time?

13. What does a Splay Tree do after a successful access?

14. When is a single zig rotation used?

15. Distinguish zig–zig and zig–zag.

16. What is one Splay operation's worst-case time?

17. What is Splay Tree amortized operation time?

18. Which tree normally performs fewer update rotations: AVL or Red–Black?

19. Which tree gives the tighter height bound?

20. Does a rotation change the inorder sequence?

📝 12. Quick Revision