rbtree-ruby

🌍 English | 日本語

A pure Ruby implementation of the Red-Black Tree data structure, providing efficient ordered key-value storage with O(log n) time complexity for insertion, deletion, and lookup operations.

Features

Self-Balancing Binary Search Tree: Maintains optimal performance through red-black tree properties. All insertions, deletions, and lookups run in O(log n).
Ordered Operations: Efficient sorted iteration, range queries (lt, gt, between), min/max retrieval.
Multi-Value Support: MultiRBTree class stores multiple values per key, with access to first or last value individually.
Pure Ruby: No C extensions required. Works on MRI, JRuby, TruffleRuby, and all Ruby implementations.
Hybrid Indexing: Internal hash index enables O(1) key lookup and membership checks — matching standard Hash performance — while ordering still decides key identity, so lookup and ordering never disagree (see Key Requirements).
Memory Efficiency: Node recycling with auto-shrinking pool (AutoShrinkNodePool) drastically reduces GC pressure in long-running apps.
Nearest Key Search: Finds the closest numeric key in O(log n) time — ideal for spatial or temporal queries.
Safe Iteration: Use safe: true to safely modify the tree (insert/delete) during iteration. Without it, modifying during iteration raises RuntimeError rather than silently misbehaving.

Installation

Add this line to your application's Gemfile:

gem 'rbtree-ruby'

And then execute:

bundle install

Or install it yourself as:

gem install rbtree-ruby

Usage

Basic RBTree

require 'rbtree'

# Create an empty tree
tree = RBTree.new

# Or initialize with data (Bulk Insert)
tree = RBTree.new({3 => 'three', 1 => 'one', 2 => 'two'})
tree = RBTree[[5, 'five'], [4, 'four']]
tree = RBTree.new do # Block initialization
  data_source.each { |data| [data.time, data.content] } 
end

# Insert and retrieve values
tree.insert(10, 'ten')
tree[20] = 'twenty'
# Bulk insert
tree.insert({30 => 'thirty', 40 => 'forty'})
puts tree[10]  # => "ten"

# Iterate in sorted order
tree.each { |key, value| puts "#{key}: #{value}" }
# Output:
# 1: one
# 2: two
# 3: three
# 10: ten
# 20: twenty

# Modification during iteration
# Unlike standard Ruby Hash/Array, modification during iteration is fully supported
# with the `safe: true` option. This allows you to delete or insert keys safely while iterating.
# Without it, modifying the tree mid-iteration raises RuntimeError (see "Iteration Safety").
tree.each(safe: true) { |k, v| tree.delete(k) if k.even? }
tree.each(reverse: true) { |k, v| puts k }  # Same as reverse_each

# Min and max — O(1), and Enumerable-compatible when given a count or a block
tree.min  # => [1, "one"]
tree.max  # => [20, "twenty"]
tree.first(2)  # => [[1, "one"], [2, "two"]]
tree.last(2)   # => [[10, "ten"], [20, "twenty"]]
tree.min(2)    # => [[1, "one"], [2, "two"]]

# Range queries (return Enumerator, use .to_a for Array)
tree.lt(10).to_a   # => [[1, "one"], [2, "two"], [3, "three"]]
tree.gte(10).each { |k, v| puts k } # Block iteration
tree.between(2, 10).to_a  # => [[2, "two"], [3, "three"], [10, "ten"]]

# Range objects in [] (v0.3.4+)
tree[..10].to_a    # lte(10)
tree[2..10].each { |k, v| ... } # Block iteration on Range
tree[2...10].to_a  # between(2, 10, include_max: false)
tree[10..].to_a    # gte(10)
tree[2..10, reverse: true].to_a # with options

# Shift and pop
tree.shift  # => [1, "one"] (removes minimum)
tree.pop    # => [20, "twenty"] (removes maximum)

# Delete
tree.delete(3)  # => "three"

# Check membership
tree.has_key?(2)  # => true
tree.size         # => 2

MultiRBTree with Duplicate Keys

require 'rbtree'

tree = MultiRBTree.new

# Insert multiple values for the same key
tree.insert(1, 'first one')
tree.insert(1, 'second one')
tree.insert(1, 'third one')
tree.insert(2, 'two')

tree.size  # => 4 (total number of key-value pairs)

# Get first value
tree.value(1)      # => "first one"
tree[1]          # => "first one"

# Get all values for a key (returns Enumerator)
tree.values(1).to_a  # => ["first one", "second one", "third one"]

# Iterate over all key-value pairs
tree.each { |k, v| puts "#{k}: #{v}" }
# Output:
# 1: first one
# 1: second one
# 1: third one
# 2: two

# Delete only first value
tree.delete_value(1)  # => "first one"
tree.value(1)         # => "second one"

# Delete all values for a key
tree.delete_key(1)      # removes all remaining values

Nearest Key Search

tree = RBTree.new({1 => 'one', 5 => 'five', 10 => 'ten'})

tree.nearest(4)   # => [5, "five"]  (closest key to 4)
tree.nearest(7)   # => [5, "five"]  (same distance, returns smaller key)
tree.nearest(8)   # => [10, "ten"]

Predecessor/Successor Search

Find the next or previous key in the tree:

tree = RBTree.new({1 => 'one', 3 => 'three', 5 => 'five', 7 => 'seven'})

tree.prev(5)   # => [3, "three"]  (largest key < 5)
tree.succ(5)   # => [7, "seven"]  (smallest key > 5)

# Works even if the key doesn't exist
tree.prev(4)   # => [3, "three"]  (4 doesn't exist, returns largest key < 4)
tree.succ(4)   # => [5, "five"]   (4 doesn't exist, returns smallest key > 4)

# Returns nil at boundaries
tree.prev(1)   # => nil (no key smaller than 1)
tree.succ(7)   # => nil (no key larger than 7)

Reverse Range Queries

All range queries return an Enumerator (use .to_a for Array) and support a :reverse option:

tree = RBTree.new({1 => 'one', 2 => 'two', 3 => 'three', 4 => 'four'})

tree.lt(3).to_a                    # => [[1, "one"], [2, "two"]]
tree.lt(3, reverse: true).to_a     # => [[2, "two"], [1, "one"]]
tree.lt(3).first                   # => [1, "one"] (lazy, no array created)

# Lazy evaluation
tree.gt(0).lazy.take(2).to_a  # => [[1, "one"], [2, "two"]] (only computes first 2)

Conversion and Merging

Seamlessly convert to standard Ruby objects or merge other collections:

tree = RBTree.new({1 => 'one', 2 => 'two'})

# Convert to Array (via Enumerable)
tree.to_a  # => [[1, "one"], [2, "two"]]

# Convert to Hash (keys are inserted in ascending order)
tree.to_h  # => {1 => "one", 2 => "two"}

# MultiRBTree maps each key to a copy of its value list
multi = MultiRBTree.new
multi.insert(1, 'a'); multi.insert(1, 'b')
multi.to_h  # => {1 => ["a", "b"]}

# Merge (destructive)
other = {3 => 'three'}
tree.merge!(other)
tree.size  # => 3

# Merge (non-destructive) — returns a new tree
merged = tree.merge({4 => 'four'})

# Merge with block for duplicate key resolution
merged = tree.merge({1 => 'ONE'}) { |key, old_val, new_val| old_val }

# Invert keys and values
tree = RBTree.new({1 => 'a', 2 => 'b', 3 => 'c'})
tree.invert.to_a  # => [["a", 1], ["b", 2], ["c", 3]]

Filtering and Copying

Note: dup, select, reject, delete_if, reject!, keep_if, invert, and merge are convenience methods composed from existing primitives. They provide no speed advantage over manual composition — their value is in readability and API completeness.

Create copies or filter trees using familiar Ruby idioms:

tree = RBTree.new({1 => 'one', 2 => 'two', 3 => 'three', 4 => 'four'})

# Deep copy — independent of original
copy = tree.dup
copy.delete(1)
tree.size  # => 4 (unchanged)

# select / reject — return a new tree
evens = tree.select { |k, _| k.even? }   # => {2=>"two", 4=>"four"}
odds  = tree.reject { |k, _| k.even? }   # => {1=>"one", 3=>"three"}

# delete_if / keep_if — modify in place
tree.delete_if { |k, _| k > 2 }
tree.to_a  # => [[1, "one"], [2, "two"]]

# reject! — like delete_if, but returns nil if nothing changed
tree.reject! { |_, _| false }  # => nil

For MultiRBTree, delete_if and keep_if operate at individual value granularity:

tree = MultiRBTree.new
tree.insert(1, 'a')
tree.insert(1, 'b')
tree.insert(2, 'c')

tree.delete_if { |k, v| k == 1 && v == 'a' }
tree.to_a  # => [[1, "b"], [2, "c"]]  — only 'a' was removed

MultiRBTree Value Array Access

For keys with multiple values, choose which value to access:

tree = MultiRBTree.new
tree.insert(1, 'first')
tree.insert(1, 'second')
tree.insert(1, 'third')

# Access first or last value
tree.value(1)               # => "first"
tree.value(1, last: true)   # => "third"
tree.first_value(1)         # => "first"
tree.last_value(1)          # => "third"

# Delete from either end
tree.delete_first_value(1)      # => "first"
tree.delete_last_value(1)       # => "third"  
tree.value(1)               # => "second"

# min/max with :last option
tree.insert(2, 'a')
tree.insert(2, 'b')
tree.min                  # => [1, "second"] (first value of min key)
tree.max(last: true)      # => [2, "b"]      (last value of max key)

Semantics

Key Requirements

Keys must be mutually comparable with <=>. Ordering — not eql?/hash — decides key identity: any key for which (key <=> stored_key) == 0 refers to the same entry.

tree = RBTree.new
tree[1] = 'int'

tree[1.0]           # => "int"   (1.0 <=> 1 is 0, so it is the same key)
tree.has_key?(1.0)  # => true
tree[1.0] = 'float'
tree.to_a           # => [[1, "float"]]  — the first key object inserted is kept

The internal hash index is keyed by eql?/hash, so a lookup like tree[1.0] above misses it and resolves through the tree instead. That fallback is skipped whenever it is provably futile — when every stored key and the lookup key share one class for which <=>-equality coincides with eql?, any matching key would already have been found in the index. Integer, Float, Rational, String, Symbol and Time qualify, so:

Tree	Lookup cost
Keys all of one core class above	O(1), hits and misses alike
Mixed key classes, or a custom key class	O(1) on a hash hit, O(log n) otherwise

A custom key class that defines <=> alongside a matching eql?/hash can opt into the O(1) path:

class Version
  include Comparable
  attr_reader :parts
  def initialize(parts) = @parts = parts
  def <=>(other) = parts <=> other.parts
  def eql?(other) = other.instance_of?(Version) && parts == other.parts
  def hash = parts.hash
end

RBTree.coherent_key_class(Version)

This is purely an optimization hint — without it such trees are still correct, just with an O(log n) descent on lookups that miss the index. A class that defines <=> but leaves eql?/hash at their default identity semantics must not be declared.

Keys that cannot be compared at all are reported as absent by lookups rather than raising:

tree['no <=> with Integer']       # => nil
tree.has_key?('...')             # => false
tree['...'] = 'x'                # raises ArgumentError — insertion needs an ordering

Iteration Safety

Iteration walks live node links, and deleted nodes are recycled by the allocator, so mutating the tree during a plain iteration is not merely lossy — it can yield keys out of order. This is detected and reported:

tree.each { |k, v| tree.delete(k) }
# => RuntimeError: can't modify RBTree during iteration (pass `safe: true` to iterate safely)

tree.each(safe: true) { |k, v| tree.delete(k) }   # supported

The guard covers each, reverse_each, keys, all range queries, and any Enumerator they return — including one held across a later mutation. Replacing the value of an existing key is not a structural change and stays allowed. delete_if, keep_if and reject! iterate safely on your behalf.

In MultiRBTree, safe: true snapshots each key's value list, so removing values while that key is being iterated will not skip its siblings; values removed during the iteration of their own key may still be yielded.

Thread Safety

No operation is synchronized. The tree, its hash index, and the node allocator are all shared mutable state, so concurrent access from multiple threads requires external locking. Note that a node allocator passed to several trees (including via dup) is shared state between them.

Performance

All major operations run in O(log n) time:

insert(key, value) - O(log n)
delete(key) - O(log n)
value(key) / [] - O(1) (O(log n) only for a miss on a mixed-class or custom-key tree — see Key Requirements)
has_key? - O(1) (same proviso)
min / max - O(1)
shift / pop - O(log n)
prev / succ - O(log n) with O(1) hash check and faster startup
clear - O(1) (nodes are left to the GC rather than recycled)

Iteration over all elements takes O(n) time.

On lookup misses: resolving key identity through ordering rather than eql? costs nothing for ordinary key types. Measured on a 200,000-entry Integer-keyed tree, 50,000 missing lookups take 8.1 ms against 6.3 ms for a bare hash probe — the difference is a class check, not a tree descent. Only a mixed-class or custom-key tree pays the descent (~1.4 µs per miss). Hits, insert, delete, iteration and range queries are unaffected.

RBTree vs Hash vs Array (Overwhelming Power)

For ordered and spatial operations, RBTree is not just faster—it is in a completely different class. The following benchmarks were conducted with 500,000 items:

Operation	RBTree	Hash/Array	Speedup	Why?
Nearest Key Search	O(log n)	O(n) scan	~8,600x faster	Spatial binary search vs full scan
Range Queries	O(log n + k)	O(n) filter	~540x faster	Direct subtree jump vs full scan
Min Extraction	O(log n)	O(n) search	~160x faster	Continuous rebalancing vs full scan
Sorted Iteration	O(n)	O(n log n)	FREE	Always sorted vs explicit `sort`
Key Lookup	O(1)	O(1)	Equal	Hybrid Hash Index provides O(1) access like standard Hash

Memory Efficiency & Custom Allocators

RBTree uses an internal Memory Pool to recycle node objects.

Significantly reduces Garbage Collection (GC) pressure during frequent insertions and deletions.
Auto-Shrinking: The default AutoShrinkNodePool automatically releases unused nodes back to Ruby's GC when the pool gets too large relative to current usage, preventing memory leaks in long-running applications with fluctuating workloads.
Customization: You can customize the pool behavior or provide your own allocator:

# Customize auto-shrink parameters
pool = RBTree::AutoShrinkNodePool.new(
  history_size: 60,       # 1 minute history
  buffer_factor: 1.5,     # Keep 50% buffer above fluctuation
  reserve_ratio: 0.2      # Always keep 20% reserve
)
tree = RBTree.new(node_allocator: pool)

When to Use RBTree

✅ Use RBTree when you need:

Ordered iteration by key
Fast min/max retrieval
Range queries (between, lt, gt, lte, gte)
Nearest key search
Priority queue behavior (shift/pop by key order)

✅ Use Hash when you only need:

Fast key-value lookup (RBTree is now equally fast!)
No ordering requirements

Run ruby demo.rb for a full benchmark demonstration.

API Documentation

Full RDoc documentation is available. Generate it locally with:

rdoc lib/rbtree.rb

Then open doc/index.html in your browser.

Development

After checking out the repo, run bundle install to install dependencies.can then run:

# Generate RDoc documentation
rake rdoc

# Build the gem
rake build

# Install locally
rake install

Contributing

Bug reports and pull requests are welcome on GitHub at https://github.com/firelzrd/rbtree-ruby.

License

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

Author

Masahito Suzuki (firelzrd@gmail.com)