Lecture Notes on Binary Search Trees and AVL Trees

Introduction

• Topic: Sorting and Binary Search Trees (BSTs)
• Focus: Efficient dynamic sorting with binary search trees
• Context: Continuing the theme of sorting algorithms

Binary Search Trees (BSTs)

Properties

• BST Property: Each node has a key
  • Left subtree: keys ≤ node’s key
  • Right subtree: keys ≥ node’s key

Traversal

• In-order Traversal: Produces sorted order
  • Visit left child
  • Print root
  • Visit right child

Operations and Complexity

• Common Operations: Insert, delete, find next larger/smaller element (successor/predecessor)
• Time Complexity: O(h) where h is the height of the tree

Balancing BSTs

Balanced vs Unbalanced Trees

• Balanced Tree: Height ≈ log n
• Worst Cast (Unbalanced): Height = n (very unbalanced, path-like structure)
• Height Definition: Length of the longest path from root to a leaf

Balanced Height Property

• Balanced: Height O(log n)
  • If height is not overly large, keeps operations efficient
• Goal: Maintain balanced trees to ensure efficient operations

AVL Trees

Introduction

• Goal: Maintain balanced BSTs
• Definition: Height of left and right subtrees of any node differ by at most 1
• Height Constraint: Avoid paths longer than O(log n)

Mathematical Proof of Balance

• Worst Case Analysis: Derived recurrence relation
  • n_h = 1 + n_{h-1} + n_{h-2}
  • Based on Fibonacci series
• Result: Height is O(log n)

Implementing AVL Trees

Insertion and Balancing

• Step 1: Perform regular BST insertion
• Step 2: Fix the AVL property

Rotations

• Purpose: Re-balance the tree
• Types: Left rotation, right rotation, and double rotations

Example Operations

Insertion

• Example: Insert 23 in a given tree
  • Modify heights and check balance
  • Apply right rotation if necessary to restore balance
• Example: Insert 55 in a given tree
  • Fix with two rotations to maintain AVL property

Rotation Procedures

• Single Rotation: When imbalance is connected in a straight line (right-heavy or left-heavy)
• Double Rotation: When imbalance forms a zigzag shape, requiring two rotations (left-right, right-left)

General Case and Algorithm

• Traversal from Changed Node Up: Fix imbalances moving up the tree
• Check and Apply Rotations: Until balance is restored at all levels of the tree

Practical Utility

Sorting with AVL Trees

• Sorting: Insert and then perform in-order traversal
• Time Complexity: O(n log n)

Operations Supported

• Insert, Delete, Find min, Successor, Predecessor
• Abstract Data Type (ADT): Defines a set of operations supported by the data structure

Comparison with Heaps

• Heaps: Good for priority queues with insert and delete min
• AVL Trees: More versatile, supports a comprehensive set of operations