Class: Containers::RubyRBTreeMap::Node
- Inherits:
-
Object
- Object
- Containers::RubyRBTreeMap::Node
- Defined in:
- lib/containers/rb_tree_map.rb
Overview
:nodoc: all
Instance Attribute Summary collapse
-
#color ⇒ Object
Returns the value of attribute color.
-
#height ⇒ Object
Returns the value of attribute height.
-
#key ⇒ Object
Returns the value of attribute key.
-
#left ⇒ Object
Returns the value of attribute left.
-
#right ⇒ Object
Returns the value of attribute right.
-
#size ⇒ Object
Returns the value of attribute size.
-
#value ⇒ Object
Returns the value of attribute value.
Instance Method Summary collapse
- #colorflip ⇒ Object
- #fixup ⇒ Object
-
#initialize(key, value) ⇒ Node
constructor
A new instance of Node.
- #move_red_left ⇒ Object
- #move_red_right ⇒ Object
- #red? ⇒ Boolean
- #rotate_left ⇒ Object
- #rotate_right ⇒ Object
- #update_size ⇒ Object
Constructor Details
#initialize(key, value) ⇒ Node
Returns a new instance of Node.
205 206 207 208 209 210 211 212 213 |
# File 'lib/containers/rb_tree_map.rb', line 205 def initialize(key, value) @key = key @value = value @color = :red @left = nil @right = nil @size = 1 @height = 1 end |
Instance Attribute Details
#color ⇒ Object
Returns the value of attribute color.
204 205 206 |
# File 'lib/containers/rb_tree_map.rb', line 204 def color @color end |
#height ⇒ Object
Returns the value of attribute height.
204 205 206 |
# File 'lib/containers/rb_tree_map.rb', line 204 def height @height end |
#key ⇒ Object
Returns the value of attribute key.
204 205 206 |
# File 'lib/containers/rb_tree_map.rb', line 204 def key @key end |
#left ⇒ Object
Returns the value of attribute left.
204 205 206 |
# File 'lib/containers/rb_tree_map.rb', line 204 def left @left end |
#right ⇒ Object
Returns the value of attribute right.
204 205 206 |
# File 'lib/containers/rb_tree_map.rb', line 204 def right @right end |
#size ⇒ Object
Returns the value of attribute size.
204 205 206 |
# File 'lib/containers/rb_tree_map.rb', line 204 def size @size end |
#value ⇒ Object
Returns the value of attribute value.
204 205 206 |
# File 'lib/containers/rb_tree_map.rb', line 204 def value @value end |
Instance Method Details
#colorflip ⇒ Object
219 220 221 222 223 |
# File 'lib/containers/rb_tree_map.rb', line 219 def colorflip @color = @color == :red ? :black : :red @left.color = @left.color == :red ? :black : :red @right.color = @right.color == :red ? :black : :red end |
#fixup ⇒ Object
284 285 286 287 288 289 290 |
# File 'lib/containers/rb_tree_map.rb', line 284 def fixup rotate_left if @right && @right.red? rotate_right if (@left && @left.red?) && (@left.left && @left.left.red?) colorflip if (@left && @left.red?) && (@right && @right.red?) update_size end |
#move_red_left ⇒ Object
265 266 267 268 269 270 271 272 273 |
# File 'lib/containers/rb_tree_map.rb', line 265 def move_red_left colorflip if (@right.left && @right.left.red?) @right.rotate_right rotate_left colorflip end self end |
#move_red_right ⇒ Object
275 276 277 278 279 280 281 282 |
# File 'lib/containers/rb_tree_map.rb', line 275 def move_red_right colorflip if (@left.left && @left.left.red?) rotate_right colorflip end self end |
#red? ⇒ Boolean
215 216 217 |
# File 'lib/containers/rb_tree_map.rb', line 215 def red? @color == :red end |
#rotate_left ⇒ Object
237 238 239 240 241 242 243 244 245 246 247 248 249 |
# File 'lib/containers/rb_tree_map.rb', line 237 def rotate_left r = @right r_key, r_value, r_color = r.key, r.value, r.color b = r.left r.left = @left @left = r @right = r.right r.right = b r.color, r.key, r.value = :red, @key, @value @key, @value = r_key, r_value r.update_size update_size end |
#rotate_right ⇒ Object
251 252 253 254 255 256 257 258 259 260 261 262 263 |
# File 'lib/containers/rb_tree_map.rb', line 251 def rotate_right l = @left l_key, l_value, l_color = l.key, l.value, l.color b = l.right l.right = @right @right = l @left = l.left l.left = b l.color, l.key, l.value = :red, @key, @value @key, @value = l_key, l_value l.update_size update_size end |
#update_size ⇒ Object
225 226 227 228 229 230 231 232 233 234 235 |
# File 'lib/containers/rb_tree_map.rb', line 225 def update_size @size = (@left ? @left.size : 0) + (@right ? @right.size : 0) + 1 left_height = (@left ? @left.height : 0) right_height = (@right ? @right.height : 0) if left_height > right_height @height = left_height + 1 else @height = right_height + 1 end self end |