Red-Black Trees

Overview

Red-Black Trees represent a specific implementation of self-balancing binary search trees that use color properties to maintain approximate balance. Each node stores an additional bit of information (red or black) that determines how the tree restructures itself during insertions and deletions. This approach differs from AVL trees, which maintain stricter balance through height tracking, and from simpler binary search trees, which provide no balance guarantees.

The data structure originated from symmetric binary B-trees, introduced by Rudolf Bayer in 1972, with the red-black formulation published by Leonidas Guibas and Robert Sedgewick in 1978. The structure gained widespread adoption after its inclusion in several standard libraries, including the C++ Standard Template Library for map and set implementations, and Java's TreeMap and TreeSet classes.

Red-Black Trees achieve balance through five color-based properties rather than maintaining strict height balance. This relaxed balancing requirement means the tree performs fewer rotations during modifications compared to AVL trees, though searches may require slightly more comparisons due to the less strict height constraint. The tree guarantees that the path from root to any leaf contains no more than twice the number of nodes as the shortest root-to-leaf path.

# Basic node structure
class RBNode
  attr_accessor :key, :value, :color, :left, :right, :parent
  
  def initialize(key, value)
    @key = key
    @value = value
    @color = :red  # New nodes start red
    @left = nil
    @right = nil
    @parent = nil
  end
  
  def red?
    @color == :red
  end
  
  def black?
    @color == :black
  end
end

The structure finds application in scenarios requiring predictable worst-case performance for dynamic set operations. Operating systems use Red-Black Trees for process scheduling (Linux's Completely Fair Scheduler), memory management, and file system implementations. Database systems employ them for indexing structures when update frequency matters as much as search speed.

Key Principles

Red-Black Trees maintain balance through five fundamental properties that every tree must satisfy after each operation:

Property 1: Node Color - Every node carries a color attribute of either red or black. This binary color information determines restructuring behavior during tree modifications.

Property 2: Root Color - The root node must always be black. This property simplifies certain algorithms and ensures the tree maintains consistent behavior at the top level.

Property 3: Leaf Color - All NIL nodes (external nodes representing absence of children) are considered black. This convention allows algorithms to treat missing children uniformly without special case logic.

Property 4: Red Node Children - A red node cannot have red children. This constraint prevents consecutive red nodes along any path, which would indicate severe imbalance. A red node must have either two black children or NIL children (which are black by Property 3).

Property 5: Black Height - Every path from a node to its descendant NIL nodes contains the same number of black nodes. This property, called black-height, ensures the tree remains approximately balanced. The black-height of a node represents the number of black nodes on any path from that node to a leaf, not counting the node itself.

These properties work together to guarantee that the longest path from root to leaf is no more than twice the length of the shortest path. If the shortest path contains b black nodes (and no red nodes), the longest possible path contains b black nodes and b red nodes (alternating to satisfy Property 4), giving a 2:1 ratio.

# Property verification helper
class RBTree
  def verify_properties(node = @root, black_count = 0, path_black_count = nil)
    return black_count if node.nil?
    
    # Property 4: Check for consecutive red nodes
    if node.red? && node.parent&.red?
      raise "Property 4 violated: consecutive red nodes"
    end
    
    # Count black nodes
    current_black_count = black_count + (node.black? ? 1 : 0)
    
    # Property 5: Verify consistent black-height at leaves
    if node.left.nil? && node.right.nil?
      path_black_count ||= current_black_count
      if current_black_count != path_black_count
        raise "Property 5 violated: inconsistent black-height"
      end
      return current_black_count
    end
    
    verify_properties(node.left, current_black_count, path_black_count)
    verify_properties(node.right, current_black_count, path_black_count)
  end
end

The black-height concept provides the mathematical foundation for the logarithmic time complexity guarantee. A tree with black-height h contains at least 2^h - 1 internal nodes. With n nodes, the black-height cannot exceed log₂(n + 1), and since total height is at most 2 * black-height, the maximum height is 2 * log₂(n + 1), providing the O(log n) bound.

Rotations form the mechanical basis for maintaining these properties during insertions and deletions. A left rotation moves a right child up to replace its parent, while moving the parent down to become the left child. Right rotations perform the mirror operation. Rotations preserve binary search tree ordering while changing the tree's shape.

def rotate_left(node)
  right_child = node.right
  node.right = right_child.left
  
  right_child.left.parent = node if right_child.left
  right_child.parent = node.parent
  
  if node.parent.nil?
    @root = right_child
  elsif node == node.parent.left
    node.parent.left = right_child
  else
    node.parent.right = right_child
  end
  
  right_child.left = node
  node.parent = right_child
end

def rotate_right(node)
  left_child = node.left
  node.left = left_child.right
  
  left_child.right.parent = node if left_child.right
  left_child.parent = node.parent
  
  if node.parent.nil?
    @root = left_child
  elsif node == node.parent.right
    node.parent.right = left_child
  else
    node.parent.left = left_child
  end
  
  left_child.right = node
  node.parent = left_child
end

Ruby Implementation

Ruby's standard library does not include a native Red-Black Tree implementation, requiring custom implementation for applications that need this specific data structure. The language's object-oriented features and method flexibility support clean implementations of the complex balancing logic.

The core implementation requires a node class, the tree class, and three primary operation methods: insertion, deletion, and search. Each modification operation splits into two phases: performing the standard binary search tree operation, then restoring Red-Black properties through recoloring and rotations.

class RedBlackTree
  attr_reader :root
  
  def initialize
    @root = nil
    @size = 0
  end
  
  def insert(key, value)
    new_node = RBNode.new(key, value)
    
    if @root.nil?
      @root = new_node
      @root.color = :black  # Property 2
      @size += 1
      return
    end
    
    # Standard BST insertion
    current = @root
    parent = nil
    
    loop do
      parent = current
      if key < current.key
        current = current.left
        if current.nil?
          parent.left = new_node
          break
        end
      elsif key > current.key
        current = current.right
        if current.nil?
          parent.right = new_node
          break
        end
      else
        # Key exists, update value
        current.value = value
        return
      end
    end
    
    new_node.parent = parent
    @size += 1
    
    # Fix violations
    insert_fixup(new_node)
  end
  
  def search(key)
    node = find_node(key)
    node&.value
  end
  
  def size
    @size
  end
  
  private
  
  def find_node(key)
    current = @root
    while current
      return current if key == current.key
      current = key < current.key ? current.left : current.right
    end
    nil
  end
end

The insertion fixup method handles six cases that can occur when a newly inserted red node violates Property 4 (red node with red parent). The algorithm works up from the inserted node toward the root, recoloring and rotating as needed.

def insert_fixup(node)
  # While parent is red (violates Property 4)
  while node.parent&.red?
    if node.parent == node.parent.parent.left
      uncle = node.parent.parent.right
      
      # Case 1: Uncle is red - recolor
      if uncle&.red?
        node.parent.color = :black
        uncle.color = :black
        node.parent.parent.color = :red
        node = node.parent.parent
      else
        # Case 2: Node is right child - convert to Case 3
        if node == node.parent.right
          node = node.parent
          rotate_left(node)
        end
        
        # Case 3: Node is left child - rotate and recolor
        node.parent.color = :black
        node.parent.parent.color = :red
        rotate_right(node.parent.parent)
      end
    else
      # Mirror cases for right subtree
      uncle = node.parent.parent.left
      
      if uncle&.red?
        node.parent.color = :black
        uncle.color = :black
        node.parent.parent.color = :red
        node = node.parent.parent
      else
        if node == node.parent.left
          node = node.parent
          rotate_right(node)
        end
        
        node.parent.color = :black
        node.parent.parent.color = :red
        rotate_left(node.parent.parent)
      end
    end
  end
  
  @root.color = :black  # Property 2
end

Deletion proves more complex than insertion due to the need to handle both the standard BST deletion logic and the Red-Black property restoration. The algorithm first performs standard BST deletion, which may involve replacing the deleted node with its in-order successor. If a black node is deleted, the tree loses a black node from certain paths, violating Property 5.

def delete(key)
  node = find_node(key)
  return nil unless node
  
  @size -= 1
  deleted_value = node.value
  
  # Determine the node to actually remove
  if node.left && node.right
    # Node has two children - find successor
    successor = minimum(node.right)
    node.key = successor.key
    node.value = successor.value
    node = successor
  end
  
  # Node has at most one child
  child = node.left || node.right
  
  if node.black?
    node.color = child.color if child
    delete_fixup(node)
  end
  
  replace_node(node, child)
  deleted_value
end

def minimum(node)
  node = node.left while node.left
  node
end

def replace_node(old_node, new_node)
  if old_node.parent.nil?
    @root = new_node
  elsif old_node == old_node.parent.left
    old_node.parent.left = new_node
  else
    old_node.parent.right = new_node
  end
  
  new_node.parent = old_node.parent if new_node
end

The deletion fixup handles eight cases, working to restore black-height balance when a black node has been removed from a path. The algorithm terminates when either the fixup node is red (which can be recolored black) or the fixup node reaches the root.

def delete_fixup(node)
  while node != @root && node.black?
    if node == node.parent.left
      sibling = node.parent.right
      
      # Case 1: Sibling is red
      if sibling.red?
        sibling.color = :black
        node.parent.color = :red
        rotate_left(node.parent)
        sibling = node.parent.right
      end
      
      # Case 2: Sibling is black with black children
      if sibling.left.black? && sibling.right.black?
        sibling.color = :red
        node = node.parent
      else
        # Case 3: Sibling's right child is black
        if sibling.right.black?
          sibling.left.color = :black
          sibling.color = :red
          rotate_right(sibling)
          sibling = node.parent.right
        end
        
        # Case 4: Sibling's right child is red
        sibling.color = node.parent.color
        node.parent.color = :black
        sibling.right.color = :black
        rotate_left(node.parent)
        node = @root
      end
    else
      # Mirror cases for right child
      sibling = node.parent.left
      
      if sibling.red?
        sibling.color = :black
        node.parent.color = :red
        rotate_right(node.parent)
        sibling = node.parent.left
      end
      
      if sibling.right.black? && sibling.left.black?
        sibling.color = :red
        node = node.parent
      else
        if sibling.left.black?
          sibling.right.color = :black
          sibling.color = :red
          rotate_left(sibling)
          sibling = node.parent.left
        end
        
        sibling.color = node.parent.color
        node.parent.color = :black
        sibling.left.color = :black
        rotate_right(node.parent)
        node = @root
      end
    end
  end
  
  node.color = :black
end

Performance Considerations

Red-Black Trees guarantee O(log n) time complexity for search, insertion, and deletion operations in both average and worst-case scenarios. This worst-case guarantee distinguishes them from simpler structures like unbalanced binary search trees, which degrade to O(n) in worst-case scenarios.

The maximum height of a Red-Black Tree with n internal nodes is 2 * log₂(n + 1). This bound derives from the black-height property and the constraint that red nodes cannot have red children. A tree with black-height h contains at least 2^h - 1 internal nodes. Solving for height in terms of nodes yields h ≤ log₂(n + 1), and since the total height includes at most h red nodes interspersed with h black nodes, the maximum height is 2h.

Search operations traverse a single path from root to target (or leaf if not found), performing at most 2 * log₂(n + 1) comparisons. This provides predictable performance independent of insertion order, unlike unbalanced trees where search time depends on tree shape.

# Benchmark comparison
require 'benchmark'

def benchmark_operations(tree, n)
  keys = (1..n).to_a.shuffle
  
  Benchmark.bm(10) do |x|
    x.report("Insert:") do
      keys.each { |k| tree.insert(k, k * 2) }
    end
    
    x.report("Search:") do
      keys.sample(1000).each { |k| tree.search(k) }
    end
    
    x.report("Delete:") do
      keys.sample(100).each { |k| tree.delete(k) }
    end
  end
end

# Results for n = 10,000 show consistent O(log n) behavior
tree = RedBlackTree.new
benchmark_operations(tree, 10_000)

Insertion requires O(log n) time for the standard BST insertion phase, followed by fixup operations. The fixup performs at most two rotations and O(log n) recoloring operations in the worst case. Each rotation executes in O(1) time, making the overall insertion O(log n).

Deletion exhibits similar complexity characteristics but with different constants. The fixup phase may perform up to three rotations and O(log n) recoloring operations. The additional complexity stems from the need to handle the removed node's position in more cases than insertion.

Memory overhead for Red-Black Trees includes one extra bit (or byte in practice) per node for color storage, plus two or three pointers per node (left, right, and optionally parent). The parent pointer simplifies many algorithms but can be eliminated at the cost of more complex traversal logic. Total space complexity is O(n).

# Memory layout analysis
class RBNode
  # Key: 8 bytes (64-bit integer or reference)
  # Value: 8 bytes (reference)
  # Color: 1 byte (symbol stored as reference, effectively 8 bytes)
  # Left: 8 bytes (reference)
  # Right: 8 bytes (reference)
  # Parent: 8 bytes (reference)
  # Total per node: approximately 48 bytes + object overhead
end

Red-Black Trees perform fewer rotations than AVL trees during insertions and deletions because the balance criteria are less strict. An AVL tree requires rebalancing when subtree heights differ by more than 1, while Red-Black Trees tolerate height differences up to a factor of 2. This relaxed balance means Red-Black Trees execute fewer restructuring operations per modification.

For workloads with frequent insertions and deletions relative to searches, Red-Black Trees often outperform AVL trees despite having slightly longer search paths. The trade-off becomes relevant in scenarios like database indexing where modifications occur constantly, but searches must remain fast.

Cache performance deserves consideration in modern systems. Red-Black Trees exhibit poor cache locality compared to structures like B-trees because nodes scatter throughout memory rather than clustering. Each pointer dereference may result in a cache miss, limiting practical performance on large datasets. B-trees and their variants pack multiple keys per node, reducing pointer chasing and improving cache utilization.

Implementation Approaches

Several implementation variations exist for Red-Black Trees, each with different trade-offs in complexity, performance, and memory usage. The primary variations involve parent pointer management, NIL node handling, and the choice between recursive and iterative algorithms.

Parent Pointer Approach - The standard implementation maintains a parent pointer in each node, simplifying rotation logic and deletion operations. The parent pointer allows direct upward traversal during fixup operations without maintaining an explicit stack. This approach trades memory (8 bytes per node on 64-bit systems) for algorithmic simplicity. Rotation implementations become straightforward because the algorithm can update parent relationships directly.

# Parent pointer simplifies rotations
def rotate_left(node)
  right_child = node.right
  
  # Update parent relationships directly
  right_child.parent = node.parent
  if node.parent
    if node == node.parent.left
      node.parent.left = right_child
    else
      node.parent.right = right_child
    end
  else
    @root = right_child
  end
  
  node.right = right_child.left
  right_child.left.parent = node if right_child.left
  
  right_child.left = node
  node.parent = right_child
end

Parentless Approach - Eliminating parent pointers reduces memory overhead but requires maintaining an explicit stack during tree traversal for operations that need upward movement. Insertion and deletion must track the path from root to the operation point, storing visited nodes. This approach reduces memory by 25% but complicates algorithms and may increase cache misses due to stack operations.

# Stack-based insertion without parent pointers
def insert_with_stack(key, value)
  path = []
  current = @root
  
  while current
    path << current
    if key < current.key
      if current.left.nil?
        current.left = RBNode.new(key, value)
        insert_fixup_with_stack(current.left, path)
        return
      end
      current = current.left
    elsif key > current.key
      if current.right.nil?
        current.right = RBNode.new(key, value)
        insert_fixup_with_stack(current.right, path)
        return
      end
      current = current.right
    else
      current.value = value
      return
    end
  end
end

Sentinel NIL Node - Some implementations use a single sentinel node to represent all NIL nodes rather than using Ruby's nil. The sentinel node has color black, satisfying Property 3 uniformly. This approach eliminates nil checks throughout the code, replacing conditional logic with direct method calls on the sentinel. The sentinel node contains pointers back to itself for left, right, and parent, preventing null pointer issues.

class SentinelRBTree
  def initialize
    @nil_node = RBNode.new(nil, nil)
    @nil_node.color = :black
    @nil_node.left = @nil_node
    @nil_node.right = @nil_node
    @nil_node.parent = @nil_node
    @root = @nil_node
  end
  
  # Eliminates nil checks
  def insert_fixup(node)
    while node.parent.red?
      if node.parent == node.parent.parent.left
        uncle = node.parent.parent.right
        if uncle.red?  # Works on sentinel too
          # Fixup logic without nil checks
        end
      end
    end
  end
end

Left-Leaning Red-Black Trees - Robert Sedgewick introduced a variant that maintains an additional invariant: red links lean left. This constraint reduces the number of cases during insertion and deletion from six and eight to three and six respectively. The simpler algorithm trades some performance (requiring more rotations) for code clarity and reduced bug potential.

# Left-leaning invariant
def maintain_left_lean(node)
  # Rotate right links that are red
  if node.right&.red? && !node.left&.red?
    node = rotate_left(node)
  end
  
  # Balance 4-nodes
  if node.left&.red? && node.left.left&.red?
    node = rotate_right(node)
  end
  
  # Split 4-nodes
  if node.left&.red? && node.right&.red?
    flip_colors(node)
  end
  
  node
end

Recursive Implementation - Some implementations favor recursive algorithms over iterative ones, particularly for fixup operations. Recursive approaches often produce more concise code at the cost of stack space proportional to tree height. For large trees, recursive implementations risk stack overflow in pathological cases, though the O(log n) height guarantee keeps stack depth manageable for typical sizes.

The choice among these approaches depends on application requirements. Parent pointers offer the clearest, most maintainable code for general-purpose implementations. Parentless variants suit memory-constrained environments. Sentinel nodes work well when minimizing conditional logic matters more than the single extra node allocation. Left-leaning variants benefit applications where code simplicity outweighs raw performance.

Practical Examples

Red-Black Trees apply to scenarios requiring guaranteed logarithmic operations on dynamic ordered data. The examples below demonstrate common use patterns and highlight the structure's advantages over alternatives.

Priority-Based Task Scheduler - Operating systems and application frameworks need to schedule tasks based on priority while supporting dynamic priority changes. A Red-Black Tree provides efficient insertion, deletion, and minimum-finding operations required for this scenario.

class TaskScheduler
  Task = Struct.new(:id, :priority, :callback)
  
  def initialize
    @tasks = RedBlackTree.new
    @task_ids = {}
  end
  
  def schedule(task_id, priority, &callback)
    task = Task.new(task_id, priority, callback)
    @tasks.insert(priority, task)
    @task_ids[task_id] = priority
  end
  
  def execute_next
    # Find and remove highest priority (minimum value)
    min_node = find_minimum(@tasks.root)
    return nil unless min_node
    
    task = @tasks.delete(min_node.key)
    @task_ids.delete(task.id)
    task.callback.call
    task
  end
  
  def change_priority(task_id, new_priority)
    old_priority = @task_ids[task_id]
    return false unless old_priority
    
    task = @tasks.delete(old_priority)
    @tasks.insert(new_priority, task)
    @task_ids[task_id] = new_priority
    true
  end
  
  def pending_count
    @tasks.size
  end
  
  private
  
  def find_minimum(node)
    return nil if node.nil?
    node = node.left while node.left
    node
  end
end

# Usage
scheduler = TaskScheduler.new
scheduler.schedule(:email_send, 5) { puts "Sending email" }
scheduler.schedule(:backup, 1) { puts "Running backup" }
scheduler.schedule(:report, 3) { puts "Generating report" }

scheduler.execute_next  # Runs backup (priority 1)
scheduler.change_priority(:email_send, 2)
scheduler.execute_next  # Runs email_send (priority 2)

Range Query Server - Applications that need to find all records within a value range benefit from Red-Black Trees. The ordered structure allows efficient traversal of all elements between two keys without examining elements outside the range.

class RangeQueryIndex
  def initialize
    @tree = RedBlackTree.new
  end
  
  def add(key, record)
    records = @tree.search(key) || []
    records << record
    @tree.insert(key, records)
  end
  
  def range_query(min_key, max_key)
    results = []
    range_search(@tree.root, min_key, max_key, results)
    results.flatten
  end
  
  private
  
  def range_search(node, min_key, max_key, results)
    return if node.nil?
    
    # Search left subtree if range extends below node
    range_search(node.left, min_key, max_key, results) if min_key < node.key
    
    # Include node if within range
    results << node.value if min_key <= node.key && node.key <= max_key
    
    # Search right subtree if range extends above node
    range_search(node.right, min_key, max_key, results) if node.key < max_key
  end
end

# Usage for time-based queries
index = RangeQueryIndex.new

# Add events with timestamps
index.add(1609459200, {event: "login", user: "alice"})
index.add(1609462800, {event: "purchase", user: "bob"})
index.add(1609466400, {event: "logout", user: "alice"})
index.add(1609470000, {event: "login", user: "charlie"})

# Find all events between timestamps
events = index.range_query(1609460000, 1609468000)
# => Events from login to logout

Cache with LRU and Frequency Tracking - A sophisticated cache implementation that evicts items based on both access frequency and recency requires ordered access to items sorted by a composite score. Red-Black Trees maintain this ordering efficiently as access patterns change.

class AdaptiveCache
  CacheEntry = Struct.new(:key, :value, :access_count, :last_access)
  
  def initialize(capacity)
    @capacity = capacity
    @entries = {}  # key -> entry
    @access_tree = RedBlackTree.new  # score -> entry
    @time = 0
  end
  
  def get(key)
    entry = @entries[key]
    return nil unless entry
    
    # Remove old score
    old_score = calculate_score(entry)
    @access_tree.delete(old_score)
    
    # Update access stats
    entry.access_count += 1
    entry.last_access = @time += 1
    
    # Reinsert with new score
    new_score = calculate_score(entry)
    @access_tree.insert(new_score, entry)
    
    entry.value
  end
  
  def put(key, value)
    if @entries[key]
      # Update existing entry
      entry = @entries[key]
      old_score = calculate_score(entry)
      @access_tree.delete(old_score)
      
      entry.value = value
      entry.last_access = @time += 1
      
      new_score = calculate_score(entry)
      @access_tree.insert(new_score, entry)
    else
      # Evict if at capacity
      evict_lowest if @entries.size >= @capacity
      
      # Insert new entry
      entry = CacheEntry.new(key, value, 1, @time += 1)
      @entries[key] = entry
      
      score = calculate_score(entry)
      @access_tree.insert(score, entry)
    end
  end
  
  private
  
  def calculate_score(entry)
    # Lower score = higher eviction priority
    # Combine frequency and recency
    (entry.access_count * 1000) + entry.last_access
  end
  
  def evict_lowest
    # Find entry with lowest score
    min_node = find_minimum(@access_tree.root)
    return unless min_node
    
    entry = min_node.value
    @access_tree.delete(min_node.key)
    @entries.delete(entry.key)
  end
  
  def find_minimum(node)
    return nil if node.nil?
    node = node.left while node.left
    node
  end
end

# Usage
cache = AdaptiveCache.new(3)
cache.put("user:1", {name: "Alice"})
cache.put("user:2", {name: "Bob"})
cache.put("user:3", {name: "Charlie"})

cache.get("user:1")  # Increases access count
cache.get("user:1")  # Increases again

cache.put("user:4", {name: "David"})  # Evicts user:2 (lowest score)

Interval Tree for Scheduling - Applications managing overlapping time intervals (meeting scheduling, resource allocation) can build on Red-Black Trees to efficiently find all intervals overlapping a query interval.

class IntervalTree
  Interval = Struct.new(:start, :end, :data)
  
  class IntervalNode < RBNode
    attr_accessor :max_end
    
    def initialize(interval)
      super(interval.start, interval)
      @max_end = interval.end
    end
  end
  
  def initialize
    @root = nil
  end
  
  def insert(start_time, end_time, data)
    interval = Interval.new(start_time, end_time, data)
    node = IntervalNode.new(interval)
    
    # Standard RB tree insertion with max_end maintenance
    insert_node(node)
    update_max_end(node)
  end
  
  def find_overlapping(query_start, query_end)
    results = []
    search_overlapping(@root, query_start, query_end, results)
    results
  end
  
  private
  
  def search_overlapping(node, query_start, query_end, results)
    return if node.nil?
    
    interval = node.value
    
    # Check if current interval overlaps
    if interval.start < query_end && interval.end > query_start
      results << interval
    end
    
    # Search left if left subtree might contain overlaps
    if node.left && node.left.max_end > query_start
      search_overlapping(node.left, query_start, query_end, results)
    end
    
    # Search right if current node's start is before query end
    if node.key < query_end
      search_overlapping(node.right, query_start, query_end, results)
    end
  end
  
  def update_max_end(node)
    while node
      old_max = node.max_end
      left_max = node.left ? node.left.max_end : node.value.end
      right_max = node.right ? node.right.max_end : node.value.end
      node.max_end = [node.value.end, left_max, right_max].max
      
      break if node.max_end == old_max
      node = node.parent
    end
  end
end

# Usage for meeting room scheduling
schedule = IntervalTree.new
schedule.insert(9, 10, "Team standup")
schedule.insert(10, 11, "Code review")
schedule.insert(14, 15, "Client call")
schedule.insert(14, 16, "Design meeting")

# Find conflicts for proposed 13:30-15:30 meeting
conflicts = schedule.find_overlapping(13.5, 15.5)
# => ["Client call", "Design meeting"]

Common Pitfalls

Red-Black Tree implementations contain several subtle error sources that lead to incorrect behavior or property violations. Understanding these pitfalls prevents hours of debugging complex tree corruption.

Incorrect Parent Pointer Updates During Rotation - Rotations must update six pointers correctly: the rotating node's parent, child, and grandchild relationships, plus the corresponding updates in both directions. Missing any update causes tree structure corruption that may not manifest immediately.

# WRONG: Missing parent update for moved subtree
def rotate_left_wrong(node)
  right_child = node.right
  node.right = right_child.left
  # MISSING: right_child.left.parent = node if right_child.left
  
  right_child.parent = node.parent
  # ... rest of rotation
end

# This creates a broken tree where a node's left child
# points up to it, but the child's parent points elsewhere

# CORRECT: Update all parent pointers
def rotate_left(node)
  right_child = node.right
  node.right = right_child.left
  right_child.left.parent = node if right_child.left  # CRITICAL
  
  right_child.parent = node.parent
  update_parent_child_link(node, right_child)
  
  right_child.left = node
  node.parent = right_child
end

Forgetting to Recolor Root Black After Fixup - The insertion fixup algorithm propagates red nodes upward, potentially coloring the root red. Property 2 requires the root to always be black. Missing this final recoloring creates an invalid tree.

# WRONG: Omitting final root recoloring
def insert_fixup_wrong(node)
  while node.parent&.red?
    # ... fixup cases
  end
  # MISSING: @root.color = :black
end

# CORRECT: Always recolor root
def insert_fixup(node)
  while node.parent&.red?
    # ... fixup cases
  end
  @root.color = :black  # CRITICAL
end

Using Wrong Node as Fixup Starting Point in Deletion - Deletion fixup should begin at the node that replaced the deleted node, not the deleted node itself. Starting at the wrong position causes the algorithm to fix violations in the wrong part of the tree.

# WRONG: Starting fixup at deleted node
def delete_wrong(key)
  node = find_node(key)
  # ... deletion logic
  delete_fixup(node)  # WRONG: node is already removed
end

# CORRECT: Fixup starts at replacement node
def delete(key)
  node = find_node(key)
  # ... determine replacement child
  child = node.left || node.right
  
  if node.black?
    # Fixup at the child's position
    delete_fixup(child || node)
  end
  
  replace_node(node, child)
end

Null Pointer Dereference in Fixup Cases - Both insertion and deletion fixup access uncle, sibling, and other nodes that might be nil. Failing to check for nil before accessing color properties causes crashes. The code must treat nil nodes as black per Property 3.

# WRONG: Accessing color without nil check
if uncle.red?  # Crashes if uncle is nil
  # ...
end

# CORRECT: Nil-safe color check
if uncle&.red?  # Returns nil if uncle is nil, which is falsy
  # ...
end

# Or explicit helper
def red?(node)
  node && node.color == :red
end

def black?(node)
  node.nil? || node.color == :black
end

Incorrect Case Selection in Fixup Algorithms - The six insertion cases and eight deletion cases have specific preconditions. Checking conditions in the wrong order or missing conditions leads to applying the wrong transformation. Each case assumes previous cases have been checked and ruled out.

# WRONG: Checking cases in wrong order
def insert_fixup_wrong(node)
  while node.parent&.red?
    if node.parent == node.parent.parent.left
      uncle = node.parent.parent.right
      
      # WRONG: Checking node position before uncle color
      if node == node.parent.right
        # Case 2 transformation
      elsif uncle&.red?
        # Case 1 transformation - should be checked first
      end
    end
  end
end

# CORRECT: Check uncle color first
def insert_fixup(node)
  while node.parent&.red?
    if node.parent == node.parent.parent.left
      uncle = node.parent.parent.right
      
      if uncle&.red?
        # Case 1: recolor - handles all uncle-red situations
      else
        # Now we know uncle is black, check node position
        if node == node.parent.right
          # Case 2
        end
        # Case 3
      end
    end
  end
end

Not Maintaining Binary Search Tree Property During Restructuring - Rotations must preserve BST ordering: all left descendants less than parent, all right descendants greater. Incorrect rotation logic can break this invariant while maintaining valid Red-Black properties, creating a structure that is a valid Red-Black tree but not a valid BST.

# WRONG: Rotation that breaks BST property
def rotate_left_wrong(node)
  right_child = node.right
  node.right = right_child.right  # WRONG: should be right_child.left
  # This moves values that should be less than node to its right
end

# Verify BST property separately from RB properties
def verify_bst(node, min = -Float::INFINITY, max = Float::INFINITY)
  return true if node.nil?
  return false if node.key <= min || node.key >= max
  verify_bst(node.left, min, node.key) && 
    verify_bst(node.right, node.key, max)
end

Infinite Loops in Fixup Due to Missing State Changes - The fixup algorithms terminate when either the node becomes the root or the node is black. If neither condition changes during an iteration, the loop runs forever. Each iteration must either move the fixup node upward or terminate through recoloring.

# WRONG: Missing node advancement in deletion case
def delete_fixup_wrong(node)
  while node != @root && node.black?
    sibling = node.parent.right
    
    if sibling.left.black? && sibling.right.black?
      sibling.color = :red
      # MISSING: node = node.parent (infinite loop if node stays black)
    end
  end
end

# CORRECT: Advance node or change color to terminate
def delete_fixup(node)
  while node != @root && node.black?
    sibling = node.parent.right
    
    if sibling.left.black? && sibling.right.black?
      sibling.color = :red
      node = node.parent  # CRITICAL: move up the tree
    else
      # Other cases that either terminate or advance node
    end
  end
end

Handling Duplicate Keys Incorrectly - Red-Black Trees are sets by nature, not multisets. If duplicate keys need support, the implementation must explicitly handle them, typically by maintaining a list of values per key. Simply inserting duplicates as separate nodes violates BST properties.

# WRONG: Allowing duplicate keys as separate nodes
def insert_wrong(key, value)
  new_node = RBNode.new(key, value)
  # Always inserts as new node, even if key exists
  # Creates invalid BST with multiple nodes having same key
end

# CORRECT: Update existing node or maintain value list
def insert(key, value)
  # ... traverse to find position
  if key == current.key
    current.value = value  # Update existing
    return
  end
  # ... insert new node only for new keys
end

Reference

Core Properties

Time Complexity Guarantees

Space Complexity

Rotation Operations

Insertion Fixup Cases

Deletion Fixup Cases

Comparison with Other Trees

Method Reference

Property Verification Methods

Common Error Patterns