Augmented Interval Tree

examples.rb

# Example of an Augmented Tree
#
# I have added an additional `lower_limit` method, which enables testing of overlapping children.
#
# See:
#   - https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree
#   - http://www.davismol.net/2016/02/07/data-structures-augmented-interval-tree-to-search-for-interval-overlapping/
#   - http://www.bowdoin.edu/~ltoma/teaching/cs231/fall08/Lectures/10-augmentedTrees/augtrees.pdf
#

a = RangeNode.new(1..5)
a.lower_limit # => 1
a.upper_limit # => 5

b = RangeNode.new(10..15)
a.insert(b)
a.lower_limit # => 1
a.upper_limit # => 15
b.lower_limit # => 10
b.upper_limit # => 15

c = RangeNode.new(4..11)
a.insert(c)
a.lower_limit # => 1
a.upper_limit # => 15
b.lower_limit # => 4
b.upper_limit # => 15
c.lower_limit # => 4
c.upper_limit # => 11

interval_node.rb

class IntervalNode

  attr_accessor :value, :left_node, :right_node, :min, :max, :lower_limit, :upper_limit

  def initialize(value)
    @value = value
  end

  def overlaps?(node)
    (min <=> node.upper_limit) <= 0 && (max <=> node.lower_limit) >= 0
  end

  def overlapped?
    (left_node && left_node.overlaps?(self)) || (right_node && right_node.overlaps?(self))
  end

  def lower_limit
    @lower_limit ||= [left_node.try(:lower_limit), right_node.try(:lower_limit), min].compact.min
  end

  def upper_limit
    @upper_limit ||= [left_node.try(:upper_limit), right_node.try(:upper_limit), max].compact.max
  end

  def insert(node)
    # reset max/min values for this node
    @lower_limit = @upper_limit = nil

    if node.min <= min
      if @left_node
        @left_node.insert(node)
      else
        @left_node = node
      end
    else
      if @right_node
        @right_node.insert(node)
      else
        @right_node = node
      end
    end
  end
end

range_node.rb

class RangeNode < IntervalNode

  def min
    @value.min
  end

  def max
    @value.max
  end

end