Class: LeftLeaningRedBlackTree::TreeNode

Inherits:
Object
  • Object
show all
Includes:
Printable
Defined in:
lib/left_leaning_red_black_tree/tree_node.rb

Direct Known Subclasses

NullNode

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from Printable

#all_elements_nil?, #max_level, #print_node, #print_white_spaces

Constructor Details

#initialize(key, payload = nil) ⇒ TreeNode

Returns a new instance of TreeNode.



7
8
9
10
11
12
13
14
15
16
 
# File 'lib/left_leaning_red_black_tree/tree_node.rb', line 7

def initialize(key, payload = nil)
  @key = key
  @payload = payload
  @color = RED
  unless key.nil?
    @left = NullNode.new
    @right = NullNode.new
  end
  self
end

Instance Attribute Details

#color ⇒ Object

Returns the value of attribute color.



5
6
7
 
# File 'lib/left_leaning_red_black_tree/tree_node.rb', line 5

def color
  @color
end

#key ⇒ Object

Returns the value of attribute key.



5
6
7
 
# File 'lib/left_leaning_red_black_tree/tree_node.rb', line 5

def key
  @key
end

#left ⇒ Object

Returns the value of attribute left.



5
6
7
 
# File 'lib/left_leaning_red_black_tree/tree_node.rb', line 5

def left
  @left
end

#payload ⇒ Object

Returns the value of attribute payload.



5
6
7
 
# File 'lib/left_leaning_red_black_tree/tree_node.rb', line 5

def payload
  @payload
end

#right ⇒ Object

Returns the value of attribute right.



5
6
7
 
# File 'lib/left_leaning_red_black_tree/tree_node.rb', line 5

def right
  @right
end

Instance Method Details

#black? ⇒ Boolean

Returns:

  • (Boolean) 


81
82
83
 
# File 'lib/left_leaning_red_black_tree/tree_node.rb', line 81

def black?
  !red?
end

#delete(key) ⇒ Object 



32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 
# File 'lib/left_leaning_red_black_tree/tree_node.rb', line 32

def delete(key)
  parent = self
  if key < @key
    if !@left.red? && !@left.left.red?
      parent = move_red_left
    end
    parent.left = parent.left.delete(key)
  else
    if @left.red?
      parent = rotate_right
    end
    if key == parent.key && parent.right.key.nil?
      return NullNode.new
    end
    if !parent.right.red? && !parent.right.left.red?
      parent = move_red_right
    end
    if key == parent.key
      parent.key = parent.right.min_node.key
      parent.right = parent.right.delete_min
    else
      parent.right = parent.right.delete(key)
    end
  end
  parent.fix_up
end

#delete_min ⇒ Object 



109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
 
# File 'lib/left_leaning_red_black_tree/tree_node.rb', line 109

def delete_min
  parent = self

  if @left.key.nil?
    return NullNode.new
  end

  if !@left.red? && !@left.left.red?
    parent = move_red_left
  end

  parent.left = parent.left.delete_min

  fix_up
end

#fix_up ⇒ Object 



155
156
157
158
159
160
161
162
163
164
165
 
# File 'lib/left_leaning_red_black_tree/tree_node.rb', line 155

def fix_up
  parent = self

  if left_rotation_required?
    parent = rotate_left
  elsif right_rotation_required?
    parent = rotate_right
  end

  parent
end

#flip_colors ⇒ Object 



85
86
87
88
89
 
# File 'lib/left_leaning_red_black_tree/tree_node.rb', line 85

def flip_colors
  @color = !@color
  @left.color = !@left.color
  @right.color = !@right.color
end

#insert(key, payload) ⇒ Object 



18
19
20
21
22
23
24
25
26
27
28
29
30
 
# File 'lib/left_leaning_red_black_tree/tree_node.rb', line 18

def insert(key, payload)
  if @left.red? && @right.red?
    flip_colors
  end

  if key <= @key
    @left = @left.insert(key, payload)
  else
    @right = @right.insert(key, payload)
  end

  fix_up
end

#min_node ⇒ Object 



125
126
127
128
129
130
131
132
 
# File 'lib/left_leaning_red_black_tree/tree_node.rb', line 125

def min_node
  cur_node = self
  while !cur_node.left.key.nil? do
    cur_node = cur_node.left
  end

  cur_node
end

#move_red_left ⇒ Object 



134
135
136
137
138
139
140
141
142
143
 
# File 'lib/left_leaning_red_black_tree/tree_node.rb', line 134

def move_red_left
  parent = self
  flip_colors
  if @right.left.red?
    @right = @right.rotate_right
    parent = rotate_left
    flip_colors
  end
  parent
end

#move_red_right ⇒ Object 



145
146
147
148
149
150
151
152
153
 
# File 'lib/left_leaning_red_black_tree/tree_node.rb', line 145

def move_red_right
  parent = self
  flip_colors
  if @left.left.red?
    parent = rotate_right
    flip_colors
  end
  parent
end

#null? ⇒ Boolean

Returns:

  • (Boolean) 


167
168
169
 
# File 'lib/left_leaning_red_black_tree/tree_node.rb', line 167

def null?
  false
end

#red? ⇒ Boolean

Returns:

  • (Boolean) 


77
78
79
 
# File 'lib/left_leaning_red_black_tree/tree_node.rb', line 77

def red?
  @color
end

#rotate_left ⇒ Object 



91
92
93
94
95
96
97
98
 
# File 'lib/left_leaning_red_black_tree/tree_node.rb', line 91

def rotate_left
  new_parent = @right
  @right = new_parent.left
  new_parent.left = self
  new_parent.color = @color
  @color = RED
  new_parent
end

#rotate_right ⇒ Object 



100
101
102
103
104
105
106
107
 
# File 'lib/left_leaning_red_black_tree/tree_node.rb', line 100

def rotate_right
  new_parent = @left
  @left = new_parent.right
  new_parent.right = self
  new_parent.color = @color
  @color = RED
  new_parent
end

#to_a ⇒ Object 



59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
 
# File 'lib/left_leaning_red_black_tree/tree_node.rb', line 59

def to_a

  if @key.nil?
    return []
  end

  # go down the left side

  array = @left.to_a

  # add the next lowest value to the array

  array << @payload

  # go down the right side

  array << @right.to_a

  array.flatten
end