Class: Tree::RedBlack

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

Overview

Tree::RedBlack is a pure-Ruby implementation of a Red-Black tree – i.e., a self-balancing binary search tree with O(log n) search, insert and delete operations. It is appropriate for maintaining an ordered collection where insertion and deletion are desired at arbitrary positions.

The implementation differs slightly from the Wikipedia description referenced above. In particular, leaf nodes are nil, which affects the details of node deletion.

Constant Summary collapse

VERSION = 
'0.4.3'

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(allow_duplicates = true) ⇒ RedBlack

Returns a new, empty Red-Black tree. If option allow_duplicates is false, then only unique values are inserted in a Red-Black tree.

The root attribute references the root node of the tree. The size attribute indicates the number of nodes in the tree. When size is 0, root is always nil.

Example

require 'tree/red_black'

rbt = Tree::RedBlack.new
p rbt.root              #=> nil
p rbt.size              #=> 0
p rbt.allow_duplicates? #=> true



43
44
45
46
47
 
# File 'lib/tree/red_black.rb', line 43

def initialize(allow_duplicates = true)
  @root = nil
  @size = 0
  @allow_duplicates = allow_duplicates
end

Instance Attribute Details

#allow_duplicates ⇒ Object

Returns the value of attribute allow_duplicates.



24
25
26
 
# File 'lib/tree/red_black.rb', line 24

def allow_duplicates
  @allow_duplicates
end

#root ⇒ Object

Returns the value of attribute root.



24
25
26
 
# File 'lib/tree/red_black.rb', line 24

def root
  @root
end

#size ⇒ Object

Returns the value of attribute size.



24
25
26
 
# File 'lib/tree/red_black.rb', line 24

def size
  @size
end

Instance Method Details

#allow_duplicates? ⇒ Boolean

Returns:

  • (Boolean) 


49
50
51
 
# File 'lib/tree/red_black.rb', line 49

def allow_duplicates?
  @allow_duplicates
end

#bsearch(&block) ⇒ Object

Returns a Red-Black tree node satisfying a criterion defined in block by binary search.

If block evaluates to true or false, returns the first node for which the block evaluates to true. In this case, the criterion is expected to return false for nodes preceding the matching node and true for subsequent nodes.

Example

require 'tree/red_black'

shuffled_values = [*1..10].shuffle
rbt = shuffled_values.reduce(Tree::RedBlack.new) do |acc, v|
  acc.insert(v)
end
rbt.bsearch { |node| node.key >= 7 }
                      #=> <Tree::RedBlackNode:0x00... @key=7 ...>

If block evaluates to <0, 0 or >0, returns first node for which block evaluates to 0. Otherwise returns nil. In this case, the criterion is expected to return <0 for nodes preceding the matching node, 0 for some subsequent nodes and >0 for nodes beyond that.

Example

require 'tree/red_black'

shuffled_values = [*1..10].shuffle
rbt = shuffled_values.reduce(Tree::RedBlack.new) do |acc, v|
  acc.insert(v)
end
rbt.bsearch { |node| 7 <=> node.key }
                      #=> <Tree::RedBlackNode:0x00... @key=7 ...>

If block+ is not given, returns an enumerator.



174
175
176
177
178
 
# File 'lib/tree/red_black.rb', line 174

def bsearch(&block)
  return enum_for(:bsearch) unless block_given?

  root ? root.bsearch(&block) : nil
end

#delete(*values) ⇒ Object

Deletes a value or sequence of values from a Red-Black tree.

Example

require 'tree/red_black'

rbt = Tree::RedBlack.new
rbt.insert(*1..10)      #=> #<Tree::RedBlack:0x00...>
p rbt.size              #=> 10
rbt.delete(*4..8)       #=> #<Tree::RedBlack:0x00...>
p rbt.size              #=> 5
rbt.map(&:key)          #=> [1, 2, 3, 9, 10]



107
108
109
110
111
112
113
114
115
116
117
 
# File 'lib/tree/red_black.rb', line 107

def delete(*values)
  values.each do |value; new_root|
    new_root = root.nil? ? nil : root.delete_red_black(value)
    unless new_root.nil?
      @root = new_root
      @size -= 1
    end
    @root = nil if size == 0
  end
  self
end

#dup ⇒ Object

Returns a deep copy of a Red-Black tree, provided that the dup method for values in the tree is also a deep copy.

Example

require 'tree/red_black'

rbt = Tree::RedBlack.new
rbt.insert({a: 1, b: 2})
rbt_copy = rbt.dup
p rbt.root.key            #=> {:a=>1, :b=>2}
p rbt.root.key.delete(:a) #=> 1
p rbt.root.key            #=> {:b=>2}
p rbt_copy.root.key       #=> {:a=>1, :b=>2}



233
234
235
236
237
238
239
 
# File 'lib/tree/red_black.rb', line 233

def dup
  copy = RedBlack.new
  copy.size = size
  copy.allow_duplicates = allow_duplicates
  copy.root = root.dup
  copy
end

#in_order(&block) ⇒ Object Also known as: each

Returns an enumerator for nodes in a Red-Black tree by in-order traversal. The each method is aliased to in_order

Example

require 'tree/red_black'

rbt = Tree::RedBlack.new
shuffled_values = [*1..10].shuffle
rbt.insert(*shuffled_values)
rbt.in_order.map(&:key)        #=> [1, 2, ..., 10]



210
211
212
213
214
215
 
# File 'lib/tree/red_black.rb', line 210

def in_order(&block)
  return enum_for(:in_order) unless block_given?
  return if root.nil?

  root.in_order(&block)
end

#insert(*values) ⇒ Object

Inserts a value or sequence of values in a Red-Black tree and increments the size attribute by the number of values inserted.

Since a Red-Black tree maintains an ordered, Enumerable collection, every value inserted must be comparable with every other value. Methods each, map, select, find, sort, etc., can be applied directly to the tree.

The individual nodes yielded by enumeration respond to method key to retrieve the value stored in that node. Method each, in particular, is aliased to in_order, so that nodes are sorted in ascending order by key value. Nodes can also be traversed by method pre_order, e.g., to generate paths in the tree.

Example

require 'tree/red_black'

rbt = Tree::RedBlack.new
rbt.insert(*1..10)      #=> #<Tree::RedBlack:0x00...>
p rbt.size              #=> 10
rbt.map(&:key)          #=> [1, 2, ..., 10]
rbt.select { |node| node.key % 2 == 0 }.map(&:key)
                        #=> [2, 4, ..., 10]



81
82
83
84
85
86
87
88
89
90
91
 
# File 'lib/tree/red_black.rb', line 81

def insert(*values)
  values.each do |value; new_root|
    new_root = (root.nil? ? RedBlackNode.new(value, :BLACK) :
                root.insert_red_black(value, @allow_duplicates))
    unless new_root.nil?
      @root = new_root
      @size += 1
    end
  end
  self
end

#pre_order(&block) ⇒ Object

Returns an enumerator for nodes in a Red-Black tree by pre-order traversal.

Example

require 'tree/red_black'

rbt = Tree::RedBlack.new
rbt.insert(*1..10)              #=> #<Tree::RedBlack:0x00...>
rbt.pre_order.map(&:key)        #=> [4, 2, 1, 3, 6, 5, 8, 7, 9, 10]



191
192
193
194
195
196
 
# File 'lib/tree/red_black.rb', line 191

def pre_order(&block)
  return enum_for(:pre_order) unless block_given?
  return if root.nil?

  root.pre_order(&block)
end

#search(value, ifnone = nil) ⇒ Object

Returns a Red-Black tree node whose key matches value by binary search. If no match is found, calls non-nil ifnone, otherwise returns nil.

Example

require 'tree/red_black'

shuffled_values = [*1..10].shuffle
rbt = shuffled_values.reduce(Tree::RedBlack.new) do |acc, v|
  acc.insert(v)
end
rbt.search(7)        #=> <Tree::RedBlackNode:0x00..., @key=7, ...>



133
134
135
 
# File 'lib/tree/red_black.rb', line 133

def search(value, ifnone = nil)
  root ? root.search(value, ifnone) : nil
end