Class: RBTree::Tree

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

Overview

Red-black tree implementation based on “Introduction to Algorithms” by CLRS.

Instances of this class are not thread-safe. However, using different instances in different threads is OK, unlike the original RedBlackTree class.

Direct Known Subclasses

TreeCmp

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Tree

Creates a new tree.



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

def initialize
  @guard = GuardNode.new
  @size = 0
  @root = @guard
end

Instance Attribute Details

#root ⇒ Object (readonly)

The tree’s root node.



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

def root
  @root
end

#size ⇒ Object (readonly)

The number of nodes in the tree.



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

def size
  @size
end

Instance Method Details

#black_height(node = root) ⇒ Object

Number of black nodes on each path from the given node to a leaf.

Red-black trees have the same number of black nodes on all paths from the root to leaves, so this function is well defined.



249
250
251
252
253
254
255
256
 
# File 'lib/rbtree/tree.rb', line 249

def black_height(node = root)
  height = 0
  while !node.nil?
    node = node.left
    height += 1 if node.nil? || node.black?
  end
  height
end

#delete(z) ⇒ Object

Removes a node from the tree.



107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
 
# File 'lib/rbtree/tree.rb', line 107

def delete(z)
  y = (z.left.nil? || z.right.nil?) ? z : successor(z)
  x = y.left.nil? ? y.right : y.left
  x.parent = y.parent

  if y.parent.nil?
    @root = x
  else
    if y == y.parent.left
      y.parent.left = x
    else
      y.parent.right = x
    end
  end

  if y != z
    z.key = y.key
    z.value = y.value
  end

  if y.color == :black
    delete_fixup(x)
  end

  @size -= 1
  y
end

#empty? ⇒ Boolean

True if the tree has no nodes in it.

Returns:

  • (Boolean) 


241
242
243
 
# File 'lib/rbtree/tree.rb', line 241

def empty?
  @root.nil?
end

#initialize_copy(source) ⇒ Object

Makes a deep copy of the source’s tree, but uses the original keys & values.



27
28
29
30
31
 
# File 'lib/rbtree/tree.rb', line 27

def initialize_copy(source)
  super
  @guard = GuardNode.new
  @root = clone_tree source.root, source.guard
end

#inorder(node = root) ⇒ Object

Yields all nodes in the given node’s subtree, in ascending key order.



176
177
178
179
180
181
182
 
# File 'lib/rbtree/tree.rb', line 176

def inorder(node = root)
  node = self.minimum
  until node.nil?
    yield node
    node = successor node
  end
end

#insert(node) ⇒ Object

Adds a new Node to the tree.

Returns the given node, if it was inserted into the tree. If a node with same key already existed, that node is returned instead, and the given node is not inserted into the tree.



62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
 
# File 'lib/rbtree/tree.rb', line 62

def insert(node)
  x = insert_helper node
  return x unless x == node

  x.color = :red
  while x != @root && x.parent.color == :red
    if x.parent == x.parent.parent.left
      y = x.parent.parent.right
      if !y.nil? && y.color == :red
        x.parent.color = :black
        y.color = :black
        x.parent.parent.color = :red
        x = x.parent.parent
      else
        if x == x.parent.right
          x = x.parent
          left_rotate x
        end
        x.parent.color = :black
        x.parent.parent.color = :red
        right_rotate x.parent.parent
      end
    else
      y = x.parent.parent.left
      if !y.nil? && y.color == :red
        x.parent.color = :black
        y.color = :black
        x.parent.parent.color = :red
        x = x.parent.parent
      else
        if x == x.parent.left
          x = x.parent
          right_rotate x
        end
        x.parent.color = :black
        x.parent.parent.color = :red
        left_rotate x.parent.parent
      end
    end
  end
  @root.color = :black
  node
end

#lower_bound(key, node = root) ⇒ Object

Returns the node with the smallest key that is >= the given key.

Returns nil if called on an empty tree or the guard node.



205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
 
# File 'lib/rbtree/tree.rb', line 205

def lower_bound(key, node = root)
  return nil if node.nil?
  loop do
    cmp = key <=> node.key
    return node if cmp == 0
    if cmp < 0
      next_node = node.left
      return node if next_node.nil?
    else
      next_node = node.right
      return successor(node) if next_node.nil?
    end
    node = next_node
  end
end

#maximum(node = root) ⇒ Object

The node with the highest key in the subtree rooted at the given node.



144
145
146
147
148
149
 
# File 'lib/rbtree/tree.rb', line 144

def maximum(node = root)
  while !node.right.nil?
    node = node.right
  end
  node
end

#minimum(node = root) ⇒ Object

The node with lowest key in the subtree rooted at the given node.



136
137
138
139
140
141
 
# File 'lib/rbtree/tree.rb', line 136

def minimum(node = root)
  while !node.left.nil?
    node = node.left
  end
  node
end

#node(key, value) ⇒ Object

Creates a new node holding a given key and value.



53
54
55
 
# File 'lib/rbtree/tree.rb', line 53

def node(key, value)
  RBTree::Node.new key, value, @guard
end

#predecessor(x) ⇒ Object

The node with the highest key that is lower than the given node’s key.



164
165
166
167
168
169
170
171
172
173
 
# File 'lib/rbtree/tree.rb', line 164

def predecessor(x)
  return maximum(x.left) unless x.left.nil?
  
  y = x.parent
  while !y.nil? && x == y.left
    x = y
    y = y.parent
  end
  y
end

#reverse_inorder(node = root) ⇒ Object

Yields all nodes in the given node’s subtree, in descending key order.



185
186
187
188
189
190
191
 
# File 'lib/rbtree/tree.rb', line 185

def reverse_inorder(node = root)
  node = self.maximum
  until node.nil?
    yield node
    node = predecessor node
  end
end

#search(key, node = root) ⇒ Object

Returns a node containing the given key or nil if no node contains the key.



194
195
196
197
198
199
200
 
# File 'lib/rbtree/tree.rb', line 194

def search(key, node = root)
  until node.nil?
    return node if node.key == key
    node = ((key <=> node.key) < 0) ? node.left : node.right
  end
  nil
end

#successor(x) ⇒ Object

The node with the lowest key that is higher than the given node’s key.



152
153
154
155
156
157
158
159
160
161
 
# File 'lib/rbtree/tree.rb', line 152

def successor(x)
  return minimum(x.right) unless x.right.nil?
  
  y = x.parent
  while !y.nil? && x == y.right
    x = y
    y = y.parent
  end
  y
end

#upper_bound(key, node = root) ⇒ Object

Returns a node with the largest key that is <= then given key.

Returns nil if called on an empty tree or the guard node.



224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
 
# File 'lib/rbtree/tree.rb', line 224

def upper_bound(key, node = root)
  return nil if node.nil?
  loop do
    cmp = key <=> node.key
    return node if cmp == 0
    if cmp < 0
      next_node = node.left
      return predecessor(node) if next_node.nil?
    else
      next_node = node.right
      return node if next_node.nil?
    end
    node = next_node
  end
end