Binary Search Trees & AVL Trees: Balancing, Operations & Self-Balancing

Key Concepts: Binary Search Trees (BSTs)

Definition and Properties

A Binary Search Tree (BST) is a binary tree where for every node:

• All nodes in the left subtree have values less than the node’s value.
• All nodes in the right subtree have values greater than the node’s value.
• No duplicate values are allowed (unless explicitly handled).

Visualization of a BST:

graph TD
    A["15"] --> B["10"]
    A --> C["20"]
    B --> D["7"]
    B --> E["12"]
    C --> F["18"]
    C --> G["25"]

Properties:

• Height: Longest path from root to leaf.
• Balanced BST: Height ≈ log₂(n) → O(log n) operations.
• Unbalanced BST: Height ≈ n → O(n) operations (worst case: linear chain).

Operations on BSTs

1. Insertion

Insert a new node while maintaining BST properties:

1. Start at the root.
2. Compare the new value with the current node:
   • If less, go to the left child.
   • If greater, go to the right child.
3. Repeat until an empty spot is found.
4. Insert the new node there.

Example: Insert 12 into the BST above

graph TD
    A["15"] --> B["10"]
    A --> C["20"]
    B --> D["7"]
    B --> E["12"]
    C --> F["18"]
    C --> G["25"]

Steps:

1. Start at 15 → 12 < 15 → go left to 10.
2. 12 > 10 → go right to null → insert 12 as right child of 10.

2. Search

Search for a value in the BST:

1. Start at the root.
2. Compare the target value with the current node:
   • If equal, return the node.
   • If less, search the left subtree.
   • If greater, search the right subtree.
3. If reach a null node, the value is not present.

Example: Search for 18 in the BST above

• Path: 15 → 20 → 18 (found).

Time Complexity:

3. Deletion

Deletion has three cases:

1. Node with no children (leaf): Simply remove it.
2. Node with one child: Replace it with its child.
3. Node with two children: Replace it with its in-order successor (smallest in the right subtree) or in-order predecessor (largest in the left subtree), then delete the successor/predecessor.

Example: Delete 10 from the BST above

1. 10 has two children (7 and 12).
2. Find in-order successor of 10: 12 (smallest in right subtree).
3. Replace 10 with 12, then delete 12 (which has no children). Resulting BST:

graph TD
    A["15"] --> B["12"]
    A --> C["20"]
    B --> D["7"]
    C --> F["18"]
    C --> G["25"]

In the Real World

1. Database Indexing (Nepal Stock Exchange - NEPSE): NEPSE’s trading system uses BSTs to index stock prices for fast lookups (e.g., finding the price of a stock like NMB Bank or NTC in O(log n) time). Unbalanced trees would slow down trades during high volatility.

2. File Systems (Windows/Linux): Operating systems use BSTs (or B-trees) to organize file directories. For example, when you search for a file in Windows Explorer, the system traverses a BST-like structure to quickly locate the file path.

3. Autocomplete in eSewa/Khalti: When you type a word in the eSewa or Khalti app, the autocomplete feature uses a BST to store all possible transactions (e.g., "electricity bill," "mobile recharge"). The BST ensures that suggestions are retrieved in O(log n) time, even with millions of entries.

AVL Trees: Self-Balancing BSTs

Why AVL Trees?

BSTs degrade to O(n) time if unbalanced (e.g., inserting sorted data). AVL Trees ensure balance by enforcing:

• Balance Factor (BF): BF = height(left subtree) – height(right subtree)
• AVL Property: For every node, |BF| ≤ 1.

Visualization of AVL Tree Insertion:

graph TD
    A["10"] --> B["5"]
    A --> C["20"]
    B --> D["2"]
    B --> E["7"]
    C --> F["15"]
    C --> G["30"]

Insert 1 (unbalanced):

1. Insert 1 as left child of 2.
2. Check BF of nodes along the path (5, 10):
   • BF of 5: height(2) - height(7) = 2 - 1 = 1 (still balanced).
   • BF of 10: height(5) - height(20) = 2 - 2 = 0 (balanced). No rotation needed yet.

Insert 16 (unbalanced):

1. Insert 16 as right child of 15.
2. Check BF of nodes:
   • BF of 15: height(null) - height(30) = 0 - 1 = -1 (balanced).
   • BF of 20: height(15) - height(30) = 2 - 1 = 1 (balanced).
   • BF of 10: height(5) - height(20) = 2 - 3 = -2 (unbalanced!).

Rotations to Maintain Balance

AVL Trees use four rotation types to rebalance:

1. Left-Left (LL) Case:

   • Problem: Right subtree is heavier by 2.
   • Solution: Right Rotation on the unbalanced node.

   graph TD
       A["Unbalanced"] --> B["Left"]
       A --> C["Right"]
       C --> D["Right-Right"]

   After Right Rotation:

   graph TD
       D["New Root"] --> A["Left"]
       D --> C["Right"]

2. Right-Right (RR) Case:

   • Problem: Left subtree is heavier by 2.
   • Solution: Left Rotation on the unbalanced node.

   graph TD
       A["Unbalanced"] --> B["Left-Left"]
       A --> C["Right"]

   After Left Rotation:

   graph TD
       B["New Root"] --> A["Right"]
       B --> D["Left"]

3. Left-Right (LR) Case:

   • Problem: Left child’s right subtree is heavier.
   • Solution: Left rotation on the left child, then right rotation on the unbalanced node.

   graph TD
       A["Unbalanced"] --> B["Left"]
       B --> C["Left-Right"]
       A --> D["Right"]

   Steps:

   1. Left rotate on B → C becomes root of left subtree.
   2. Right rotate on A.

4. Right-Left (RL) Case:

   • Problem: Right child’s left subtree is heavier.
   • Solution: Right rotation on the right child, then left rotation on the unbalanced node.

   graph TD
       A["Unbalanced"] --> B["Left"]
       A --> C["Right-Left"]
       C --> D["Right"]

   Steps:

   1. Right rotate on C → D becomes root of right subtree.
   2. Left rotate on A.

AVL Insertion Example

Insert 1, 2, 3, 4 into an empty AVL Tree:

1. Insert 1 → Tree: [1] (balanced).
2. Insert 2 → Right child of 1 → BF of 1: 0 - 1 = -1 (balanced).
3. Insert 3 → Right child of 2 → BF of 2: 0 - 1 = -1 (balanced). BF of 1: 0 - 2 = -2 (unbalanced!). Case: Left-Left (LL) → Right Rotation on 1. Result:

   graph TD
       A["2"] --> B["1"]
       A --> C["3"]

Time Complexity of AVL Trees

Why?

• AVL Trees guarantee height ≈ log₂(n), so all operations remain efficient.

Comparison: BST vs. AVL Tree

Applications of AVL Trees

1. Databases (e.g., MySQL Indexes): AVL Trees are used in B-tree variants for indexing tables (e.g., PRIMARY KEY lookups in SQL). Ensures fast queries even with millions of records.

2. Symbol Tables (Compilers): Compilers use AVL Trees to store variable names and scopes during code compilation (e.g., in C/C++ compilers).

3. Network Routing (NTC’s IP Lookup): NTC’s routers use trie-based AVL Trees to quickly route packets to destinations (e.g., finding the best path to Google’s IP in O(log n) time).

Exam Tip

1. Understand BST Properties:

   • Always verify left < root < right for every node.
   • Memorize in-order traversal gives sorted output.

2. Deletion Cases:

   • Three cases: No child, one child, two children (use successor/predecessor).
   • Practice: Delete a node with two children and trace the successor.

3. AVL Rotations:

   • Four cases (LL, RR, LR, RL): Draw each and know when to apply them.
   • Balance Factor: Calculate BF after every insertion/deletion to identify unbalanced nodes.

4. Time Complexity:

   • BST: O(n) worst case (degenerate tree).
   • AVL Tree: Always O(log n) due to balancing.

5. Real-World Links:

   • eSewa/Khalti: BST for transaction history (sorted by date).
   • NEPSE: AVL-like structures for stock price indexing.
   • Pathao/Daraz: AVL Trees for dynamic pricing algorithms.

Practice Problem: Given an AVL Tree with nodes [10, 20, 30], insert 5 and perform rotations if needed. Draw the tree before and after insertion and show the BF of each node.