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.8"

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:



155
156
157
158
159
160
161
 
# File 'lib/red-black-tree.rb', line 155

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) 


124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
 
# File 'lib/red-black-tree.rb', line 124

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?
    delete_node_with_two_children! node
  elsif node.single_child_is_valid?
    delete_node_with_one_child! node
  elsif node.children_are_leaves?
    delete_leaf_node! node, original_node
  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) 


192
193
194
 
# File 'lib/red-black-tree.rb', line 192

def include? data
  !search(data).nil?
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:



168
169
170
171
172
173
174
175
176
177
178
 
# File 'lib/red-black-tree.rb', line 168

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) 


181
182
183
184
185
 
# File 'lib/red-black-tree.rb', line 181

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:



214
215
216
217
218
219
220
 
# File 'lib/red-black-tree.rb', line 214

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:



240
241
242
243
244
245
246
247
248
249
250
251
252
 
# File 'lib/red-black-tree.rb', line 240

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:



228
229
230
231
232
233
234
 
# File 'lib/red-black-tree.rb', line 228

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:



201
202
203
204
205
206
207
 
# File 'lib/red-black-tree.rb', line 201

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