Ins:

Del:

Ins:|Del:

Overview & Concept

An AVL Tree (named after inventors Adelson-Velsky and Landis) is a self-balancing Binary Search Tree. For every node in an AVL tree, the heights of its two subtrees differ by at most 1: Balance Factor = height(left) - height(right) ∈ {-1, 0, 1}. Whenever an insertion or deletion violates this invariant, one of four tree rotations (Left, Right, Left-Right, Right-Left) is applied to restore balance in O(1) time per rotation, guaranteeing O(log n) worst-case time for search, insert, and delete.

How It Works

Balance Factor Tracking: Each node maintains its subtree height. Balance Factor BF = height(left) - height(right).

Violation Detection: After recursive insert or delete, the call stack unwinds, recalculating heights and checking if |BF| > 1.

Single Rotations: Left-Left (LL) imbalance is corrected by a single Right Rotation. Right-Right (RR) imbalance by a single Left Rotation.

Double Rotations: Left-Right (LR) imbalance requires a Left Rotation on left child followed by Right Rotation on current node. Right-Left (RL) requires Right Rotation on right child followed by Left Rotation on current node.

Step-by-Step Execution

1. Standard BST OperationPerform standard recursive BST insertion or deletion based on key comparison.

2. Height UpdateTraversing back up the ancestor stack, update node.height = 1 + max(height(left), height(right)).

3. Balance Factor ComputationCalculate BF = height(left) - height(right). Check if BF > 1 or BF < -1.

4. Rebalancing RotationsIf BF > 1 and key < left.key → Right Rotation (LL). If BF > 1 and key > left.key → Left-Right (LR). If BF < -1 and key > right.key → Left Rotation (RR). If BF < -1 and key < right.key → Right-Left (RL).

Asymptotic Complexity Analysis

Metric	Best Case	Average Case	Worst Case	Space Complexity
Complexity Bound	O(log n) guaranteed	O(log n) search/insert	O(log n) strictly bounded	O(n)
Explanation	Optimal input arrangement minimizing operations.	Expected time for uniformly distributed randomized inputs.	Adversarial degenerate conditions requiring full traversal.	Auxiliary memory allocated beyond original input size.

Pseudocode & Invariants

Algorithm Logic

// AVL Tree (Self-Balancing BST)
operation insert(node, key):
  if node == null: return new Node(key)
  if key < node.key: node.left = insert(node.left, key)
  else: node.right = insert(node.right, key)

  // Update height and compute Balance Factor (BF)
  node.height = 1 + max(height(node.left), height(node.right))
  bf = height(node.left) - height(node.right)

  // Rebalance if |bf| > 1 via Rotations
  if bf > 1 and key < node.left.key:   return rightRotate(node)       // LL
  if bf > 1 and key > node.left.key:   node.left = leftRotate(node.left)
                                       return rightRotate(node)       // LR
  if bf < -1 and key > node.right.key: return leftRotate(node)        // RR
  if bf < -1 and key < node.right.key: node.right = rightRotate(node.right)
                                       return leftRotate(node)        // RL
  return node

Algorithmic Invariants

BST Invariant: Left subtree keys < root key < right subtree keys.
AVL Balance Invariant: For every node x, |height(x.left) - height(x.right)| ≤ 1.
Height Bound Invariant: Maximum tree height h < 1.44 log₂(n + 2) - 0.328, strictly guaranteeing O(log n) lookup depth.

Correctness Guarantee: Invariants hold true prior to loop entry, are preserved during every iteration, and guarantee correct post-condition upon termination.

Advantages & Disadvantages

Key Advantages

•Strictly balanced: lookup time is faster and more consistent than standard BST or Red-Black trees due to tighter height bounds.
•Guaranteed O(log n) worst-case time for search, insertion, and deletion.
•Prevents tree degeneration into an O(n) linked list under sorted insertion sequences.

Trade-offs & Limitations

•Requires frequent rotations during insertion and especially deletion.
•Additional memory overhead per node to store height or balance factor.
•Implementation complexity is significantly higher than basic BSTs.

Real-World Applications

Database Indexing with Intensive Lookups

In-memory relational database indexes where read queries drastically outnumber write transactions.

Routing Tables & IP Lookup

Network packet forwarding tables requiring deterministic sub-microsecond prefix match lookups.

Compiler Symbol Tables

Programming language compiler scope resolvers verifying identifier declarations during code generation.

Decision Guide: When to Use

Ideal Scenarios

✓When search operations are substantially more frequent than insertions and deletions.
✓When deterministic O(log n) response latency is critical and degenerate BSTs cannot be tolerated.

Consider Alternatives When

✕When frequent bulk insertions/deletions occur (Red-Black trees or B-Trees offer fewer rebalancing rotations).
✕When simple data sets are already randomly ordered.

Compare trade-offs and complexity across complementary tools in AlgoViz.

Binary Tree (BST)B-Tree Binary Search