Class: RedBlackTree::Node

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

Direct Known Subclasses

EmptyNode

Defined Under Namespace

Classes: EmptyNode

Constant Summary collapse

UNDEFINED = 
Object.new

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(key, value, left, right, color = :RED) ⇒ Node

Returns a new instance of Node.



12
13
14
15
16
17
18
19
 
# File 'lib/red_black_tree.rb', line 12

def initialize(key, value, left, right, color = :RED)
  @key = key
  @value = value
  @left = left
  @right = right
  # new node is added as RED
  @color = color
end

Instance Attribute Details

#color ⇒ Object

Returns the value of attribute color.



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

def color
  @color
end

#key ⇒ Object (readonly)

Returns the value of attribute key.



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

def key
  @key
end

#left ⇒ Object

Returns the value of attribute left.



10
11
12
 
# File 'lib/red_black_tree.rb', line 10

def left
  @left
end

#right ⇒ Object

Returns the value of attribute right.



10
11
12
 
# File 'lib/red_black_tree.rb', line 10

def right
  @right
end

#value ⇒ Object (readonly)

Returns the value of attribute value.



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

def value
  @value
end

Instance Method Details

#black? ⇒ Boolean

Returns:

  • (Boolean) 


29
30
31
 
# File 'lib/red_black_tree.rb', line 29

def black?
  @color == :BLACK
end

#check_height ⇒ Object

for debugging



144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
 
# File 'lib/red_black_tree.rb', line 144

def check_height
  lh = @left.empty? ? 0 : @left.check_height
  rh = @right.empty? ? 0 : @right.check_height
  if red?
    if @left.red? or @right.red?
      puts dump_tree(STDERR)
      raise 'red/red assertion failed'
    end
  else
    if lh != rh
      puts dump_tree(STDERR)
      raise "black height unbalanced: #{lh} #{rh}"
    end
  end
  (lh > rh ? lh : rh) + (black? ? 1 : 0)
end

#delete(key) ⇒ Object

returns [deleted_node, new_root, is_rebalance_needed]



105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
 
# File 'lib/red_black_tree.rb', line 105

def delete(key)
  ret = self
  case key <=> @key
  when -1
    deleted, @left, rebalance = @left.delete(key)
    if rebalance
      ret, rebalance = rebalance_for_left_delete
    end
  when 0
    deleted = self
    ret, rebalance = delete_node
  when 1
    deleted, @right, rebalance = @right.delete(key)
    if rebalance
      ret, rebalance = rebalance_for_right_delete
    end
  else
    raise TypeError, "cannot compare #{key} and #{@key} with <=>"
  end
  [deleted, ret, rebalance]
end

#dump_sexp ⇒ Object 



133
134
135
136
137
138
139
140
141
 
# File 'lib/red_black_tree.rb', line 133

def dump_sexp
  left = @left.dump_sexp
  right = @right.dump_sexp
  if left or right
    '(' + [@key, left || '-', right].compact.join(' ') + ')'
  else
    @key
  end
end

#dump_tree(io, indent = '') ⇒ Object 



127
128
129
130
131
 
# File 'lib/red_black_tree.rb', line 127

def dump_tree(io, indent = '')
  @right.dump_tree(io, indent + '  ')
  io << indent << sprintf("#<%s:0x%010x %s %s> => %s", self.class.name, __id__, @color, @key.inspect, @value.inspect) << $/
  @left.dump_tree(io, indent + '  ')
end

#each {|[@key, @value]| ... } ⇒ Object

inorder

Yields:



42
43
44
45
46
 
# File 'lib/red_black_tree.rb', line 42

def each(&block)
  @left.each(&block)
  yield [@key, @value]
  @right.each(&block)
end

#each_key ⇒ Object 



48
49
50
51
52
 
# File 'lib/red_black_tree.rb', line 48

def each_key
  each do |k, v|
    yield k
  end
end

#each_value ⇒ Object 



54
55
56
57
58
 
# File 'lib/red_black_tree.rb', line 54

def each_value
  each do |k, v|
    yield v
  end
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


33
34
35
 
# File 'lib/red_black_tree.rb', line 33

def empty?
  false
end

#insert(key, value) ⇒ Object

returns new_root



69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
# File 'lib/red_black_tree.rb', line 69

def insert(key, value)
  ret = self
  case key <=> @key
  when -1
    @left = @left.insert(key, value)
    if black? and @right.black? and @left.red? and !@left.children_color?(:BLACK)
      ret = rebalance_for_left_insert
    end
  when 0
    @value = value
  when 1
    @right = @right.insert(key, value)
    if black? and @left.black? and @right.red? and !@right.children_color?(:BLACK)
      ret = rebalance_for_right_insert
    end
  else
    raise TypeError, "cannot compare #{key} and #{@key} with <=>"
  end
  ret.pullup_red
end

#keys ⇒ Object 



60
61
62
 
# File 'lib/red_black_tree.rb', line 60

def keys
  collect { |k, v| k }
end

#red? ⇒ Boolean

Returns:

  • (Boolean) 


25
26
27
 
# File 'lib/red_black_tree.rb', line 25

def red?
  @color == :RED
end

#retrieve(key) ⇒ Object

returns value



91
92
93
94
95
96
97
98
99
100
101
102
 
# File 'lib/red_black_tree.rb', line 91

def retrieve(key)
  case key <=> @key
  when -1
    @left.retrieve(key)
  when 0
    @value
  when 1
    @right.retrieve(key)
  else
    nil
  end
end

#set_root ⇒ Object 



21
22
23
 
# File 'lib/red_black_tree.rb', line 21

def set_root
  @color = :BLACK
end

#size ⇒ Object 



37
38
39
 
# File 'lib/red_black_tree.rb', line 37

def size
  @left.size + 1 + @right.size
end

#values ⇒ Object 



64
65
66
 
# File 'lib/red_black_tree.rb', line 64

def values
  collect { |k, v| v }
end