Class: DSA::BasicBinarySearchTree
- Inherits:
-
Object
- Object
- DSA::BasicBinarySearchTree
- Includes:
- Enumerable
- Defined in:
- lib/DSA/binary_search_tree.rb
Overview
A basic binary search tree(or ordered map), with no specific self balancing
Direct Known Subclasses
Instance Method Summary collapse
- #[](key) ⇒ Object
- #[]=(key, value) ⇒ Object
-
#bfs_print ⇒ Object
breadth first traversal.
- #delete(key) ⇒ Object
- #each ⇒ Object
-
#ge(key) ⇒ Object
yield the key/value pair for all those great than or equal to input key.
-
#gt(key) ⇒ Object
yield the key/value pair for all those great than input key.
-
#initialize ⇒ BasicBinarySearchTree
constructor
A new instance of BasicBinarySearchTree.
-
#le(key) ⇒ Object
yield the key/value pair for all those great than or equal to input key.
-
#lt(key) ⇒ Object
yield the key/value pair for all those less than input key.
- #max ⇒ Object
- #min ⇒ Object
Constructor Details
#initialize ⇒ BasicBinarySearchTree
Returns a new instance of BasicBinarySearchTree.
18 19 20 |
# File 'lib/DSA/binary_search_tree.rb', line 18 def initialize @root = nil end |
Instance Method Details
#[](key) ⇒ Object
38 39 40 41 42 43 44 45 46 |
# File 'lib/DSA/binary_search_tree.rb', line 38 def [](key) return nil if @root.nil? node = find_node @root, key if node node.value else nil end end |
#[]=(key, value) ⇒ Object
22 23 24 25 26 27 28 29 |
# File 'lib/DSA/binary_search_tree.rb', line 22 def []=(key, value) new_node = BasicBinarySearchTreeNode.new(key, value) if @root.nil? @root = new_node else insert(@root, new_node) end end |
#bfs_print ⇒ Object
breadth first traversal
190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 |
# File 'lib/DSA/binary_search_tree.rb', line 190 def bfs_print puts '=' * 100 level = [@root] until level.empty? next_level = [] level.each do |node| if node printf "<#{node.key}, #{node.value}>" printf "(parent_is_#{node.parent.key})\t" if node != @root next_level.push node.left next_level.push node.right else printf "<Nil>\t" next_level.push nil next_level.push nil end end puts if next_level.count(nil) < next_level.length level = next_level else level = [] end end puts '=' * 100 end |
#delete(key) ⇒ Object
31 32 33 34 35 36 |
# File 'lib/DSA/binary_search_tree.rb', line 31 def delete(key) return nil if @root.nil? node = find_node @root, key return nil if node.nil? delete_node(node).first.value end |
#each ⇒ Object
160 161 162 163 164 165 166 167 168 169 170 171 |
# File 'lib/DSA/binary_search_tree.rb', line 160 def each return if @root.nil? if block_given? in_order_traversal @root, Proc.new else Enumerator.new do |y| each do |key, value| y << [key, value] end end end end |
#ge(key) ⇒ Object
yield the key/value pair for all those great than or equal to input key
103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 |
# File 'lib/DSA/binary_search_tree.rb', line 103 def ge(key) return nil if @root.nil? if block_given? node = find_node @root, key yield [node.key, node.value] if node node = find_gt_node @root, key if node yield [node.key, node.value] loop do node = in_order_next_node node if node yield [node.key, node.value] else break end end end else Enumerator.new do |y| ge(key) do |key, value| y << [key, value] end end end end |
#gt(key) ⇒ Object
yield the key/value pair for all those great than input key
49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
# File 'lib/DSA/binary_search_tree.rb', line 49 def gt(key) return nil if @root.nil? if block_given? node = find_gt_node @root, key if node yield [node.key, node.value] loop do node = in_order_next_node node if node yield [node.key, node.value] else break end end end else Enumerator.new do |y| gt(key) do |key, value| y << [key, value] end end end end |
#le(key) ⇒ Object
yield the key/value pair for all those great than or equal to input key
131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 |
# File 'lib/DSA/binary_search_tree.rb', line 131 def le(key) return nil if @root.nil? if block_given? node = find_node @root, key yield [node.key, node.value] if node node = find_lt_node @root, key if node yield [node.key, node.value] loop do node = in_order_prev_node node if node yield [node.key, node.value] else break end end end else Enumerator.new do |y| le(key) do |key, value| y << [key, value] end end end end |
#lt(key) ⇒ Object
yield the key/value pair for all those less than input key
77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
# File 'lib/DSA/binary_search_tree.rb', line 77 def lt(key) return nil if @root.nil? if block_given? node = find_lt_node @root, key if node yield [node.key, node.value] loop do node = in_order_prev_node node if node yield [node.key, node.value] else break end end end else Enumerator.new do |y| lt(key) do |key, value| y << [key, value] end end end end |
#max ⇒ Object
181 182 183 184 185 186 187 |
# File 'lib/DSA/binary_search_tree.rb', line 181 def max if @root.nil? nil else max_node(@root).value end end |
#min ⇒ Object
173 174 175 176 177 178 179 |
# File 'lib/DSA/binary_search_tree.rb', line 173 def min if @root.nil? nil else min_node(@root).value end end |