AVL trees are self-balancing binary search trees that maintain a balanced structure for efficient operations. They use a balance factor to ensure the heights of left and right subtrees differ by at most one, guaranteeing logarithmic height and performance.

AVL trees support standard operations like search, insertion, and deletion, all with O(log n) time complexity. When insertions or deletions cause imbalance, rotations are performed to restore balance, ensuring the tree remains efficient for all operations.

AVL Tree Properties

Properties of AVL trees

• Self-balancing binary search tree maintains balanced structure for efficient operations
• Balance factor of a node calculated as $height(left subtree) - height(right subtree)$
  • In an AVL tree, balance factor of every node is either -1, 0, or 1
• Height-balance property ensures heights of left and right subtrees of any node differ by at most 1
  • Mathematically represented as $|height(left subtree) - height(right subtree)| \leq 1$
• Height of an AVL tree with $n$ nodes is always $O(\log n)$
  • Guarantees balanced structure and efficient operations (search, insertion, deletion)

AVL Tree Operations

Insertions and deletions in AVL trees

• Insertion follows standard BST insertion process
  • After insertion, check balance factor of each node along path from inserted node to root
  • If any node becomes unbalanced (balance factor -2 or 2), perform appropriate rotations to restore balance
• Deletion follows standard BST deletion process
  • After deletion, check balance factor of each node along path from deleted node's parent to root
  • If any node becomes unbalanced, perform appropriate rotations to restore balance

Time complexity of AVL operations

• Search operation takes $O(\log n)$ time in worst case
  • Balanced structure ensures height of tree is logarithmic, resulting in efficient search
• Insertion operation takes $O(\log n)$ time in worst case
  1. Insertion itself takes $O(\log n)$ time, following BST insertion process
  2. After insertion, rebalancing process (rotations) takes constant time, $O(1)$
• Deletion operation takes $O(\log n)$ time in worst case
  1. Deletion itself takes $O(\log n)$ time, following BST deletion process
  2. After deletion, rebalancing process (rotations) takes constant time, $O(1)$

Rotations for AVL rebalancing

• Left Rotation (LL Rotation) performed when node has balance factor of -2 and its right child has balance factor of -1 or 0
  • Right child becomes new root of subtree, original root becomes left child of new root
• Right Rotation (RR Rotation) performed when node has balance factor of 2 and its left child has balance factor of 1 or 0
  • Left child becomes new root of subtree, original root becomes right child of new root
• Left-Right Rotation (LR Rotation) performed when node has balance factor of -2 and its right child has balance factor of 1
  1. Perform left rotation on right child of unbalanced node
  2. Perform right rotation on unbalanced node
• Right-Left Rotation (RL Rotation) performed when node has balance factor of 2 and its left child has balance factor of -1
  1. Perform right rotation on left child of unbalanced node
  2. Perform left rotation on unbalanced node