Class: RedBlackTree

Inherits:
Object
  • Object
show all
Includes:
Enumerable, Utils
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, LeafNodeComparable, Utils Classes: LeafNode, Node

Constant Summary collapse

VERSION = 
"0.1.9"

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ RedBlackTree

Returns a new instance of RedBlackTree.



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

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:



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

def left_most_node
  @left_most_node
end

#root ⇒ RedBlackTree::Node? (readonly)

Returns the root node.

Returns:



16
17
18
 
# File 'lib/red-black-tree.rb', line 16

def root
  @root
end

#size ⇒ Integer (readonly)

Returns the number of valid/non-leaf nodes.

Returns:

  • (Integer) —

    the number of valid/non-leaf nodes



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

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) 


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

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) 


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

def any?
  !empty?
end

#clear! ⇒ RedBlackTree

Removes all nodes from the tree.

Returns:



156
157
158
159
160
161
162
163
164
165
166
167
 
# File 'lib/red-black-tree.rb', line 156

def clear!
  traverse_post_order do |node|
    node.tree = nil
    node.colour = node.parent = node.left = node.right = nil
  end

  @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) 


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
151
 
# File 'lib/red-black-tree.rb', line 125

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

#each {|RedBlackTree::Node| ... } ⇒ void, Enumerator

Traverses the tree in in-order and yields each node. When called without a block, returns an Enumerator.

Yields:

Returns:

  • (void, Enumerator) 


207
208
209
210
211
 
# File 'lib/red-black-tree.rb', line 207

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

  traverse_in_order(&block)
end

#empty? ⇒ true, false

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

Returns:

  • (true, false) 


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

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) 


198
199
200
 
# File 'lib/red-black-tree.rb', line 198

def include? data
  !search(data).nil?
end

#insert!(node, target_parent = nil, direction = nil) ⇒ RedBlackTree

Inserts the given node using the given direction relative to the given parent.

Parameters:

  • node (RedBlackTree::Node) —

    the node to be inserted

  • target_parent (RedBlackTree::Node) (defaults to: nil) —

    the parent under which the node should be inserted

  • direction ("left", "right") (defaults to: nil) —

    the direction of the node relative to the parent

Returns:

Raises:

  • (ArgumentError) 


85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
 
# File 'lib/red-black-tree.rb', line 85

def insert! node, target_parent = nil, direction = nil
  raise ArgumentError, "cannot insert leaf node" if node.instance_of? LeafNode

  if target_parent.nil?
    raise ArgumentError, "Target parent must be provided for tree with root" if @root
  else
    raise ArgumentError, "Target parent direction must be provided" if direction.nil?
    raise ArgumentError, "Target parent already has #{direction} child" if (child = target_parent[direction]) && child.valid?
  end

  node.tree = self
  node.parent = nil
  node.left = LeafNode.new
  node.left.parent = node
  node.right = LeafNode.new
  node.right.parent = node

  if target_parent.nil?
    @root = node
    @root.black!
  else
    target_parent[direction] = node
    node.parent = target_parent
    node.red!

    rebalance_after_insertion! node
  end

  node.validate! @root == node

  increment_size!
  update_left_most_node!

  self
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:



174
175
176
177
178
179
180
181
182
183
184
 
# File 'lib/red-black-tree.rb', line 174

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) 


187
188
189
190
191
 
# File 'lib/red-black-tree.rb', line 187

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

  _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:



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

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:



231
232
233
234
235
236
237
 
# File 'lib/red-black-tree.rb', line 231

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:



257
258
259
260
261
262
263
264
265
266
267
 
# File 'lib/red-black-tree.rb', line 257

def traverse_level_order &block
  return if @root.nil?

  queue = [@root]
  until queue.empty?
    node = queue.shift
    block.call node
    queue << node.left unless node.left.leaf?
    queue << node.right unless node.right.leaf?
  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:



245
246
247
248
249
250
251
 
# File 'lib/red-black-tree.rb', line 245

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:



218
219
220
221
222
223
224
 
# File 'lib/red-black-tree.rb', line 218

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