RedBlackTree

Version

Red-black tree data structure for Ruby.

Installation

Install the gem and add to the application's Gemfile by executing:

$ bundle add red-black-tree

If bundler is not being used to manage dependencies, install the gem by executing:

$ gem install red-black-tree

Usage

Work = Struct.new :min_latency, keyword_init: true

# Needs to be implemented by you
class WorkNode < RedBlackTree::Node
  def <=> other
    self.data.min_latency <=> other.data.min_latency
  end
end

tree = RedBlackTree.new

tree << WorkNode.new(Work.new min_latency: 0.8)
tree << WorkNode.new(Work.new min_latency: 1.2)
tree << WorkNode.new(Work.new min_latency: 0.8)
tree << WorkNode.new(Work.new min_latency: 0.4)

until tree.empty?
  work = tree.shift # 0.4, 0.8, 0.8, 1.2
  # process work
end

Performance

[!NOTE] Red-black trees are designed for specific use cases and are not intended as a general-purpose data structure. The comparisons below are provided merely to illustrate the performance characteristics of the gem. However, it is important to note that the benchmarks do not take into account the self-balancing nature of red-black trees.

Sort and iterate 10,000 elements

require "benchmark/ips"

Work = Struct.new :min_latency, keyword_init: true

class WorkNode < RedBlackTree::Node
  def <=> other
    self.data.min_latency <=> other.data.min_latency
  end
end

sample_data = 10_000.times.map { Work.new(min_latency: rand(1_000)) }

Benchmark.ips do |x|
  x.report("RedBlackTree") do
    tree = RedBlackTree.new
    sample_data.each { |work| tree << WorkNode.new(work); }
    tree.shift until tree.empty?
  end

  # 1:1 comparison
  x.report("Array (gradual sort)") do
    array = []
    sample_data.each { |work| array << work; array.sort_by!(&:min_latency); }
    array.shift until array.empty?
  end

  x.report("Array (single sort)") do
    array = []
    sample_data.each { |work| array << work; }
    array.sort_by!(&:min_latency)
    array.shift until array.empty?
  end

  x.compare!
end

#=> ruby 4.0.5 (2026-05-20 revision 64336ffd0e) +YJIT +PRISM [arm64-darwin23]
#=> Warming up --------------------------------------
#=>         RedBlackTree     1.000 i/100ms
#=> Array (gradual sort)     1.000 i/100ms
#=>  Array (single sort)    88.000 i/100ms
#=> Calculating -------------------------------------
#=>         RedBlackTree     16.106 (± 0.0%) i/s   (62.09 ms/i) -     81.000 in   5.029225s
#=> Array (gradual sort)      0.235 (± 0.0%) i/s     (4.25 s/i) -      2.000 in   8.507957s
#=>  Array (single sort)    886.474 (± 1.8%) i/s    (1.13 ms/i) -      4.488k in   5.062752s
#=> 
#=> Comparison:
#=>  Array (single sort):      886.5 i/s
#=>         RedBlackTree:       16.1 i/s - 55.04x  slower
#=> Array (gradual sort):        0.2 i/s - 3771.04x  slower

Sort and search 10,000 elements

require "benchmark/ips"

Work = Struct.new :min_latency, keyword_init: true

class WorkNode < RedBlackTree::Node
  def <=> other
    self.data.min_latency <=> other.data.min_latency
  end
end

sample_data = 10_000.times.map { Work.new(min_latency: rand(1_000)) }
search_sample = sample_data.sample

Benchmark.ips do |x|
  x.report("RedBlackTree#search") do
    tree = RedBlackTree.new
    sample_data.each { |work| tree << WorkNode.new(work); }
    raise unless tree.search { |node| node.data == search_sample }
  end

  # 1:1 comparison
  x.report("Array#find (gradual sort)") do
    array = []
    sample_data.each { |work| array << work; array.sort_by!(&:min_latency); }
    raise unless array.find { |work| work.min_latency == search_sample.min_latency }
  end

  x.report("Array#find (single sort)") do
    array = []
    sample_data.each { |work| array << work; }
    array.sort_by!(&:min_latency)
    raise unless array.find { |work| work.min_latency == search_sample.min_latency }
  end

  # 1:1 comparison
  x.report("Array#bsearch (gradual sort)") do
    array = []
    sample_data.each { |work| array << work; array.sort_by!(&:min_latency); }
    raise unless array.bsearch { |work| search_sample.min_latency <= work.min_latency }
  end

  x.report("Array#bsearch (single sort)") do
    array = []
    sample_data.each { |work| array << work; }
    array.sort_by!(&:min_latency)
    raise unless array.bsearch { |work| search_sample.min_latency <= work.min_latency }
  end

  x.compare!
end

#=> ruby 4.0.5 (2026-05-20 revision 64336ffd0e) +YJIT +PRISM [arm64-darwin23]
#=> Warming up --------------------------------------
#=>          RedBlackTree#search     3.000 i/100ms
#=>    Array#find (gradual sort)     1.000 i/100ms
#=>     Array#find (single sort)    84.000 i/100ms
#=> Array#bsearch (gradual sort)     1.000 i/100ms
#=>  Array#bsearch (single sort)    95.000 i/100ms
#=> Calculating -------------------------------------
#=>          RedBlackTree#search     39.110 (± 2.6%) i/s   (25.57 ms/i) -    198.000 in   5.062672s
#=>    Array#find (gradual sort)      0.236 (± 0.0%) i/s     (4.24 s/i) -      2.000 in   8.471965s
#=>     Array#find (single sort)    855.532 (± 1.5%) i/s    (1.17 ms/i) -      4.284k in   5.007411s
#=> Array#bsearch (gradual sort)      0.237 (± 0.0%) i/s     (4.23 s/i) -      2.000 in   8.456356s
#=>  Array#bsearch (single sort)    945.266 (± 4.9%) i/s    (1.06 ms/i) -      4.750k in   5.025042s
#=> 
#=> Comparison:
#=>  Array#bsearch (single sort):      945.3 i/s
#=>     Array#find (single sort):      855.5 i/s - 1.10x  slower
#=>          RedBlackTree#search:       39.1 i/s - 24.17x  slower
#=> Array#bsearch (gradual sort):        0.2 i/s - 3996.75x  slower
#=>    Array#find (gradual sort):        0.2 i/s - 4004.13x  slower

WIP Features

RedBlackTree#max
RedBlackTree#height

Development

After checking out the repo, run bin/setup to install dependencies. Then, run bundle exec rake test to run the tests. You can also run bin/console for an interactive prompt that will allow you to experiment.

Contributing

Bug reports and pull requests are welcome on GitHub at https://github.com/joshuay03/red-black-tree.

License

The gem is available as open source under the terms of the MIT License.

Code of Conduct

Everyone interacting in the RedBlackTree project's codebases, issue trackers, chat rooms and mailing lists is expected to follow the code of conduct.