Class: RedBlackTree

Inherits:
Object
  • Object
show all
Defined in:
lib/red-black-tree.rb,
lib/red_black_tree/node.rb,
lib/red_black_tree/utils.rb,
lib/red_black_tree/version.rb,
lib/red_black_tree/node/leaf_node.rb,
lib/red_black_tree/node/data_delegation.rb,
lib/red_black_tree/node/leaf_node_comparable.rb,
lib/red_black_tree/node/left_right_element_referencers.rb

Defined Under Namespace

Modules: DataDelegation Classes: Node

Constant Summary collapse

VERSION = 
"0.1.7"

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ RedBlackTree

Returns a new instance of RedBlackTree.



21
22
23
24
25
 
# File 'lib/red-black-tree.rb', line 21

def initialize
  @size = 0
  @root = nil
  @left_most_node = nil
end

Instance Attribute Details

#left_most_node ⇒ RedBlackTree::Node? (readonly) Also known as: min

Returns the left most node.

Returns:



18
19
20
 
# File 'lib/red-black-tree.rb', line 18

def left_most_node
  @left_most_node
end

#size ⇒ Integer (readonly)

Returns the number of valid/non-leaf nodes.

Returns:

  • (Integer) —

    the number of valid/non-leaf nodes



11
12
13
 
# File 'lib/red-black-tree.rb', line 11

def size
  @size
end

Instance Method Details

#<<(node) ⇒ RedBlackTree Also known as: add!

Traverses the tree, comparing existing nodes to the node to be added, and inserts the node with the appropriate parent and direction.

Parameters:

Returns:

Raises:

  • (ArgumentError) 


60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 
# File 'lib/red-black-tree.rb', line 60

def << node
  raise ArgumentError, "cannot add leaf node" if node.instance_of? LeafNode

  parent = @root
  direction = nil

  while parent
    direction = node >= parent ? Node::RIGHT : Node::LEFT
    break if (child = parent[direction]).leaf?

    parent = child
  end

  insert! node, parent, direction
end

#any? ⇒ true, false

Returns true if there are any valid/non-leaf nodes, and false if there are none.

Returns:

  • (true, false) 


37
38
39
 
# File 'lib/red-black-tree.rb', line 37

def any?
  !empty?
end

#clear! ⇒ RedBlackTree

Removes all nodes from the tree.

Returns:



235
236
237
238
239
240
241
 
# File 'lib/red-black-tree.rb', line 235

def clear!
  @root = nil
  @size = 0
  @left_most_node = nil

  self
end

#delete!(node) ⇒ RedBlackTree::Node?

Removes the given node from the tree.

Parameters:

Returns:

Raises:

  • (ArgumentError) 


144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
 
# File 'lib/red-black-tree.rb', line 144

def delete! node
  raise ArgumentError, "cannot delete leaf node" if node.instance_of? LeafNode

  if node.tree.nil?
    return
  elsif node.tree != self
    raise ArgumentError, "node does not belong to this tree"
  end

  original_node = node

  if node.children_are_valid?
    is_root = is_root? node

    successor = node.left
    successor = successor.left until successor.left.leaf?
    node.swap_colour_with! successor
    node.swap_position_with! successor
    node.swap_position_with! LeafNode.new

    @root = successor if is_root
  elsif node.single_child_is_valid?
    is_root = is_root? node

    valid_child = node.children.find(&:valid?)
    valid_child.black!
    node.swap_position_with! valid_child
    node.swap_position_with! LeafNode.new

    @root = valid_child if is_root
  elsif node.children_are_leaves?
    if is_root? node
      @root = nil
    elsif node.red?
      node.swap_position_with! LeafNode.new
    else
      loop do
        if node.sibling && node.sibling.valid? && node.sibling.red?
          node.parent.red!
          node.sibling.black!
          rotate_sub_tree! node.parent, node.position
        end

        if node.close_nephew && node.close_nephew.valid? && node.close_nephew.red?
          node.sibling.red! unless node.sibling.leaf?
          node.close_nephew.black!
          rotate_sub_tree! node.sibling, node.opposite_position
        end

        if node.distant_nephew && node.distant_nephew.valid? && node.distant_nephew.red?
          case node.parent.colour
          when Node::RED then node.sibling.red!
          when Node::BLACK then node.sibling.black!
          end
          node.parent.black!
          node.distant_nephew.black!
          rotate_sub_tree! node.parent, node.position

          break
        end

        if node.parent && node.parent.red?
          node.sibling.red! unless node.sibling.leaf?
          node.parent.black!

          break
        end

        if node.sibling && !node.sibling.leaf?
          node.sibling.red!
        end

        break unless node = node.parent
      end

      original_node.swap_position_with! LeafNode.new
    end
  end

  original_node.tree = nil
  original_node.validate_free!

  decrement_size!
  update_left_most_node!

  original_node
end

#empty? ⇒ true, false

Returns true if there are no valid/non-leaf nodes, and false if there are.

Returns:

  • (true, false) 


30
31
32
 
# File 'lib/red-black-tree.rb', line 30

def empty?
  @size == 0
end

#include?(data) ⇒ true, false

Returns true if there is a node which matches the given data/value, and false if there is not.

Returns:

  • (true, false) 


272
273
274
 
# File 'lib/red-black-tree.rb', line 272

def include? data
  !!search(data)
end

#search(data = nil) {|RedBlackTree::Node| ... } ⇒ RedBlackTree::Node? Also known as: find

Searches for a node which matches the given data/value.

Parameters:

  • data (any) (defaults to: nil) —

    the data to search for

Yields:

Returns:



248
249
250
251
252
253
254
255
256
257
258
 
# File 'lib/red-black-tree.rb', line 248

def search data = nil, &block
  if block_given?
    raise ArgumentError, "provide either data or block, not both for search" if data

    _search_by_block block, @root
  else
    raise ArgumentError, "data must be provided for search" unless data

    _search_by_data data, @root
  end
end

#select(&block) ⇒ Object Also known as: filter, find_all

Raises:

  • (ArgumentError) 


261
262
263
264
265
 
# File 'lib/red-black-tree.rb', line 261

def select &block
  raise ArgumentError, "block must be provided for select" unless block

  _select_by_block block, @root
end

#shift ⇒ RedBlackTree::Node?

Removes the left most node (the node with the lowest data value) from the tree.

Returns:



44
45
46
47
48
49
50
51
52
53
 
# File 'lib/red-black-tree.rb', line 44

def shift
  return unless @left_most_node

  node = @left_most_node.dup
  node.colour = node.parent = node.left = node.right = nil

  delete! @left_most_node

  node
end

#traverse_in_order(node = @root) {|RedBlackTree::Node| ... } ⇒ void Also known as: traverse

This method returns an undefined value.

Traverses the tree in in-order and yields each node.

Parameters:

Yields:



294
295
296
297
298
299
300
 
# File 'lib/red-black-tree.rb', line 294

def traverse_in_order node = @root, &block
  return if node.nil? || node.leaf?

  traverse_in_order node.left, &block
  block.call node
  traverse_in_order node.right, &block
end

#traverse_level_order {|RedBlackTree::Node| ... } ⇒ void

This method returns an undefined value.

Traverses the tree in level-order and yields each node.

Yields:



320
321
322
323
324
325
326
327
328
329
330
331
332
 
# File 'lib/red-black-tree.rb', line 320

def traverse_level_order &block
  return if @root.nil?

  queue = [@root]
  until queue.empty?
    node = queue.shift
    next if node.nil? || node.leaf?

    block.call node
    queue << node.left
    queue << node.right
  end
end

#traverse_post_order(node = @root) {|RedBlackTree::Node| ... } ⇒ void

This method returns an undefined value.

Traverses the tree in post-order and yields each node.

Parameters:

Yields:



308
309
310
311
312
313
314
 
# File 'lib/red-black-tree.rb', line 308

def traverse_post_order node = @root, &block
  return if node.nil? || node.leaf?

  traverse_post_order node.left, &block
  traverse_post_order node.right, &block
  block.call node
end

#traverse_pre_order(node = @root) {|RedBlackTree::Node| ... } ⇒ void

This method returns an undefined value.

Traverses the tree in pre-order and yields each node.

Parameters:

Yields:



281
282
283
284
285
286
287
 
# File 'lib/red-black-tree.rb', line 281

def traverse_pre_order node = @root, &block
  return if node.nil? || node.leaf?

  block.call node
  traverse_pre_order node.left, &block
  traverse_pre_order node.right, &block
end