AVL Trees

Overview

AVL trees are self-balancing binary search trees named after inventors Georgy Adelson-Velsky and Evgenii Landis. The structure maintains the binary search tree property while ensuring the tree remains balanced after every insertion and deletion operation. Balance is maintained by requiring that for every node, the heights of its left and right subtrees differ by at most one.

The balance constraint guarantees that the tree height remains logarithmic relative to the number of nodes, ensuring operations like search, insertion, and deletion complete in O(log n) time. This predictable performance makes AVL trees suitable for applications requiring guaranteed worst-case performance rather than average-case optimization.

When an operation violates the balance property, the tree performs one or more rotations to restore balance. Four rotation types handle all possible imbalance scenarios: left rotation, right rotation, left-right rotation, and right-left rotation. Each rotation restructures a small portion of the tree while preserving the binary search tree ordering.

Balanced AVL Tree:
       8
      / \
     4   12
    / \  / \
   2  6 10 14

Imbalanced after inserting 1:
       8
      / \
     4   12
    /    / \
   2    10 14
  /
 1

After right rotation on 4:
       8
      / \
     2   12
    / \  / \
   1  4 10 14

AVL trees provide stronger balance guarantees than red-black trees, resulting in faster lookups at the cost of more frequent rebalancing during modifications. Applications prioritizing read operations over write operations benefit from this trade-off.

Key Principles

Every AVL tree node stores a balance factor calculated as the height of its right subtree minus the height of its left subtree. Valid balance factors are -1, 0, and 1. A balance factor of -1 indicates the left subtree is one level taller, 0 indicates equal heights, and 1 indicates the right subtree is one level taller. Any other value violates the AVL property.

The tree enforces the balance property through structural rotations. A rotation changes the tree structure while maintaining the binary search tree ordering property. Single rotations handle cases where an imbalance occurs in a straight line (left-left or right-right), while double rotations handle zigzag patterns (left-right or right-left).

Left Rotation: Applied when the right subtree is too tall. The right child becomes the new root, the original root becomes the left child of the new root, and the new root's former left child becomes the original root's right child.

Before left rotation:
   A
    \
     B
      \
       C

After left rotation:
     B
    / \
   A   C

Right Rotation: Applied when the left subtree is too tall. The left child becomes the new root, the original root becomes the right child of the new root, and the new root's former right child becomes the original root's left child.

Before right rotation:
     C
    /
   B
  /
 A

After right rotation:
   B
  / \
 A   C

Left-Right Rotation: Applied when a node's left child has a taller right subtree. First performs a left rotation on the left child, then a right rotation on the original node.

Before:
     C
    /
   A
    \
     B

After left rotation on A:
     C
    /
   B
  /
 A

After right rotation on C:
   B
  / \
 A   C

Right-Left Rotation: Applied when a node's right child has a taller left subtree. First performs a right rotation on the right child, then a left rotation on the original node.

Height calculation forms the foundation for balance factor computation. A node's height equals one plus the maximum height of its children. Leaf nodes have height 0, and nil nodes have height -1. The tree recalculates heights and balance factors along the path from the modified node to the root after each insertion or deletion.

The insertion process follows standard binary search tree insertion, then walks back up the tree updating balance factors. If a node's balance factor becomes -2 or 2, the algorithm determines which rotation pattern to apply based on the balance factors of the node and its children. After rotation, the tree regains balance and no further rotations are needed for that insertion.

Deletion requires more complex handling. After removing a node using standard binary search tree deletion, the algorithm traces back to the root, potentially requiring multiple rotations. Each rotation may cause a reduction in subtree height, triggering additional imbalance higher in the tree. This cascading effect means deletion may require up to O(log n) rotations in the worst case, though typically fewer occur in practice.

Ruby Implementation

Ruby does not include an AVL tree in its standard library, requiring custom implementation. The implementation consists of a node class storing value, left and right children, and height, plus a tree class managing the root and tree operations.

class AVLNode
  attr_accessor :value, :left, :right, :height

  def initialize(value)
    @value = value
    @left = nil
    @right = nil
    @height = 0
  end

  def balance_factor
    right_height = @right ? @right.height : -1
    left_height = @left ? @left.height : -1
    right_height - left_height
  end

  def update_height
    right_height = @right ? @right.height : -1
    left_height = @left ? @left.height : -1
    @height = [right_height, left_height].max + 1
  end
end

The tree class implements insertion with automatic rebalancing:

class AVLTree
  attr_reader :root

  def initialize
    @root = nil
  end

  def insert(value)
    @root = insert_recursive(@root, value)
  end

  private

  def insert_recursive(node, value)
    return AVLNode.new(value) if node.nil?

    if value < node.value
      node.left = insert_recursive(node.left, value)
    elsif value > node.value
      node.right = insert_recursive(node.right, value)
    else
      return node  # Duplicate values not allowed
    end

    node.update_height
    rebalance(node)
  end

  def rebalance(node)
    balance = node.balance_factor

    # Left heavy
    if balance < -1
      if node.left.balance_factor > 0
        node.left = rotate_left(node.left)
      end
      return rotate_right(node)
    end

    # Right heavy
    if balance > 1
      if node.right.balance_factor < 0
        node.right = rotate_right(node.right)
      end
      return rotate_left(node)
    end

    node
  end

  def rotate_left(node)
    new_root = node.right
    node.right = new_root.left
    new_root.left = node

    node.update_height
    new_root.update_height

    new_root
  end

  def rotate_right(node)
    new_root = node.left
    node.left = new_root.right
    new_root.right = node

    node.update_height
    new_root.update_height

    new_root
  end
end

Search follows standard binary search tree logic without modification:

class AVLTree
  def search(value)
    search_recursive(@root, value)
  end

  private

  def search_recursive(node, value)
    return nil if node.nil?
    return node if node.value == value

    if value < node.value
      search_recursive(node.left, value)
    else
      search_recursive(node.right, value)
    end
  end
end

Deletion requires finding the node, removing it, and rebalancing the path back to the root:

class AVLTree
  def delete(value)
    @root = delete_recursive(@root, value)
  end

  private

  def delete_recursive(node, value)
    return nil if node.nil?

    if value < node.value
      node.left = delete_recursive(node.left, value)
    elsif value > node.value
      node.right = delete_recursive(node.right, value)
    else
      # Node with one child or no child
      return node.right if node.left.nil?
      return node.left if node.right.nil?

      # Node with two children
      successor = find_min(node.right)
      node.value = successor.value
      node.right = delete_recursive(node.right, successor.value)
    end

    node.update_height
    rebalance(node)
  end

  def find_min(node)
    current = node
    current = current.left while current.left
    current
  end
end

In-order traversal visits nodes in sorted order:

class AVLTree
  def in_order_traversal
    result = []
    in_order_recursive(@root, result)
    result
  end

  private

  def in_order_recursive(node, result)
    return if node.nil?

    in_order_recursive(node.left, result)
    result << node.value
    in_order_recursive(node.right, result)
  end
end

Practical Examples

A sorted set implementation demonstrates AVL tree usage for maintaining ordered unique elements:

class SortedSet
  def initialize
    @tree = AVLTree.new
    @size = 0
  end

  def add(value)
    previous_size = size
    @tree.insert(value)
    @size = @tree.in_order_traversal.length
    @size > previous_size
  end

  def include?(value)
    !@tree.search(value).nil?
  end

  def remove(value)
    return false unless include?(value)
    @tree.delete(value)
    @size -= 1
    true
  end

  def to_a
    @tree.in_order_traversal
  end

  def size
    @size
  end
end

# Usage
sorted_set = SortedSet.new
sorted_set.add(5)
sorted_set.add(2)
sorted_set.add(8)
sorted_set.add(2)  # => false, already exists

sorted_set.to_a  # => [2, 5, 8]
sorted_set.include?(5)  # => true
sorted_set.remove(2)  # => true
sorted_set.to_a  # => [5, 8]

Range query implementation finds all values within a specified range:

class AVLTree
  def range_query(min, max)
    result = []
    range_query_recursive(@root, min, max, result)
    result
  end

  private

  def range_query_recursive(node, min, max, result)
    return if node.nil?

    range_query_recursive(node.left, min, max, result) if node.value > min
    result << node.value if node.value >= min && node.value <= max
    range_query_recursive(node.right, min, max, result) if node.value < max
  end
end

# Usage
tree = AVLTree.new
[10, 5, 15, 3, 7, 12, 20].each { |val| tree.insert(val) }

tree.range_query(6, 15)  # => [7, 10, 12, 15]
tree.range_query(1, 8)   # => [3, 5, 7]

Priority queue implementation with efficient access to minimum and maximum elements:

class PriorityQueue
  def initialize
    @tree = AVLTree.new
  end

  def enqueue(priority, item)
    @tree.insert(priority)
  end

  def dequeue_min
    return nil if @tree.root.nil?
    
    min_node = find_min(@tree.root)
    min_priority = min_node.value
    @tree.delete(min_priority)
    min_priority
  end

  def peek_min
    min_node = find_min(@tree.root)
    min_node&.value
  end

  def empty?
    @tree.root.nil?
  end

  private

  def find_min(node)
    current = node
    current = current.left while current&.left
    current
  end
end

# Usage
pq = PriorityQueue.new
pq.enqueue(5, "task1")
pq.enqueue(2, "task2")
pq.enqueue(8, "task3")

pq.dequeue_min  # => 2
pq.peek_min     # => 5

Database index simulation using AVL trees for efficient lookups:

class DatabaseIndex
  def initialize
    @indices = Hash.new { |h, k| h[k] = AVLTree.new }
  end

  def add_record(id, attributes)
    attributes.each do |column, value|
      @indices[column].insert(value)
    end
  end

  def find_by(column, value)
    node = @indices[column].search(value)
    !node.nil?
  end

  def find_range(column, min, max)
    @indices[column].range_query(min, max)
  end
end

# Usage
index = DatabaseIndex.new
index.add_record(1, { age: 25, salary: 50000 })
index.add_record(2, { age: 30, salary: 60000 })
index.add_record(3, { age: 28, salary: 55000 })

index.find_by(:age, 30)  # => true
index.find_range(:salary, 50000, 58000)  # => [50000, 55000]

Common Patterns

The lazy height update pattern recalculates heights only when needed during rebalancing, avoiding unnecessary computation:

class AVLNode
  def lazy_update_height
    return if @left.nil? && @right.nil? && @height == 0
    
    right_height = @right ? @right.height : -1
    left_height = @left ? @left.height : -1
    @height = [right_height, left_height].max + 1
  end
end

The parent pointer pattern maintains references to parent nodes, simplifying traversal back to the root:

class AVLNodeWithParent
  attr_accessor :value, :left, :right, :parent, :height

  def initialize(value)
    @value = value
    @left = nil
    @right = nil
    @parent = nil
    @height = 0
  end

  def update_ancestors
    current = self
    while current
      current.update_height
      current = current.parent
    end
  end
end

The iterative insertion pattern avoids recursion for environments with limited stack space:

def insert_iterative(value)
  return @root = AVLNode.new(value) if @root.nil?

  path = []
  current = @root
  parent = nil

  while current
    path << current
    parent = current
    
    if value < current.value
      current = current.left
    elsif value > current.value
      current = current.right
    else
      return  # Duplicate
    end
  end

  new_node = AVLNode.new(value)
  if value < parent.value
    parent.left = new_node
  else
    parent.right = new_node
  end

  path.reverse.each do |node|
    node.update_height
    rebalance_at(node)
  end
end

The bulk loading pattern builds balanced trees efficiently from sorted input:

def build_from_sorted(values)
  build_recursive(values, 0, values.length - 1)
end

def build_recursive(values, start, finish)
  return nil if start > finish

  mid = (start + finish) / 2
  node = AVLNode.new(values[mid])

  node.left = build_recursive(values, start, mid - 1)
  node.right = build_recursive(values, mid + 1, finish)

  node.update_height
  node
end

The split pattern divides a tree into two trees based on a threshold value:

def split(threshold)
  smaller_tree = AVLTree.new
  larger_tree = AVLTree.new

  in_order_traversal.each do |value|
    if value < threshold
      smaller_tree.insert(value)
    else
      larger_tree.insert(value)
    end
  end

  [smaller_tree, larger_tree]
end

Performance Considerations

AVL trees guarantee O(log n) time complexity for search, insertion, and deletion operations in all cases, including worst case. This contrasts with unbalanced binary search trees that degrade to O(n) when insertions create a linear chain. The strict balance requirement keeps tree height bounded by 1.44 * log n.

Space complexity is O(n) for storing n nodes. Each node stores constant additional data: two child pointers and a height value. Some implementations store the balance factor directly instead of height, saving computation at the cost of additional storage.

Rebalancing overhead affects write-heavy workloads. Insertion requires at most one rotation, plus O(log n) height updates along the path to the root. Deletion may require multiple rotations in the worst case, though empirical studies show an average of 0.21 rotations per deletion. Applications with frequent modifications and infrequent lookups may prefer red-black trees, which guarantee at most three rotations per operation.

Cache performance suffers compared to array-based structures because pointer chasing causes cache misses. Tree traversal accesses memory locations scattered throughout the heap rather than contiguous locations. For datasets fitting in cache, sorted arrays with binary search often outperform AVL trees despite worse theoretical complexity.

require 'benchmark'

# Compare AVL tree vs sorted array for different operations
avl = AVLTree.new
sorted_array = []

n = 10000

Benchmark.bm do |x|
  x.report("AVL insert:") do
    n.times { |i| avl.insert(rand(100000)) }
  end

  x.report("Array insert:") do
    n.times do |i|
      value = rand(100000)
      index = sorted_array.bsearch_index { |x| x >= value } || sorted_array.length
      sorted_array.insert(index, value)
    end
  end

  x.report("AVL search:") do
    1000.times { avl.search(rand(100000)) }
  end

  x.report("Array search:") do
    1000.times { sorted_array.bsearch { |x| x >= rand(100000) } }
  end
end

The height calculation overhead accumulates during operations. Each insertion or deletion triggers O(log n) height updates. Caching heights at nodes reduces this to constant time per update. Without caching, height calculation requires traversing both subtrees, increasing complexity to O(n) per operation.

Memory allocation patterns affect performance in garbage-collected languages like Ruby. Frequent insertions and deletions create allocation pressure, triggering garbage collection pauses. Preallocating a node pool or using object pooling reduces allocation overhead:

class NodePool
  def initialize(capacity)
    @pool = Array.new(capacity) { AVLNode.new(nil) }
    @index = 0
  end

  def allocate(value)
    return AVLNode.new(value) if @index >= @pool.length
    
    node = @pool[@index]
    node.value = value
    node.left = nil
    node.right = nil
    node.height = 0
    @index += 1
    node
  end

  def reset
    @index = 0
  end
end

Common Pitfalls

Forgetting to update heights after rotations causes incorrect balance factor calculations. Every rotation changes the heights of the involved nodes. The rotated node and the new root both need height updates:

# INCORRECT - missing height updates
def rotate_left(node)
  new_root = node.right
  node.right = new_root.left
  new_root.left = node
  new_root  # Heights not updated
end

# CORRECT
def rotate_left(node)
  new_root = node.right
  node.right = new_root.left
  new_root.left = node
  
  node.update_height       # Update old root first
  new_root.update_height   # Then new root
  
  new_root
end

Calculating balance factor as left height minus right height instead of right minus left creates inverted logic. This reverses which rotations apply:

# INCORRECT
def balance_factor
  left_height = @left ? @left.height : -1
  right_height = @right ? @right.height : -1
  left_height - right_height  # Wrong direction
end

# CORRECT
def balance_factor
  left_height = @left ? @left.height : -1
  right_height = @right ? @right.height : -1
  right_height - left_height
end

Applying single rotations to zigzag patterns fails to restore balance. Left-right and right-left imbalances require double rotations:

# INCORRECT - only checks top-level balance
def rebalance(node)
  balance = node.balance_factor
  
  return rotate_left(node) if balance > 1   # Missing child check
  return rotate_right(node) if balance < -1  # Missing child check
  
  node
end

# CORRECT
def rebalance(node)
  balance = node.balance_factor
  
  if balance > 1
    node.right = rotate_right(node.right) if node.right.balance_factor < 0
    return rotate_left(node)
  end
  
  if balance < -1
    node.left = rotate_left(node.left) if node.left.balance_factor > 0
    return rotate_right(node)
  end
  
  node
end

Not rebalancing after deletion allows the tree to become unbalanced. Deletion requires rebalancing along the entire path from the deleted node to the root:

# INCORRECT - no rebalancing
def delete_recursive(node, value)
  return nil if node.nil?
  
  if value < node.value
    node.left = delete_recursive(node.left, value)
  elsif value > node.value
    node.right = delete_recursive(node.right, value)
  else
    return node.right if node.left.nil?
    return node.left if node.right.nil?
    
    successor = find_min(node.right)
    node.value = successor.value
    node.right = delete_recursive(node.right, successor.value)
  end
  
  node  # Missing rebalance call
end

# CORRECT
def delete_recursive(node, value)
  return nil if node.nil?
  
  if value < node.value
    node.left = delete_recursive(node.left, value)
  elsif value > node.value
    node.right = delete_recursive(node.right, value)
  else
    return node.right if node.left.nil?
    return node.left if node.right.nil?
    
    successor = find_min(node.right)
    node.value = successor.value
    node.right = delete_recursive(node.right, successor.value)
  end
  
  node.update_height
  rebalance(node)  # Essential step
end

Using nil height as 0 instead of -1 breaks height calculations for leaf nodes. Leaf nodes should have height 0, which requires treating nil children as height -1:

# INCORRECT
def update_height
  right_height = @right ? @right.height : 0  # Wrong
  left_height = @left ? @left.height : 0     # Wrong
  @height = [right_height, left_height].max + 1
end

# CORRECT
def update_height
  right_height = @right ? @right.height : -1
  left_height = @left ? @left.height : -1
  @height = [right_height, left_height].max + 1
end

Modifying node values directly after insertion violates the binary search tree property. Values determine node position and cannot change after insertion without reconstruction:

# INCORRECT
node = tree.search(10)
node.value = 20  # Breaks BST ordering

# CORRECT
tree.delete(10)
tree.insert(20)

Reference

Balance Factor Values

Rotation Selection

Time Complexity

Space Complexity

Operation Characteristics

Node Structure

Implementation Checklist