Class: RBTree::Node

Inherits:
Object
  • Object
show all
Defined in:
lib/rbtree/node.rb

Overview

A node in the red-black tree.

Nodes should only be manipulated directly by the RedBlackTree class.

Direct Known Subclasses

GuardNode

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(key, value, guard) ⇒ Node

Creates a new node.

New tree nodes are red by default.



19
20
21
22
23
24
 
# File 'lib/rbtree/node.rb', line 19

def initialize(key, value, guard)
  @color = :red
  @key = key
  @value = value
  @left = @right = @parent = guard
end

Instance Attribute Details

#color ⇒ Object

Returns the value of attribute color.



11
12
13
 
# File 'lib/rbtree/node.rb', line 11

def color
  @color
end

#key ⇒ Object

Returns the value of attribute key.



8
9
10
 
# File 'lib/rbtree/node.rb', line 8

def key
  @key
end

#left ⇒ Object

Returns the value of attribute left.



12
13
14
 
# File 'lib/rbtree/node.rb', line 12

def left
  @left
end

#parent ⇒ Object

Returns the value of attribute parent.



14
15
16
 
# File 'lib/rbtree/node.rb', line 14

def parent
  @parent
end

#right ⇒ Object

Returns the value of attribute right.



13
14
15
 
# File 'lib/rbtree/node.rb', line 13

def right
  @right
end

#value ⇒ Object

Returns the value of attribute value.



9
10
11
 
# File 'lib/rbtree/node.rb', line 9

def value
  @value
end

Instance Method Details

#black? ⇒ Boolean

True for black nodes.

Returns:

  • (Boolean) 


27
28
29
 
# File 'lib/rbtree/node.rb', line 27

def black?
  @color == :black
end

#inspect ⇒ Object 



50
51
52
53
54
55
56
 
# File 'lib/rbtree/node.rb', line 50

def inspect
  <<ENDI
<RBTree::Node (#{@color}) #{@key.inspect} -> #{@value.inspect}
Left: [#{@left.inspect.gsub!("\n", "\n  ")}]
Right: [#{@right.inspect.gsub!("\n", "\n  ")}]>
ENDI
end

#red? ⇒ Boolean

True for red nodes.

Returns:

  • (Boolean) 


32
33
34
 
# File 'lib/rbtree/node.rb', line 32

def red?
  @color == :red
end

#to_a ⇒ Object

Returns an array of the node’s [key, value].

This method is used for nodes in a RBTree’s tree.



39
40
41
 
# File 'lib/rbtree/node.rb', line 39

def to_a
  [@key, @value]
end

#to_single_a ⇒ Object

Returns an array of the node’s [key, first value].

This method is used for nodes in a MultiRBTree’s tree.



46
47
48
 
# File 'lib/rbtree/node.rb', line 46

def to_single_a
  [@key, @value.first]
end