class Algorithmable::DataStructs::Tree::BinarySearch
Public Class Methods
new(collection = [])
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 8 def initialize(collection = []) @root = nil collection.each { |item| put item } end
Public Instance Methods
balanced?(diff = 1)
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 102 def balanced?(diff = 1) (max_depth - min_depth) <= diff end
each(&block)
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 45 def each(&block) each_with_dfs(&block) end
each_with_bfs(&block)
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 54 def each_with_bfs(&block) tmp = collect_nodes_with_bfs(@root).to_a block_given? ? tmp.each(&block) : tmp end
each_with_dfs(&block)
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 49 def each_with_dfs(&block) tmp = collect_nodes_with_dfs(@root).to_a block_given? ? tmp.each(&block) : tmp end
empty?()
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 27 def empty? 0 == size end
flip!()
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 85 def flip! @root = flip_bang_imp! @root, 0 end
flip_bang_imp!(n, count)
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 89 def flip_bang_imp!(n, count) return unless n return n unless n.left && n.right new_head = flip_bang_imp! n.left, count + 1 n.left.left = n.right n.left.right = n if count == 0 n.left = nil n.right = nil end new_head end
max()
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 40 def max return if empty? max_impl(@root).item end
max_depth()
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 13 def max_depth max_height_of @root end
Also aliased as: height
min()
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 35 def min return if empty? min_impl(@root).item end
min_depth()
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 19 def min_depth min_height_of @root end
put(object)
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 31 def put(object) @root = put_impl @root, object end
reverse!()
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 81 def reverse! @root = reverse_bang_impl @root end
size()
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 23 def size size_of @root end
to_print()
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 59 def to_print return if empty? queue = new_fifo_queue level = 0 next_level = 1 out = [] queue.enqueue @root until queue.empty? level += 1 node = queue.dequeue out << node.item << ' ' queue.enqueue node.left if node.left queue.enqueue node.right if node.right if level == next_level next_level += queue.size out << "\n" end end out.join end
Private Instance Methods
collect_nodes_with_bfs(root)
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 128 def collect_nodes_with_bfs(root) queue = new_fifo_queue stack = new_lifo_queue queue.enqueue root until queue.empty? node = queue.dequeue stack.push node.item queue.enqueue node.left if node.left queue.enqueue node.right if node.right end stack end
collect_nodes_with_dfs(node)
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 141 def collect_nodes_with_dfs(node) stack = [] dfs_impl node, stack stack end
dfs_impl(node, stack)
click to toggle source
in-order traversal
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 148 def dfs_impl(node, stack) dfs_impl node.left, stack if node.left stack.push node.item dfs_impl node.right, stack if node.right end
make_node(object, size)
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 183 def make_node(object, size) Node.new object, size end
max_height_of(node)
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 108 def max_height_of(node) return 0 unless node 1 + [max_height_of(node.left), max_height_of(node.right)].max end
max_impl(node)
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 154 def max_impl(node) return node if node.right.nil? max_impl(node.right) end
min_height_of(node)
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 113 def min_height_of(node) return 0 unless node 1 + [min_height_of(node.left), min_height_of(node.right)].min end
min_impl(node)
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 159 def min_impl(node) return node if node.left.nil? min_impl(node.left) end
put_impl(node, object)
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 164 def put_impl(node, object) return make_node(object, 1) unless node case object <=> node.item when -1 node.left = put_impl(node.left, object) when 1 node.right = put_impl(node.right, object) else node.item = object end node.size = 1 + size_of(node.left) + size_of(node.right) node end
reverse_bang_impl(root)
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 118 def reverse_bang_impl(root) return unless root reverse_bang_impl root.left reverse_bang_impl root.right tmp = root.left root.left = root.right root.right = tmp root end
size_of(node)
click to toggle source
# File lib/algorithmable/data_structs/tree/binary_search.rb, line 178 def size_of(node) return 0 if node.nil? node.size end