Module: RedBlackTree::Node::Implementation

Includes:
LeftRightElementReferencers, Utils
Included in:
RedBlackTree::Node
Defined in:
lib/red_black_tree/node.rb

Defined Under Namespace

Classes: StructuralError

Constant Summary collapse

RED = 
"red"
BLACK = 
"black"
COLOURS = 
[RED, BLACK].freeze
LEFT = 
"left"
RIGHT = 
"right"
DIRECTIONS = 
[LEFT, RIGHT].freeze

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from LeftRightElementReferencers

#[], #[]=

Instance Attribute Details

#colour ⇒ Object

Returns the value of attribute colour.



58
59
60
 
# File 'lib/red_black_tree/node.rb', line 58

def colour
  @colour
end

#data=(value) ⇒ Object (writeonly)

Sets the attribute data

Parameters:

  • value —

    the value to set the attribute data to.



57
58
59
 
# File 'lib/red_black_tree/node.rb', line 57

def data=(value)
  @data = value
end

#left ⇒ Object

Returns the value of attribute left.



58
59
60
 
# File 'lib/red_black_tree/node.rb', line 58

def left
  @left
end

#parent ⇒ Object

Returns the value of attribute parent.



58
59
60
 
# File 'lib/red_black_tree/node.rb', line 58

def parent
  @parent
end

#right ⇒ Object

Returns the value of attribute right.



58
59
60
 
# File 'lib/red_black_tree/node.rb', line 58

def right
  @right
end

#tree=(value) ⇒ Object (writeonly)

Sets the attribute tree

Parameters:

  • value —

    the value to set the attribute tree to.



57
58
59
 
# File 'lib/red_black_tree/node.rb', line 57

def tree=(value)
  @tree = value
end

Instance Method Details

#black! ⇒ Object 



65
 
# File 'lib/red_black_tree/node.rb', line 65

def black! = @colour = BLACK

#black? ⇒ Boolean

Returns:

  • (Boolean) 


64
 
# File 'lib/red_black_tree/node.rb', line 64

def black? = @colour == BLACK

#children ⇒ Object 



91
92
93
 
# File 'lib/red_black_tree/node.rb', line 91

def children
  [@left, @right]
end

#children_are_leaves? ⇒ Boolean

Returns:

  • (Boolean) 


70
 
# File 'lib/red_black_tree/node.rb', line 70

def children_are_leaves? = children.all?(&:leaf?)

#children_are_valid? ⇒ Boolean

Returns:

  • (Boolean) 


71
 
# File 'lib/red_black_tree/node.rb', line 71

def children_are_valid? = children.all?(&:valid?)

#close_nephew ⇒ Object 



101
102
103
104
105
 
# File 'lib/red_black_tree/node.rb', line 101

def close_nephew
  return unless sibling

  sibling[position]
end

#distant_nephew ⇒ Object 



107
108
109
110
111
 
# File 'lib/red_black_tree/node.rb', line 107

def distant_nephew
  return unless sibling

  sibling[opposite_position]
end

#leaf? ⇒ Boolean

Returns:

  • (Boolean) 


67
 
# File 'lib/red_black_tree/node.rb', line 67

def leaf? = black? && (instance_of? RedBlackTree::LeafNode)

#opposite_position ⇒ Object 



85
86
87
88
89
 
# File 'lib/red_black_tree/node.rb', line 85

def opposite_position
  return unless @parent

  opposite_direction position
end

#position ⇒ Object 



75
76
77
78
79
80
81
82
83
 
# File 'lib/red_black_tree/node.rb', line 75

def position
  return unless @parent

  case self.object_id
  when @parent.left.object_id then LEFT
  when @parent.right.object_id then RIGHT
  else raise StructuralError, "Disowned by parent"
  end
end

#red! ⇒ Object 



62
 
# File 'lib/red_black_tree/node.rb', line 62

def red! = @colour = RED

#red? ⇒ Boolean

Returns:

  • (Boolean) 


61
 
# File 'lib/red_black_tree/node.rb', line 61

def red? = @colour == RED

#sibling ⇒ Object 



95
96
97
98
99
 
# File 'lib/red_black_tree/node.rb', line 95

def sibling
  return unless @parent

  @parent[opposite_position]
end

#single_child_is_leaf? ⇒ Boolean Also known as: single_child_is_valid?

Returns:

  • (Boolean) 


72
 
# File 'lib/red_black_tree/node.rb', line 72

def single_child_is_leaf? = children.any?(&:leaf?) && !children_are_leaves?

#swap_colour_with!(other_node) ⇒ Object 



131
132
133
134
135
136
137
138
139
140
141
142
143
 
# File 'lib/red_black_tree/node.rb', line 131

def swap_colour_with! other_node
  temp_colour = @colour

  case other_node.colour
  when RED then red!
  when BLACK then black!
  end

  case temp_colour
  when RED then other_node.red!
  when BLACK then other_node.black!
  end
end

#swap_position_with!(other_node) ⇒ Object 



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
 
# File 'lib/red_black_tree/node.rb', line 145

def swap_position_with! other_node
  self_position = position
  other_position = other_node.position
  opp_other_position = opposite_direction other_position if other_position

  if other_node.parent.object_id == self.object_id
    self[other_position] = other_node[other_position]
    other_node[other_position] = self

    self[other_position].parent = self
    other_node.parent = @parent

    @parent[self_position] = other_node if self_position
    @parent = other_node

    temp_node = self[opp_other_position]
    self[opp_other_position] = other_node[opp_other_position]
    other_node[opp_other_position] = temp_node

    self[opp_other_position].parent = self
    other_node[opp_other_position].parent = other_node
  elsif other_node.object_id == @parent.object_id
    other_node.swap_position_with! self
  else
    other_node.parent[other_position] = self if other_node.parent
    @parent[self_position] = other_node if @parent

    temp_node = other_node.parent
    other_node.parent = @parent
    @parent = temp_node

    temp_node = other_node.left
    other_node.left = @left
    @left = temp_node

    @left.parent = self if @left
    other_node.left.parent = other_node if other_node.left

    temp_node = other_node.right
    other_node.right = @right
    @right = temp_node

    @right.parent = self if @right
    other_node.right.parent = other_node if other_node.right
  end
end

#valid? ⇒ Boolean

Returns:

  • (Boolean) 


68
 
# File 'lib/red_black_tree/node.rb', line 68

def valid? = (red? || black?) && !(instance_of? RedBlackTree::LeafNode)

#validate!(is_root = false) ⇒ Object

Raises:



113
114
115
116
117
 
# File 'lib/red_black_tree/node.rb', line 113

def validate! is_root = false
  return if (@parent || is_root) && @left && @right

  raise StructuralError, "Node is invalid"
end

#validate_free! ⇒ Object

Raises:



119
120
121
122
123
124
125
126
127
128
129
 
# File 'lib/red_black_tree/node.rb', line 119

def validate_free!
  raise StructuralError, "Node is still chained to a tree" if @tree

  anchors = []
  anchors << "parent" if @parent
  anchors << "left child" if @left && @left.valid?
  anchors << "right child" if @right && @right.valid?
  return if anchors.empty?

  raise StructuralError, "Node is still chained to #{anchors.join(", ")}"
end