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/leaf_node_comparable.rb,
lib/red_black_tree/node/left_right_element_referencers.rb

Defined Under Namespace

Classes: Node

Constant Summary collapse

VERSION = 
"0.1.2"

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ RedBlackTree

Returns a new instance of RedBlackTree.



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

def initialize
  @size = 0
  @left_most_node = nil
end

Instance Attribute Details

#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

#delete!(node) ⇒ RedBlackTree

Removes the given node from the tree.

Parameters:

Returns:

Raises:

  • (ArgumentError) 


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

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

  original_node = node

  if node.children_are_valid?
    successor = node.left
    successor = successor.left until successor.left.leaf?
    node.swap_data_with! successor

    return delete! successor
  elsif node.single_child_is_valid?
    is_root = is_root? node

    valid_child = node.children.find(&:valid?)
    node.swap_data_with! valid_child
    node.black!

    @root = node if is_root

    return delete! valid_child
  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.validate_free!

  decrement_size!
  update_left_most_node!

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


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

def include? data
  !!search(data)
end

#search(data) ⇒ RedBlackTree::Node?

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

Parameters:

  • data (any) —

    the data to search for

Returns:

Raises:

  • (ArgumentError) 


225
226
227
228
229
 
# File 'lib/red-black-tree.rb', line 225

def search data
  raise ArgumentError, "data must be provided for search" unless data

  _search data, @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