Class: RBTree

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/rbtree.rb,
lib/rbtree/version.rb

Overview

A Red-Black Tree implementation providing efficient ordered key-value storage.

RBTree is a self-balancing binary search tree that maintains sorted order of keys and provides O(log n) time complexity for insertion, deletion, and lookup operations. The tree enforces the following red-black properties to maintain balance:

  1. Every node is either red or black
  2. The root is always black
  3. All leaves (nil nodes) are black
  4. Red nodes cannot have red children
  5. All paths from root to leaves contain the same number of black nodes

Features

  • Ordered iteration over key-value pairs
  • Range queries (less than, greater than, between)
  • Efficient min/max retrieval
  • Nearest key search for numeric keys
  • Tree integrity validation

Usage

# Create an empty tree
tree = RBTree.new

# Create from a hash
tree = RBTree.new({3 => 'three', 1 => 'one', 2 => 'two'})

# Create from an array of key-value pairs
tree = RBTree.new([[3, 'three'], [1, 'one'], [2, 'two']])

# Create using bracket notation
tree = RBTree[3 => 'three', 1 => 'one', 2 => 'two']

# Insert and retrieve values
tree.insert(5, 'five')
tree[4] = 'four'
puts tree[4]  # => "four"

# Iterate in sorted order
tree.each { |key, value| puts "#{key}: #{value}" }

Performance

All major operations (insert, delete, search) run in O(log n) time. Iteration over all elements takes O(n) time.

Author:

  • Masahito Suzuki

Since:

  • 0.1.0

Direct Known Subclasses

MultiRBTree

Defined Under Namespace

Classes: AutoShrinkNodePool, Node, NodeAllocator, NodePool

Constant Summary collapse

VERSION =

The version of the rbtree-ruby gem

Since:

  • 0.1.0

"0.4.0"

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(*args, overwrite: true, node_allocator: AutoShrinkNodePool.new, &block) ⇒ RBTree

Initializes a new RBTree.

The tree can be initialized empty or populated with initial data from a Hash, Array, or Enumerator. A block can also be provided to supply the initial data.

Examples:

Create an empty tree

tree = RBTree.new

Create from a hash

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

Create from an array

tree = RBTree.new([[1, 'one'], [2, 'two']])

Create with overwrite: false

tree = RBTree.new([[1, 'one'], [1, 'uno']], overwrite: false)

Parameters:

  • args (Hash, Array, nil) —

    optional initial data

  • overwrite (Boolean) (defaults to: true) —

    whether to overwrite existing keys (default: true)

  • node_allocator (NodeAllocator) (defaults to: AutoShrinkNodePool.new) —

    allocator instance to use (default: AutoShrinkNodePool.new)

Yield Returns:

  • (Object) —

    optional initial data

    • If a Hash is provided, each key-value pair is inserted into the tree
    • If an Array is provided, it should contain [key, value] pairs
    • If a block is provided, it is yielded to get the source data
    • If no arguments are provided, an empty tree is created

Raises:

  • (ArgumentError) —

    if arguments are invalid

Since:

  • 0.1.0



118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
 
# File 'lib/rbtree.rb', line 118

def initialize(*args, overwrite: true, node_allocator: AutoShrinkNodePool.new, &block)
  @nil_node = Node.new
  @nil_node.color = Node::BLACK
  @nil_node.left = @nil_node
  @nil_node.right = @nil_node
  @root = @nil_node
  @min_node = @nil_node
  @max_node = @nil_node
  @hash_index = {}  # Hash index for O(1) key lookup, one entry per node
  @node_allocator = node_allocator
  @key_count = 0
  @mod_count = 0    # bumped by changes a traversal can observe
  @key_class = nil  # single class of all keys, or false once mixed
  @coherent_keys = false

  @overwrite = overwrite

  if args.size > 0 || block_given?
    insert(*args, overwrite: overwrite, &block)
  end
end

Instance Attribute Details

#key_count ⇒ Integer (readonly)

Returns the number of key-value pairs stored in the tree.

Returns:

  • (Integer) —

    the number of entries in the tree

Since:

  • 0.1.0



82
83
84
 
# File 'lib/rbtree.rb', line 82

def key_count
  @key_count
end

Class Method Details

.[](*args) ⇒ RBTree

Creates a new RBTree from the given arguments.

This is a convenience method equivalent to RBTree.new(*args).

Examples:

tree = RBTree[1 => 'one', 2 => 'two', 3 => 'three']

Parameters:

  • args (Hash, Array) —

    optional initial data

Returns:

  • (RBTree) —

    a new RBTree instance

Since:

  • 0.1.0



92
93
94
 
# File 'lib/rbtree.rb', line 92

def self.[](*args)
  new(*args)
end

.coherent_key_class(klass) ⇒ Class

Declares that (a <=> b) == 0 and a.eql?(b) agree for instances of the given key class, speeding up lookups that miss the internal hash index.

Optimization hint only: undeclared classes are still handled correctly, at O(log n) per missed lookup. Declaring a class that does not satisfy this makes such lookups report a present key as absent.

Examples:

RBTree.coherent_key_class(Version)

Parameters:

  • klass (Class) —

    the key class to declare coherent

Returns:

  • (Class) —

    the declared class

Since:

  • 0.1.0



75
76
77
78
 
# File 'lib/rbtree.rb', line 75

def self.coherent_key_class(klass)
  COHERENT_KEY_CLASSES[klass] = true
  klass
end

Instance Method Details

#[](key_or_range) ⇒ Object, ...

Retrieves a value associated with the given key, or a range of entries if a Range is provided.

Examples:

Single key lookup

tree[2]      # => "two"

Range lookup

tree[2..4].to_a  # => [[2, "two"], [3, "three"], [4, "four"]]
tree[...3].to_a  # => [[1, "one"], [2, "two"]]

Parameters:

  • key_or_range (Object, Range) —

    the key to look up or a Range for query

  • ... (Hash) —

    additional options to pass to the respective lookup method

Returns:

  • (Object, Enumerator, nil) —
    • If a key is provided: the associated value, or nil if not found
    • If a Range is provided: an Enumerator yielding [key, value] pairs

Since:

  • 0.1.0



284
285
286
287
288
289
290
291
292
293
294
295
296
297
 
# File 'lib/rbtree.rb', line 284

def [](key_or_range, **)
  return value(key_or_range, **) if !key_or_range.is_a?(Range)

  r = key_or_range
  r.begin ? (
    r.end ?
      between(r.begin, r.end, include_max: !r.exclude_end?, **) :
      gte(r.begin, **)
  ) : (
    r.end ?
      (r.exclude_end? ? lt(r.end, **) : lte(r.end, **)) :
      each(**)
  )
end

#between(min, max, include_min: true, include_max: true, reverse: false, safe: false) {|key, value| ... } ⇒ Enumerator, RBTree

Retrieves all key-value pairs with keys within the specified range.

Examples:

tree = RBTree.new({1 => 'one', 2 => 'two', 3 => 'three', 4 => 'four', 5 => 'five'})
tree.between(2, 4).to_a  # => [[2, "two"], [3, "three"], [4, "four"]]
tree.between(2, 4, reverse: true).first  # => [4, "four"]

Parameters:

  • min (Object) —

    the lower bound

  • max (Object) —

    the upper bound

  • include_min (Boolean) (defaults to: true) —

    whether to include the lower bound (default: true)

  • include_max (Boolean) (defaults to: true) —

    whether to include the upper bound (default: true)

  • reverse (Boolean) (defaults to: false) —

    if true, iterate in descending order (default: false)

  • safe (Boolean) (defaults to: false) —

    if true, safe for modifications during iteration (default: false)

Yields:

  • (key, value) —

    each matching key-value pair (if block given)

Returns:

  • (Enumerator, RBTree) —

    Enumerator if no block given, self otherwise

Since:

  • 0.1.0



718
719
720
721
722
 
# File 'lib/rbtree.rb', line 718

def between(min, max, include_min: true, include_max: true, reverse: false, safe: false, &block)
  return enum_for(__method__, min, max, include_min: include_min, include_max: include_max, reverse: reverse, safe: safe) unless block_given?
  traverse_range(reverse, min, max, include_min, include_max, safe: safe, &block)
  self
end

#clear ⇒ RBTree

Removes all key-value pairs from the tree.

Runs in O(1): the nodes are left to the garbage collector, and the allocator is told of the bulk discard so that pool statistics stay accurate.

Returns:

Since:

  • 0.1.0



545
546
547
548
549
550
551
552
553
554
 
# File 'lib/rbtree.rb', line 545

def clear
  @node_allocator.discard(@key_count) if @key_count > 0
  @root = @min_node = @max_node = @nil_node
  @hash_index.clear
  @key_count = 0
  @key_class = nil
  @coherent_keys = false
  @mod_count += 1
  self
end

#delete_if {|key, value| ... } ⇒ RBTree, Enumerator

Deletes key-value pairs for which the block returns true. Modifies the tree in place.

Yields:

  • (key, value) —

    each key-value pair

Returns:

  • (RBTree, Enumerator) —

    self, or Enumerator if no block

Since:

  • 0.1.0



771
772
773
774
775
 
# File 'lib/rbtree.rb', line 771

def delete_if(&block)
  return enum_for(__method__) { size } unless block_given?
  each(safe: true) { |k, v| delete(k) if block.call(k, v) }
  self
end

#delete_key(key) ⇒ Object? Also known as: delete

Deletes the key-value pair with the specified key.

Entries whose value is nil or false are deleted correctly, so the return value alone cannot distinguish them from a missing key; use #has_key? first if that matters.

Examples:

tree = RBTree.new({1 => 'one', 2 => 'two'})
tree.delete(1)  # => "one"
tree.delete(3)  # => nil

Parameters:

  • key (Object) —

    the key to delete

Returns:

  • (Object, nil) —

    the value associated with the deleted key, or nil if not found

Since:

  • 0.1.0



503
504
505
506
507
508
 
# File 'lib/rbtree.rb', line 503

def delete_key(key)
  return nil unless (z = find_node(key))
  value = z.value
  delete_found_node(z)
  value
end

#each(reverse: false, safe: false) {|key, value| ... } ⇒ Enumerator, RBTree

Iterates over all key-value pairs in ascending (or descending) order.

Examples:

tree = RBTree.new({3 => 'three', 1 => 'one', 2 => 'two'})
tree.each { |k, v| puts "#{k}: #{v}" }
# Output:
# 1: one
# 2: two
# 3: three

# Reverse iteration
tree.each(reverse: true) { |k, v| ... }

# Safe iteration for modifications
tree.each(safe: true) do |k, v|
  tree.delete(k) if k.even?
end

Parameters:

  • reverse (Boolean) (defaults to: false) —

    if true, iterate in descending order (default: false)

  • safe (Boolean) (defaults to: false) —

    if true, safe for modifications during iteration (default: false)

Yields:

  • (key, value) —

    each key-value pair in the tree

Returns:

  • (Enumerator, RBTree) —

    an Enumerator if no block is given, self otherwise

Since:

  • 0.1.0



605
606
607
608
609
 
# File 'lib/rbtree.rb', line 605

def each(reverse: false, safe: false, &block)
  return enum_for(__method__, reverse: reverse, safe: safe) { size } unless block_given?
  traverse_range(reverse, nil, nil, false, false, safe: safe, &block)
  self
end

#empty? ⇒ Boolean

Checks if the tree is empty.

Returns:

  • (Boolean) —

    true if the tree contains no elements, false otherwise

Since:

  • 0.1.0



166
 
# File 'lib/rbtree.rb', line 166

def empty? = @hash_index.empty?

#first(n = nil) ⇒ Array?

Returns the first key-value pair, or the first n pairs, without removing them.

Examples:

tree = RBTree.new({3 => 'three', 1 => 'one', 2 => 'two'})
tree.first     # => [1, "one"]
tree.first(2)  # => [[1, "one"], [2, "two"]]

Parameters:

  • n (Integer, nil) (defaults to: nil) —

    number of leading pairs to return

Returns:

  • (Array, nil) —

    the pair, or the n smallest pairs in ascending order

Since:

  • 0.1.0



229
 
# File 'lib/rbtree.rb', line 229

def first(n = nil) = n.nil? ? min : take(n)

#gt(key, reverse: false, safe: false) {|key, value| ... } ⇒ Enumerator, RBTree

Retrieves all key-value pairs with keys greater than the specified key.

Examples:

tree = RBTree.new({1 => 'one', 2 => 'two', 3 => 'three', 4 => 'four'})
tree.gt(2).to_a  # => [[3, "three"], [4, "four"]]
tree.gt(2, reverse: true).first  # => [4, "four"]

Parameters:

  • key (Object) —

    the lower bound (exclusive)

  • reverse (Boolean) (defaults to: false) —

    if true, iterate in descending order (default: false)

  • safe (Boolean) (defaults to: false) —

    if true, safe for modifications during iteration (default: false)

Yields:

  • (key, value) —

    each matching key-value pair (if block given)

Returns:

  • (Enumerator, RBTree) —

    Enumerator if no block given, self otherwise

Since:

  • 0.1.0



681
682
683
684
685
 
# File 'lib/rbtree.rb', line 681

def gt(key, reverse: false, safe: false, &block)
  return enum_for(__method__, key, reverse: reverse, safe: safe) unless block_given?
  traverse_range(reverse, key, nil, false, false, safe: safe, &block)
  self
end

#gte(key, reverse: false, safe: false) {|key, value| ... } ⇒ Enumerator, RBTree

Retrieves all key-value pairs with keys greater than or equal to the specified key.

Examples:

tree = RBTree.new({1 => 'one', 2 => 'two', 3 => 'three', 4 => 'four'})
tree.gte(2).to_a  # => [[2, "two"], [3, "three"], [4, "four"]]
tree.gte(2, reverse: true).first  # => [4, "four"]

Parameters:

  • key (Object) —

    the lower bound (inclusive)

  • reverse (Boolean) (defaults to: false) —

    if true, iterate in descending order (default: false)

  • safe (Boolean) (defaults to: false) —

    if true, safe for modifications during iteration (default: false)

Yields:

  • (key, value) —

    each matching key-value pair (if block given)

Returns:

  • (Enumerator, RBTree) —

    Enumerator if no block given, self otherwise

Since:

  • 0.1.0



698
699
700
701
702
 
# File 'lib/rbtree.rb', line 698

def gte(key, reverse: false, safe: false, &block)
  return enum_for(__method__, key, reverse: reverse, safe: safe) unless block_given?
  traverse_range(reverse, key, nil, true, false, safe: safe, &block)
  self
end

#has_key?(key) ⇒ Boolean Also known as: key?

Checks if the tree contains the given key.

A key counts as present when (key <=> stored_key) == 0, even if the two objects are not eql? (e.g. 1.0 finds a stored 1).

Examples:

tree = RBTree.new({1 => 'one', 2 => 'two'})
tree.key?(1)    # => true
tree.key?(1.0)  # => true
tree.key?(3)    # => false

Parameters:

  • key (Object) —

    the key to search for

Returns:

  • (Boolean) —

    true if the key exists in the tree, false otherwise

Since:

  • 0.1.0



259
 
# File 'lib/rbtree.rb', line 259

def has_key?(key) = @hash_index.key?(key) || !find_node_by_order(key).nil?

#initialize_copy(orig) ⇒ void

This method returns an undefined value.

Creates a deep copy of the tree. Called automatically by dup and clone.

The copy shares the original's node allocator instance.

Parameters:

  • orig (RBTree) —

    the original tree to copy

Since:

  • 0.1.0



147
148
149
150
151
152
 
# File 'lib/rbtree.rb', line 147

def initialize_copy(orig)
  initialize(
    overwrite: orig.instance_variable_get(:@overwrite),
    node_allocator: orig.instance_variable_get(:@node_allocator))
  orig.each { |k, v| insert(k, v) }
end

#insert(*args, overwrite: @overwrite, &block) ⇒ Boolean? Also known as: []=

Inserts one or more key-value pairs into the tree.

This method supports both single entry insertion and bulk insertion.

Single insertion:

insert(key, value, overwrite: true)

Bulk insertion:

insert(hash, overwrite: true)
insert(array_of_pairs, overwrite: true)
insert(enumerator, overwrite: true)
insert { data_source }

If the key already exists and overwrite is true (default), the value is updated. If overwrite is false and the key exists, the operation returns nil without modification.

Examples:

Single insert

tree.insert(1, 'one')

Bulk insert from Hash

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

Bulk insert from Array

tree.insert([[1, 'one'], [2, 'two']])

Parameters:

  • args (Object) —

    key (and value) or source object

  • overwrite (Boolean) (defaults to: @overwrite) —

    whether to overwrite existing keys (default: true)

Yield Returns:

  • (Object) —

    data source for bulk insertion

Returns:

  • (Boolean, nil) —

    true if inserted/updated, nil if key exists and overwrite is false (for single insert)

Since:

  • 0.1.0



408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
 
# File 'lib/rbtree.rb', line 408

def insert(*args, overwrite: @overwrite, &block)
  if args.size == 2
    key, value = args
    insert_entry(key, value, overwrite: overwrite)
  else
    source = nil
    if args.empty? && block_given?
      source = yield
    elsif args.size == 1
      source = args[0]
    elsif args.empty?
      return # No-op
    else
      raise ArgumentError, "wrong number of arguments (given #{args.size}, expected 0..2)"
    end

    return if source.nil?

    unless source.respond_to?(:each)
      raise ArgumentError, "Source must be iterable"
    end

    # Self-insertion (e.g. tree.merge!(tree)) must not mutate what it iterates.
    source = source.to_a if source.equal?(self)

    source.each do |*pair|
      key, value = nil, nil
      if pair.size == 1 && pair[0].is_a?(Array)
        key, value = pair[0]
        raise ArgumentError, "Invalid pair size: #{pair[0].size} (expected 2)" unless pair[0].size == 2
      elsif pair.size == 2
        key, value = pair
      else
        raise ArgumentError, "Invalid pair format: #{pair.inspect}"
      end
      insert_entry(key, value, overwrite: overwrite)
    end
  end
end

#inspect ⇒ String

Returns a string representation of the tree.

Shows the first 5 entries and total size. Useful for debugging.

Returns:

  • (String) —

    a human-readable representation of the tree

Since:

  • 0.1.0



795
796
797
798
799
 
# File 'lib/rbtree.rb', line 795

def inspect
  content = take(5).map { |k, v| "#{k.inspect}=>#{v.inspect}" }.join(", ")
  suffix = size > 5 ? ", ..." : ""
  "#<#{self.class}:0x#{object_id.to_s(16)} size=#{size} {#{content}#{suffix}}>"
end

#invert ⇒ RBTree, MultiRBTree

Returns a new tree with keys and values swapped.

For RBTree, duplicate values result in later keys overwriting earlier ones. For MultiRBTree, all key-value pairs are preserved. Values must implement <=> to serve as keys in the new tree.

Returns:

Since:

  • 0.1.0



784
785
786
787
788
 
# File 'lib/rbtree.rb', line 784

def invert
  result = new_derived_tree
  each { |k, v| result.insert(v, k) }
  result
end

#keep_if {|key, value| ... } ⇒ RBTree, Enumerator

Keeps key-value pairs for which the block returns true, deleting the rest. Modifies the tree in place.

Yields:

  • (key, value) —

    each key-value pair

Returns:

  • (RBTree, Enumerator) —

    self, or Enumerator if no block

Since:

  • 0.1.0



761
762
763
764
765
 
# File 'lib/rbtree.rb', line 761

def keep_if(&block)
  return enum_for(__method__) { size } unless block_given?
  each(safe: true) { |k, v| delete(k) unless block.call(k, v) }
  self
end

#keys(reverse: false, safe: false) {|key| ... } ⇒ Enumerator, RBTree

Iterates over all keys in ascending (or descending) order.

Examples:

tree = RBTree.new({3 => 'three', 1 => 'one', 2 => 'two'})
tree.keys { |k| puts k }
# Output:
# 1
# 2
# 3

# Reverse iteration
tree.keys(reverse: true) { |k| ... }

# Safe iteration for modifications
tree.keys(safe: true) do |k|
  tree.delete(k) if k.even?
end

Parameters:

  • reverse (Boolean) (defaults to: false) —

    if true, iterate in descending order (default: false)

  • safe (Boolean) (defaults to: false) —

    if true, safe for modifications during iteration (default: false)

Yields:

  • (key) —

    each key in the tree

Returns:

  • (Enumerator, RBTree) —

    an Enumerator if no block is given, self otherwise

Since:

  • 0.1.0



577
578
579
580
581
582
 
# File 'lib/rbtree.rb', line 577

def keys(reverse: false, safe: false, &block)
  # `size`, not `key_count`: MultiRBTree yields a key once per value it holds.
  return enum_for(__method__, reverse: reverse, safe: safe) { size } unless block_given?
  each(reverse: reverse, safe: safe) { |key, _| yield key }
  self
end

#last(n = nil) ⇒ Array?

Returns the last key-value pair, or the last n pairs, without removing them.

Examples:

tree = RBTree.new({3 => 'three', 1 => 'one', 2 => 'two'})
tree.last     # => [3, "three"]
tree.last(2)  # => [[2, "two"], [3, "three"]]

Parameters:

  • n (Integer, nil) (defaults to: nil) —

    number of trailing pairs to return

Returns:

  • (Array, nil) —

    the pair, or the n largest pairs in ascending order

Since:

  • 0.1.0



239
240
241
242
243
244
245
 
# File 'lib/rbtree.rb', line 239

def last(n = nil)
  return max if n.nil?
  result = []
  reverse_each { |pair| break if result.size >= n; result << pair }
  result.reverse!
  result
end

#lt(key, reverse: false, safe: false) {|key, value| ... } ⇒ Enumerator, RBTree

Retrieves all key-value pairs with keys less than the specified key.

Examples:

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).first  # => [2, "two"]
tree.lt(3, safe: true) { |k, _| tree.delete(k) if k.even? }  # safe to delete

Parameters:

  • key (Object) —

    the upper bound (exclusive)

  • reverse (Boolean) (defaults to: false) —

    if true, iterate in descending order (default: false)

  • safe (Boolean) (defaults to: false) —

    if true, safe for modifications during iteration (default: false)

Yields:

  • (key, value) —

    each matching key-value pair (if block given)

Returns:

  • (Enumerator, RBTree) —

    Enumerator if no block given, self otherwise

Since:

  • 0.1.0



647
648
649
650
651
 
# File 'lib/rbtree.rb', line 647

def lt(key, reverse: false, safe: false, &block)
  return enum_for(__method__, key, reverse: reverse, safe: safe) unless block_given?
  traverse_range(reverse, nil, key, false, false, safe: safe, &block)
  self
end

#lte(key, reverse: false, safe: false) {|key, value| ... } ⇒ Enumerator, RBTree

Retrieves all key-value pairs with keys less than or equal to the specified key.

Examples:

tree = RBTree.new({1 => 'one', 2 => 'two', 3 => 'three', 4 => 'four'})
tree.lte(3).to_a  # => [[1, "one"], [2, "two"], [3, "three"]]
tree.lte(3, reverse: true).first  # => [3, "three"]

Parameters:

  • key (Object) —

    the upper bound (inclusive)

  • reverse (Boolean) (defaults to: false) —

    if true, iterate in descending order (default: false)

  • safe (Boolean) (defaults to: false) —

    if true, safe for modifications during iteration (default: false)

Yields:

  • (key, value) —

    each matching key-value pair (if block given)

Returns:

  • (Enumerator, RBTree) —

    Enumerator if no block given, self otherwise

Since:

  • 0.1.0



664
665
666
667
668
 
# File 'lib/rbtree.rb', line 664

def lte(key, reverse: false, safe: false, &block)
  return enum_for(__method__, key, reverse: reverse, safe: safe) unless block_given?
  traverse_range(reverse, nil, key, false, true, safe: safe, &block)
  self
end

#max(*args, &block) ⇒ Array?

Returns the maximum key-value pair without removing it.

With no argument and no block this is an O(1) cached lookup; given a count or a comparison block, Enumerable#max semantics apply instead.

Examples:

tree = RBTree.new({3 => 'three', 1 => 'one', 2 => 'two'})
tree.max     # => [3, "three"]
tree.max(2)  # => [[3, "three"], [2, "two"]]

Parameters:

  • args (Integer) —

    optional number of largest pairs to return

Returns:

  • (Array, nil) —

    the pair, or the n largest pairs, or nil if tree is empty

Since:

  • 0.1.0



216
217
218
219
 
# File 'lib/rbtree.rb', line 216

def max(*args, &block)
  return super if !args.empty? || block
  max_node&.pair
end

#max_key ⇒ Object?

Returns the maximum key without removing it.

Examples:

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

Returns:

  • (Object, nil) —

    the maximum key, or nil if tree is empty

Since:

  • 0.1.0



203
 
# File 'lib/rbtree.rb', line 203

def max_key = max_node&.key

#merge(other) {|key, old_value, new_value| ... } ⇒ RBTree

Returns a new tree containing the merged contents of self and other.

When a block is given, it is called with (key, old_value, new_value) for duplicate keys, and the block's return value is used.

Parameters:

  • other (RBTree, Hash, Enumerable) —

    the source to merge from

Yields:

  • (key, old_value, new_value) —

    called for duplicate keys when block given

Returns:

  • (RBTree) —

    a new tree with merged contents

Since:

  • 0.1.0



457
458
459
 
# File 'lib/rbtree.rb', line 457

def merge(other, &block)
  dup.merge!(other, &block)
end

#merge!(other, overwrite: true) {|key, old_value, new_value| ... } ⇒ RBTree

Merges the contents of another tree, hash, or enumerable into this tree.

When a block is given, it is called with (key, old_value, new_value) for duplicate keys, and the block's return value is used.

Parameters:

  • other (RBTree, Hash, Enumerable) —

    the source to merge from

  • overwrite (Boolean) (defaults to: true) —

    whether to overwrite existing keys (default: true). Ignored if block given.

Yields:

  • (key, old_value, new_value) —

    called for duplicate keys when block given

Returns:

Since:

  • 0.1.0



470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
 
# File 'lib/rbtree.rb', line 470

def merge!(other, overwrite: true, &block)
  if defined?(MultiRBTree) && other.is_a?(MultiRBTree)
    raise ArgumentError, "Cannot merge MultiRBTree into RBTree"
  end
  if block
    other_enum = other.is_a?(Hash) || other.is_a?(RBTree) ? other : other.each
    # Snapshot on self-merge; see RBTree#insert.
    other_enum = other_enum.to_a if other_enum.equal?(self)
    other_enum.each do |k, v|
      if has_key?(k)
        insert_entry(k, block.call(k, value(k), v), overwrite: true)
      else
        insert_entry(k, v)
      end
    end
  else
    insert(other, overwrite: overwrite)
  end
  self
end

#min(*args, &block) ⇒ Array?

Returns the minimum key-value pair without removing it.

With no argument and no block this is an O(1) cached lookup; given a count or a comparison block, Enumerable#min semantics apply instead.

Examples:

tree = RBTree.new({3 => 'three', 1 => 'one', 2 => 'two'})
tree.min     # => [1, "one"]
tree.min(2)  # => [[1, "one"], [2, "two"]]

Parameters:

  • args (Integer) —

    optional number of smallest pairs to return

Returns:

  • (Array, nil) —

    the pair, or the n smallest pairs, or nil if tree is empty

Since:

  • 0.1.0



192
193
194
195
 
# File 'lib/rbtree.rb', line 192

def min(*args, &block)
  return super if !args.empty? || block
  min_node&.pair
end

#min_key ⇒ Object?

Returns the minimum key without removing it.

Examples:

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

Returns:

  • (Object, nil) —

    the minimum key, or nil if tree is empty

Since:

  • 0.1.0



179
 
# File 'lib/rbtree.rb', line 179

def min_key = min_node&.key

#nearest(key) ⇒ Array(Object, Object)?

Returns the key-value pair with the key closest to the given key.

This method requires keys to be numeric or support subtraction and abs methods. If multiple keys have the same distance, the one with the smaller key is returned.

Examples:

tree = RBTree.new({1 => 'one', 5 => 'five', 10 => 'ten'})
tree.nearest(4)   # => [5, "five"]
tree.nearest(7)   # => [5, "five"]
tree.nearest(8)   # => [10, "ten"]

Parameters:

  • key (Numeric) —

    the target key

Returns:

  • (Array(Object, Object), nil) —

    a two-element array [key, value], or nil if tree is empty

Since:

  • 0.1.0



324
 
# File 'lib/rbtree.rb', line 324

def nearest(key) = ((n = find_nearest_node(key)) == @nil_node)? nil : n.pair

#nearest_key(key) ⇒ Object?

Returns the key with the key closest to the given key.

This method requires keys to be numeric or support subtraction and abs methods.

Examples:

tree = RBTree.new({1 => 'one', 5 => 'five', 10 => 'ten'})
tree.nearest_key(4)   # => 5
tree.nearest_key(7)   # => 5
tree.nearest_key(8)   # => 10

Parameters:

  • key (Numeric) —

    the target key

Returns:

  • (Object, nil) —

    the key, or nil if tree is empty

Since:

  • 0.1.0



310
 
# File 'lib/rbtree.rb', line 310

def nearest_key(key) = ((n = find_nearest_node(key)) == @nil_node)? nil : n.key

#pop ⇒ Array(Object, Object)?

Removes and returns the maximum key-value pair.

Examples:

tree = RBTree.new({3 => 'three', 1 => 'one', 2 => 'two'})
tree.pop  # => [3, "three"]
tree.pop  # => [2, "two"]

Returns:

  • (Array(Object, Object), nil) —

    a two-element array [key, value], or nil if tree is empty

Since:

  • 0.1.0



532
533
534
535
536
537
 
# File 'lib/rbtree.rb', line 532

def pop
  return nil unless (n = @max_node) != @nil_node
  pair = n.pair
  delete(n.key)
  pair
end

#prev(key) ⇒ Array(Object, Object)?

Returns the key-value pair with the largest key that is smaller than the given key.

If the key exists in the tree, returns the predecessor (previous element). If the key does not exist, returns the largest key-value pair with key < given key.

Examples:

tree = RBTree.new({1 => 'one', 3 => 'three', 5 => 'five', 7 => 'seven'})
tree.prev(5)   # => [3, "three"]
tree.prev(4)   # => [3, "three"] (4 does not exist)
tree.prev(1)   # => nil (no predecessor)

Parameters:

  • key (Object) —

    the reference key

Returns:

  • (Array(Object, Object), nil) —

    a two-element array [key, value], or nil if no predecessor exists

Since:

  • 0.1.0



352
 
# File 'lib/rbtree.rb', line 352

def prev(key) = ((n = find_predecessor_node(key)) == @nil_node)? nil : n.pair

#prev_key(key) ⇒ Object?

Returns the key with the largest key that is smaller than the given key.

If the key exists in the tree, returns the predecessor (previous element). If the key does not exist, returns the largest key with key < given key.

Examples:

tree = RBTree.new({1 => 'one', 3 => 'three', 5 => 'five', 7 => 'seven'})
tree.prev_key(5)   # => 3
tree.prev_key(4)   # => 3 (4 does not exist)
tree.prev_key(1)   # => nil (no predecessor)

Parameters:

  • key (Object) —

    the reference key

Returns:

  • (Object, nil) —

    the key, or nil if no predecessor exists

Since:

  • 0.1.0



338
 
# File 'lib/rbtree.rb', line 338

def prev_key(key) = ((n = find_predecessor_node(key)) == @nil_node)? nil : n.key

#reject {|key, value| ... } ⇒ RBTree, Enumerator

Returns a new tree containing key-value pairs for which the block returns false.

Yields:

  • (key, value) —

    each key-value pair

Returns:

  • (RBTree, Enumerator) —

    a new tree with non-rejected pairs, or Enumerator if no block

Since:

  • 0.1.0



739
740
741
742
743
744
 
# File 'lib/rbtree.rb', line 739

def reject(&block)
  return enum_for(__method__) { size } unless block_given?
  result = new_derived_tree
  each { |k, v| result.insert(k, v) unless block.call(k, v) }
  result
end

#reject! {|key, value| ... } ⇒ RBTree, ...

Deletes key-value pairs for which the block returns true. Returns nil if no changes were made.

Yields:

  • (key, value) —

    each key-value pair

Returns:

  • (RBTree, nil, Enumerator) —

    self if changed, nil if unchanged, or Enumerator if no block

Since:

  • 0.1.0



750
751
752
753
754
755
 
# File 'lib/rbtree.rb', line 750

def reject!(&block)
  return enum_for(__method__) { size } unless block_given?
  size_before = size
  delete_if(&block)
  size == size_before ? nil : self
end

#reverse_each(safe: false) {|key, value| ... } ⇒ Enumerator, RBTree

Iterates over all key-value pairs in descending order of keys.

Iterates over all key-value pairs in descending order of keys.

This is an alias for each(reverse: true).

Examples:

tree = RBTree.new({3 => 'three', 1 => 'one', 2 => 'two'})
tree.reverse_each { |k, v| puts "#{k}: #{v}" }
# Output:
# 3: three
# 2: two
# 1: one

Parameters:

  • safe (Boolean) (defaults to: false) —

    if true, safe for modifications during iteration (default: false)

Yields:

  • (key, value) —

    each key-value pair in the tree

  • (key, value) —

    each key-value pair in the tree

Returns:

  • (Enumerator, RBTree) —

    an Enumerator if no block is given, self otherwise

  • (Enumerator, RBTree) —

    an Enumerator if no block is given, self otherwise

See Also:

Since:

  • 0.1.0



630
631
632
633
 
# File 'lib/rbtree.rb', line 630

def reverse_each(safe: false, &block)
  return enum_for(__method__, safe: safe) { size } unless block_given?
  each(reverse: true, safe: safe, &block)
end

#select {|key, value| ... } ⇒ RBTree, Enumerator

Returns a new tree containing key-value pairs for which the block returns true.

Yields:

  • (key, value) —

    each key-value pair

Returns:

  • (RBTree, Enumerator) —

    a new tree with selected pairs, or Enumerator if no block

Since:

  • 0.1.0



728
729
730
731
732
733
 
# File 'lib/rbtree.rb', line 728

def select(&block)
  return enum_for(__method__) { size } unless block_given?
  result = new_derived_tree
  each { |k, v| result.insert(k, v) if block.call(k, v) }
  result
end

#shift ⇒ Array(Object, Object)?

Removes and returns the minimum key-value pair.

Examples:

tree = RBTree.new({3 => 'three', 1 => 'one', 2 => 'two'})
tree.shift  # => [1, "one"]
tree.shift  # => [2, "two"]

Returns:

  • (Array(Object, Object), nil) —

    a two-element array [key, value], or nil if tree is empty

Since:

  • 0.1.0



518
519
520
521
522
523
 
# File 'lib/rbtree.rb', line 518

def shift
  return nil unless (n = @min_node) != @nil_node
  pair = n.pair
  delete(n.key)
  pair
end

#size ⇒ Integer Also known as: value_count

Returns the number of key-value pairs stored in the tree.

Returns:

  • (Integer) —

    the number of entries in the tree

Since:

  • 0.1.0



170
 
# File 'lib/rbtree.rb', line 170

def size = @key_count

#succ(key) ⇒ Array(Object, Object)?

Returns the key-value pair with the smallest key that is larger than the given key.

If the key exists in the tree, returns the successor (next element). If the key does not exist, returns the smallest key-value pair with key > given key.

Examples:

tree = RBTree.new({1 => 'one', 3 => 'three', 5 => 'five', 7 => 'seven'})
tree.succ(5)   # => [7, "seven"]
tree.succ(4)   # => [5, "five"] (4 does not exist)
tree.succ(7)   # => nil (no successor)

Parameters:

  • key (Object) —

    the reference key

Returns:

  • (Array(Object, Object), nil) —

    a two-element array [key, value], or nil if no successor exists

Since:

  • 0.1.0



380
 
# File 'lib/rbtree.rb', line 380

def succ(key) = ((n = find_successor_node(key)) == @nil_node)? nil : n.pair

#succ_key(key) ⇒ Object?

Returns the key with the smallest key that is larger than the given key.

If the key exists in the tree, returns the successor (next element). If the key does not exist, returns the smallest key with key > given key.

Examples:

tree = RBTree.new({1 => 'one', 3 => 'three', 5 => 'five', 7 => 'seven'})
tree.succ_key(5)   # => 7
tree.succ_key(4)   # => 5 (4 does not exist)
tree.succ_key(1)   # => 3 (1 does not exist)

Parameters:

  • key (Object) —

    the reference key

Returns:

  • (Object, nil) —

    the key, or nil if no successor exists

Since:

  • 0.1.0



366
 
# File 'lib/rbtree.rb', line 366

def succ_key(key) = ((n = find_successor_node(key)) == @nil_node)? nil : n.key

#to_h ⇒ Hash

Returns a Hash containing all key-value pairs from the tree, in ascending key order.

Returns:

  • (Hash) —

    a new Hash with the tree's contents

Since:

  • 0.1.0



157
158
159
160
161
 
# File 'lib/rbtree.rb', line 157

def to_h
  h = {}
  each { |k, v| h[k] = v }
  h
end

#valid? ⇒ Boolean

Validates the red-black tree properties and the auxiliary structures.

Checks that:

  1. Root is black and has no parent
  2. All paths from root to leaves have the same number of black nodes
  3. No red node has a red child
  4. Keys are ordered against bounds inherited from ancestors
  5. Every child's parent pointer points back at its parent
  6. The Hash index holds exactly one entry per node, mapped to that node
  7. @min_node / @max_node are the actual extremes, and key_count is right

Returns:

  • (Boolean) —

    true if all properties are satisfied, false otherwise

Since:

  • 0.1.0



813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
 
# File 'lib/rbtree.rb', line 813

def valid?
  return false if @root.color == Node::RED
  return false if @root != @nil_node && @root.parent != @nil_node
  return false if check_black_height(@root) == -1
  return false unless check_order(@root, nil, nil)
  return false unless check_links(@root)

  count = 0
  first_node = nil
  last_node = nil
  indexed = true
  each_node_asc do |n|
    count += 1
    first_node ||= n
    last_node = n
    indexed &&= @hash_index[n.key].equal?(n)
  end

  return false unless indexed
  return false unless count == @key_count
  return false unless @hash_index.size == @key_count
  return false unless (first_node || @nil_node).equal?(@min_node)
  return false unless (last_node || @nil_node).equal?(@max_node)
  true
end

#value(key) ⇒ Object? Also known as: get

Retrieves the value associated with the given key.

Examples:

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

Parameters:

  • key (Object) —

    the key to look up

Returns:

  • (Object, nil) —

    the associated value, or nil if the key is not found

Since:

  • 0.1.0



269
 
# File 'lib/rbtree.rb', line 269

def value(key) = (@hash_index[key] || find_node_by_order(key))&.value