Class: RBTree::Tree
- Inherits:
-
Object
- Object
- RBTree::Tree
- 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
Instance Attribute Summary collapse
-
#root ⇒ Object
readonly
The tree’s root node.
-
#size ⇒ Object
readonly
The number of nodes in the tree.
Instance Method Summary collapse
-
#black_height(node = root) ⇒ Object
Number of black nodes on each path from the given node to a leaf.
-
#delete(z) ⇒ Object
Removes a node from the tree.
-
#empty? ⇒ Boolean
True if the tree has no nodes in it.
-
#initialize ⇒ Tree
constructor
Creates a new tree.
-
#initialize_copy(source) ⇒ Object
Makes a deep copy of the source’s tree, but uses the original keys & values.
-
#inorder(node = root) ⇒ Object
Yields all nodes in the given node’s subtree, in ascending key order.
-
#insert(node) ⇒ Object
Adds a new Node to the tree.
-
#lower_bound(key, node = root) ⇒ Object
Returns the node with the smallest key that is >= the given key.
-
#maximum(node = root) ⇒ Object
The node with the highest key in the subtree rooted at the given node.
-
#minimum(node = root) ⇒ Object
The node with lowest key in the subtree rooted at the given node.
-
#node(key, value) ⇒ Object
Creates a new node holding a given key and value.
-
#predecessor(x) ⇒ Object
The node with the highest key that is lower than the given node’s key.
-
#reverse_inorder(node = root) ⇒ Object
Yields all nodes in the given node’s subtree, in descending key order.
-
#search(key, node = root) ⇒ Object
Returns a node containing the given key or nil if no node contains the key.
-
#successor(x) ⇒ Object
The node with the lowest key that is higher than the given node’s key.
-
#upper_bound(key, node = root) ⇒ Object
Returns a node with the largest key that is <= then given key.
Constructor Details
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.
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 |